Problem

You are given an integer array nums of length n which represents a permutation of all the integers in the range [0, n - 1].

The number of global inversions is the number of the different pairs (i, j) where:

  • 0 <= i < j < n
  • nums[i] > nums[j]

The number of local inversions is the number of indices i where:

  • 0 <= i < n - 1
  • nums[i] > nums[i + 1]

Return true if the number ofglobal inversions is equal to the number of local inversions.

Examples

Example 1

1
2
3

Input: nums = [1,0,2]
Output: true
Explanation: There is 1 global inversion and 1 local inversion.

Example 2

1
2
3

Input: nums = [1,2,0]
Output: false
Explanation: There are 2 global inversions and 1 local inversion.

Constraints

  • n == nums.length
  • 1 <= n <= 10^5
  • 0 <= nums[i] < n
  • All the integers of nums are unique.
  • nums is a permutation of all the numbers in the range [0, n - 1].

Solution

Method 1 – Check for Non-local Global Inversions

Intuition

Every local inversion is also a global inversion, but not every global inversion is local. For the counts to be equal, there must be no global inversion that is not local. This means for all i < j - 1, nums[i] < nums[j] must hold. We can check this by tracking the maximum value up to i - 2 and ensuring it is less than nums[i] for all i >= 2.

Approach

  1. Iterate through the array from index 2 to n-1.
  2. Track the maximum value seen so far up to index i-2.
  3. If this maximum is greater than nums[i], return False.
  4. If the loop completes, return True.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    bool isIdealPermutation(vector<int>& nums) {
        int mx = nums[0];
        for (int i = 2; i < nums.size(); ++i) {
            mx = max(mx, nums[i-2]);
            if (mx > nums[i]) return false;
        }
        return true;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func isIdealPermutation(nums []int) bool {
    mx := nums[0]
    for i := 2; i < len(nums); i++ {
        if mx > nums[i] {
            return false
        }
        if nums[i-1] > mx {
            mx = nums[i-1]
        }
    }
    return true
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public boolean isIdealPermutation(int[] nums) {
        int mx = nums[0];
        for (int i = 2; i < nums.length; i++) {
            mx = Math.max(mx, nums[i-2]);
            if (mx > nums[i]) return false;
        }
        return true;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    fun isIdealPermutation(nums: IntArray): Boolean {
        var mx = nums[0]
        for (i in 2 until nums.size) {
            mx = maxOf(mx, nums[i-2])
            if (mx > nums[i]) return false
        }
        return true
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def isIdealPermutation(self, nums: list[int]) -> bool:
        mx = nums[0]
        for i in range(2, len(nums)):
            mx = max(mx, nums[i-2])
            if mx > nums[i]:
                return False
        return True
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

impl Solution {
    pub fn is_ideal_permutation(nums: Vec<i32>) -> bool {
        let mut mx = nums[0];
        for i in 2..nums.len() {
            mx = mx.max(nums[i-2]);
            if mx > nums[i] {
                return false;
            }
        }
        true
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    isIdealPermutation(nums: number[]): boolean {
        let mx = nums[0];
        for (let i = 2; i < nums.length; i++) {
            mx = Math.max(mx, nums[i-2]);
            if (mx > nums[i]) return false;
        }
        return true;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — Single pass through the array.
  • 🧺 Space complexity: O(1) — Only a few variables for tracking maximum.