Problem Description

You are given an integer array nums of length n that contains a permutation of all integers from 0 to n-1.

The problem asks you to compare two types of inversions in this array:

Global inversions: These are pairs of indices (i, j) where:

• i comes before j in the array (0 <= i < j < n)
• The value at position i is greater than the value at position j (nums[i] > nums[j])

Local inversions: These are adjacent pairs where the first element is greater than the second:

• Valid indices are from 0 to n-2 (0 <= i < n - 1)
• The value at position i is greater than its immediate neighbor (nums[i] > nums[i + 1])

Your task is to determine whether the number of global inversions equals the number of local inversions. Return true if they are equal, false otherwise.

Note that every local inversion is also a global inversion (since adjacent elements satisfy the global inversion criteria), but not every global inversion is local. The key insight is that if there exists any global inversion that is not local (i.e., elements that are inverted but not adjacent), then the counts cannot be equal.

The solution cleverly checks if any element at position i is greater than any element at position i+2 or beyond. It maintains the maximum value seen up to position i-2 and compares it with the current element at position i. If such a non-local inversion exists, the function returns false; otherwise, it returns true.

Intuition

The key observation is that every local inversion (adjacent elements out of order) is automatically a global inversion. So if the number of global inversions equals the number of local inversions, it means there are no "extra" global inversions beyond the local ones.

In other words, we need to check if there exists any global inversion that is NOT a local inversion. If such an inversion exists, the counts cannot be equal.

What would a non-local global inversion look like? It would be a pair (i, j) where j > i + 1 and nums[i] > nums[j]. This means elements that are at least 2 positions apart are inverted.

Since the array is a permutation of [0, n-1], in an ideal permutation where global inversions equal local inversions, each element can only be displaced by at most 1 position from its original sorted position. If element nums[i] is greater than nums[i+2], it means the element has moved too far from where it should be.

The solution approach becomes clear: for each position i, we need to check if any element before position i-1 is greater than nums[i]. To do this efficiently, we keep track of the maximum value among all elements up to position i-2. If this maximum is ever greater than nums[i], we've found a non-local global inversion, and we return false.

By maintaining mx = max(nums[0], nums[1], ..., nums[i-2]) and comparing it with nums[i], we can detect if there's any element at least 2 positions before that is greater than the current element, which would create a global inversion that isn't local.

Learn more about Math patterns.

Solution Approach

The implementation uses a single-pass algorithm with constant space complexity to solve the problem efficiently.

Algorithm Steps:

1. Initialize a maximum tracker: Start with mx = 0 to keep track of the maximum value seen so far (excluding the immediate previous element).

2. Iterate through the array starting from index 2: We begin at index 2 because we need to maintain a gap of at least 2 positions between the elements we're comparing.

3. Update and check the maximum: For each position i (starting from 2):

   • First, update mx to be the maximum of itself and nums[i-2]. This ensures mx contains the maximum value from positions 0 to i-2.
   • Then check if mx > nums[i]. If true, we've found a non-local global inversion (an element at least 2 positions before is greater than the current element).

4. Return the result:

   • If we find any non-local global inversion during the iteration, immediately return false.
   • If we complete the iteration without finding any, return true.

Implementation Details:

def isIdealPermutation(self, nums: List[int]) -> bool:
    mx = 0
    for i in range(2, len(nums)):
        if (mx := max(mx, nums[i - 2])) > nums[i]:
            return False
    return True

The code uses the walrus operator := to update mx and check the condition in a single line. This is equivalent to:

mx = max(mx, nums[i - 2])
if mx > nums[i]:
    return False

Time and Space Complexity:

• Time Complexity: O(n) where n is the length of the array, as we traverse the array once.
• Space Complexity: O(1) as we only use a single variable mx to track the maximum value.

This approach is optimal because it solves the problem in a single pass without needing to count all inversions explicitly.

Example Walkthrough

Let's walk through the solution with a concrete example to understand how it detects non-local global inversions.

Example 1: nums = [1, 0, 2]

• Step 1: Initialize mx = 0
• Step 2: Start loop at i = 2
  • Update mx = max(0, nums[0]) = max(0, 1) = 1
  • Check if mx > nums[2]: Is 1 > 2? No
• Step 3: Loop ends, return true

This array has only one inversion: (0,1) where nums[0]=1 > nums[1]=0, which is a local inversion. Since all local inversions are also global inversions, the counts are equal.

Example 2: nums = [2, 0, 1]

• Step 1: Initialize mx = 0
• Step 2: Start loop at i = 2
  • Update mx = max(0, nums[0]) = max(0, 2) = 2
  • Check if mx > nums[2]: Is 2 > 1? Yes!
  • Found a non-local global inversion between positions 0 and 2
• Step 3: Return false

This array has global inversions: (0,1) where 2>0, (0,2) where 2>1, and (1,2) where 0<1 (not an inversion). It has only one local inversion: (0,1). Since (0,2) is a global inversion but not local (elements are 2 positions apart), the counts differ.

Example 3: nums = [0, 2, 1, 3]

• Step 1: Initialize mx = 0
• Step 2: Loop from i = 2 to i = 3
  • At i = 2:
    • Update mx = max(0, nums[0]) = max(0, 0) = 0
    • Check if mx > nums[2]: Is 0 > 1? No
  • At i = 3:
    • Update mx = max(0, nums[1]) = max(0, 2) = 2
    • Check if mx > nums[3]: Is 2 > 3? No
• Step 3: Loop ends, return true

This array has one local inversion (1,2) where 2>1, which is also the only global inversion. The algorithm correctly identifies no non-local global inversions exist.

The key insight: By maintaining the maximum of all elements at least 2 positions before the current element, we can efficiently detect if any "far away" element creates a global inversion that isn't local.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the input array nums. The algorithm iterates through the array once, starting from index 2 to the end. In each iteration, it performs constant time operations: finding the maximum between two values (max(mx, nums[i - 2])) and comparing with nums[i]. Since we traverse the array once with constant operations per iteration, the overall time complexity is linear.

Space Complexity: O(1). The algorithm uses only a constant amount of extra space. The variable mx is used to track the maximum value seen so far (excluding the immediate previous element), and the loop variable i is used for iteration. No additional data structures that scale with the input size are created, resulting in constant space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Problem Statement

Pitfall: Many developers initially try to count both global and local inversions separately and compare their counts. This leads to unnecessary complexity and O(n²) time complexity for counting global inversions.

Why it's wrong: Counting all inversions explicitly is inefficient and misses the key insight that every local inversion is also a global inversion.

Incorrect approach example:

def isIdealPermutation(self, nums: List[int]) -> bool:
    # Wrong: Trying to count inversions explicitly
    global_count = 0
    local_count = 0
  
    # O(n²) complexity for global inversions
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] > nums[j]:
                global_count += 1
  
    # O(n) for local inversions
    for i in range(len(nums) - 1):
        if nums[i] > nums[i + 1]:
            local_count += 1
  
    return global_count == local_count

Solution: Recognize that if ANY non-local global inversion exists (elements inverted but not adjacent), the counts cannot be equal. Focus on detecting non-local inversions instead of counting.

2. Off-by-One Errors in Index Management

Pitfall: Starting the loop from the wrong index or incorrectly updating the maximum value tracker.

Common mistakes:

# Wrong: Starting from index 1 instead of 2
for i in range(1, len(nums)):
    mx = max(mx, nums[i - 1])  # This only maintains a gap of 1
    if mx > nums[i]:
        return False

# Wrong: Updating max after comparison
for i in range(2, len(nums)):
    if mx > nums[i]:
        return False
    mx = max(mx, nums[i - 2])  # Should update before comparison

Solution: Ensure the loop starts from index 2 and update the maximum tracker before the comparison to maintain the correct gap of at least 2 positions.

3. Incorrect Maximum Value Tracking

Pitfall: Including elements that are too close to the current position in the maximum value tracker.

Wrong approach:

def isIdealPermutation(self, nums: List[int]) -> bool:
    # Wrong: Including nums[i-1] in the maximum
    mx = 0
    for i in range(2, len(nums)):
        mx = max(mx, nums[i - 1])  # This includes adjacent element!
        if mx > nums[i]:
            return False
    return True

Why it fails: This would flag local inversions as non-local inversions since we're comparing with the immediate previous element.

Solution: Always maintain at least a 2-position gap by only including elements up to nums[i-2] in the maximum tracker.

4. Edge Case Handling

Pitfall: Not handling arrays with length less than 3 properly.

Issue: The algorithm starts from index 2, so arrays of length 0, 1, or 2 need special consideration.

Solution: The current implementation handles this correctly by starting the loop at index 2. For arrays shorter than 3 elements:

• Length 0 or 1: No inversions possible, returns True
• Length 2: Only local inversions possible, returns True

The loop simply doesn't execute for these cases, which is the correct behavior.

5. Misinterpreting the Permutation Property

Pitfall: Not utilizing the fact that the array is a permutation of [0, n-1].

Observation: In an "ideal" permutation where global inversions equal local inversions, each element can be at most 1 position away from its sorted position. This means nums[i] should be in {i-1, i, i+1}.

Alternative solution using this property:

def isIdealPermutation(self, nums: List[int]) -> bool:
    for i in range(len(nums)):
        if abs(nums[i] - i) > 1:
            return False
    return True

This approach is equally valid and perhaps more intuitive once you understand the permutation property.