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)
1#include <vector>
2#include <cmath>
3
4class Solution {
5public:
6 bool isIdealPermutation(std::vector<int>& nums) {
7 for (int i = 0; i < nums.size(); i++) {
8 if (std::abs(nums[i] - i) > 1) {
9 return false;
10 }
11 }
12 return true;
13 }
14};This solution uses the absolute value check for misplacement beyond what local inversions would allow, verifying the oversteps in distance.