This approach checks the condition if there is any inversion other than local inversions by checking for the maximum value condition constraint. We assume that if there exists any i such that nums[i] > nums[j] and j > i + 1, then it implies that the number of global inversions is greater than the number of local inversions.
Therefore, ensure for all i, nums[i] > nums[i+2] does not hold since, for it, nums[i] should be larger than any of the elements up to at least i + 2.
Time Complexity: O(n) because it requires a single traversal of the array.
Space Complexity: O(1) as no additional data structures are used.
1class Solution {
2 public boolean isIdealPermutation(int[] nums) {
3 int max = -1;
4 for (int i = 0; i < nums.length - 2; i++) {
5 max = Math.max(max, nums[i]);
6 if (max > nums[i + 2]) return false;
7 }
8 return true;
9 }
10}Here, we iterate with the idea of calculating the maximum value from the first to two less than the current index. If any max is greater than a non-contributing local inversion, return false.
In this method, we will check each element if it is in a permissible range, conditionally permitting swaps with one element left or right, as can occur with local inversions. Assume an element is misplaced if it is not at i or i ± 1.
Time Complexity: O(n)
Space Complexity: O(1)
1class Solution {
2 public boolean isIdealPermutation(int[] nums) {
3 for (int i = 0; i < nums.length; i++) {
4 if (Math.abs(nums[i] - i) > 1) {
5 return false;
6 }
7 }
8 return true;
9 }
10}In Java implementation achieves logic verification by using Math.abs to ensure the allowed swap window is within [-1, 1].