LeetCode 775 - Global and Local Inversions

The problem presents an array nums of length n that is a permutation of integers from 0 to n-1. A global inversion is defined as any pair (i, j) such that i < j and nums[i] nums[j], meaning the earlier element is larger than a later element anywhere in the array.

leetcodemediumarraymath

LeetCode Problem 775

Difficulty: 🟡 Medium
Topics: Array, Math

Solution

Problem Understanding

The problem presents an array nums of length n that is a permutation of integers from 0 to n-1. A global inversion is defined as any pair (i, j) such that i < j and nums[i] > nums[j], meaning the earlier element is larger than a later element anywhere in the array. A local inversion is more restrictive: it only considers consecutive elements (i, i+1) where nums[i] > nums[i+1].

The task is to determine whether the total number of global inversions equals the total number of local inversions. If every global inversion in the array is also a local inversion, the array satisfies the condition and the function should return true; otherwise, it should return false.

Constraints provide important context. The array length n can be up to 100,000, and the elements are guaranteed to be unique and a permutation of [0, n-1]. This allows us to consider approaches that exploit permutation properties rather than arbitrary integers. Important edge cases include arrays of length 1 or 2, where inversions are limited, and arrays that are almost sorted except for a single distant inversion, which is enough to break the ideal permutation property.

Approaches

A brute-force approach would count global and local inversions directly. For global inversions, this involves checking all pairs (i, j) with i < j to see if nums[i] > nums[j]. For local inversions, we simply check each consecutive pair. While this produces the correct answer, it requires O(n^2) time for global inversions, which is infeasible for n up to 100,000.

A key observation allows an optimal solution. Every local inversion is a global inversion by definition. Therefore, the only situation where the number of global inversions exceeds local inversions is when there exists a non-local global inversion, i.e., a pair (i, j) with j > i + 1 and nums[i] > nums[j]. By tracking the maximum value encountered so far and comparing it to subsequent elements at distance greater than 1, we can detect any non-local inversion in linear time.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(1) Count all pairs for global inversions and all consecutive pairs for local inversions
Optimal O(n) O(1) Check for non-local inversions using a running maximum and single pass through the array

Algorithm Walkthrough

  1. Initialize a variable max_seen to nums[0]. This will track the largest number seen so far while iterating.
  2. Iterate through the array from index 1 to n-2. We stop at n-2 because local inversions at the end do not create non-local global inversions.
  3. For each index i, update max_seen to the maximum of max_seen and nums[i].
  4. Check if max_seen > nums[i + 1]. If it is, this indicates a non-local inversion because an element earlier in the array is larger than a later element not immediately next to it. Return false immediately.
  5. If no non-local inversion is found during the iteration, return true at the end.

Why it works: By definition, any local inversion is automatically counted as a global inversion. Therefore, the array has equal global and local inversions if and only if no non-local global inversion exists. This algorithm checks for precisely that condition efficiently using a running maximum.

Python Solution

from typing import List

class Solution:
    def isIdealPermutation(self, nums: List[int]) -> bool:
        max_seen = nums[0]
        for i in range(1, len(nums) - 1):
            max_seen = max(max_seen, nums[i])
            if max_seen > nums[i + 1]:
                return False
        return True

The Python implementation uses a simple for loop and a running maximum. At each step, we update max_seen to track the largest number so far, then check against nums[i + 1] to detect a non-local inversion. The loop stops at len(nums) - 2 because the last element cannot create a non-local inversion. This corresponds directly to the algorithm walkthrough.

Go Solution

func isIdealPermutation(nums []int) bool {
    if len(nums) < 2 {
        return true
    }
    maxSeen := nums[0]
    for i := 1; i < len(nums)-1; i++ {
        if nums[i] > maxSeen {
            maxSeen = nums[i]
        }
        if maxSeen > nums[i+1] {
            return false
        }
    }
    return true
}

The Go version mirrors the Python logic. It initializes maxSeen with the first element, iterates through indices 1 to len(nums)-2, updates maxSeen, and checks for a non-local inversion. Go requires explicit index management and uses len(nums) instead of Python's range. Edge cases such as arrays of length 1 or 2 are handled by returning true immediately when no iterations can occur.

Worked Examples

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

i max_seen nums[i+1] Check
1 max(1,0)=1 2 1 > 2? No
Iteration completes, return true. Only one global inversion (1>0) which is local.

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

i max_seen nums[i+1] Check
1 max(1,2)=2 0 2 > 0? Yes
Return false immediately. There is a global inversion (2>0) that is not local.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass through the array to track max_seen and check non-local inversions
Space O(1) Only one variable max_seen is used; no additional data structures are required

The optimal solution avoids nested loops and does not require sorting or extra storage, ensuring linear runtime and constant space usage, which is efficient for n up to 100,000.

Test Cases

# Provided examples
assert Solution().isIdealPermutation([1,0,2]) == True  # 1 global = 1 local
assert Solution().isIdealPermutation([1,2,0]) == False # 2 global > 1 local

# Edge cases
assert Solution().isIdealPermutation([0]) == True      # single element
assert Solution().isIdealPermutation([1,0]) == True    # 1 local inversion, same as global
assert Solution().isIdealPermutation([0,1]) == True    # sorted array, no inversions
assert Solution().isIdealPermutation([2,0,1]) == False # non-local inversion exists
assert Solution().isIdealPermutation([0,2,1,3]) == True# local inversion only at index 1
assert Solution().isIdealPermutation([3,2,1,0]) == False# all global inversions not local
Test Why
[1,0,2] Single nontrivial local inversion matches global inversion
[1,2,0] Non-local inversion breaks ideal property
[0] Minimal array, no inversions possible
[1,0] Only one inversion, which is local
[0,1] Fully sorted, no inversions
[2,0,1] Non-local inversion exists
[0,2,1,3] Only local inversion exists
[3,2,1,0] Multiple non-local inversions exist

Edge Cases

One important edge case is an array of length 1, such as [0]. There are no pairs to compare, so both global and local inversion counts are zero, and the function correctly returns true.

A second edge case is an array of length 2, such as [1,0]. Here, a single inversion is both local and global. The algorithm handles this correctly because the loop will not iterate past len(nums)-2 if the array is too small, returning true.

A third edge case involves a near-sorted array where a single distant element creates a non-local inversion, such as [0,1,3,2]. Without careful checking of non-local inversions, a naive algorithm might incorrectly return true. The running maximum ensures that 3 > 2 is detected as a non-local inversion, and the function correctly returns false.

This solution robustly handles all these edge cases by leveraging the property that any non-local inversion immediately disqualifies the array from having equal global and local inversions.