#775

Medium

LeetCode Problem Workspace

Global and Local Inversions

Determine if every global inversion in a permutation array is also a local inversion using array and math logic efficiently.

array math

Problem Statement

You are given an integer array nums of length n which represents a permutation of the integers from 0 to n - 1. A global inversion is a pair (i, j) where i < j and nums[i] > nums[j].

A local inversion is an index i where nums[i] > nums[i + 1]. Determine whether the number of global inversions is equal to the number of local inversions, returning true if all global inversions are local, otherwise false.

Examples

Example 1

Input: nums = [1,0,2]

Output: true

There is 1 global inversion and 1 local inversion.

Example 2

Input: nums = [1,2,0]

Output: false

There are 2 global inversions and 1 local inversion.

Constraints

n == nums.length
1 <= n <= 105
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 Approach

Track Maximum Before Each Index

Iterate through nums from left to right, maintaining the maximum value seen so far up to index i - 2. If nums[i] is smaller than this max, it indicates a global inversion that is not local, so return false.

Use One-Pass Check

Instead of counting all inversions, use a single pass to check the condition nums[i] > max(previous elements before i-1). This leverages array structure and mathematical reasoning about positions in a permutation.

Return True If No Violations

If the traversal completes without finding any nums[i] violating the maximum-before check, then every global inversion is local, so return true. This method avoids extra space and nested loops.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The approach runs in O(n) time and O(1) extra space by maintaining a running maximum and scanning the array once, avoiding explicit inversion counting.

What Interviewers Usually Probe

Checks if you understand the distinction between local and global inversions.
Wants you to optimize beyond brute-force nested loops.
Seeks recognition of permutation constraints and mathematical bounds for array positions.

Common Pitfalls or Variants

Common pitfalls

Counting inversions directly with nested loops causes timeouts for large arrays.
Ignoring that local inversions are always global inversions can lead to false negatives.
Not considering positions two or more apart for global inversions results in incorrect answers.

Follow-up variants

Determine the number of global inversions minus local inversions instead of boolean check.
Handle arrays that are not strict permutations, requiring extra validation.
Extend to k-local inversions, where an inversion spans at most k indices.

FAQ

What is the main difference between global and local inversions in this problem?

A local inversion is always a global inversion where indices are adjacent, but a global inversion can span non-adjacent indices, which is critical to detect in this problem.

Why is a one-pass solution preferred for Global and Local Inversions?

It leverages the array plus math pattern to maintain a running maximum, avoiding costly nested iteration and reducing time complexity to O(n).

Can this approach handle large arrays up to 105 elements?

Yes, because it scans the array once and uses O(1) extra space, it scales efficiently for large n within the problem constraints.

Is counting local and global inversions separately necessary?

No, direct counting is inefficient; using maximum tracking detects any global inversion that is not local, which suffices for correctness.

How does the permutation property of nums simplify the solution?

Since nums is a permutation of 0 to n - 1, mathematical bounds ensure that checking the maximum before index i - 2 is enough to detect extra global inversions.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

class Solution:
    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

Solution 2

#### Python3

1

2

3

4

5

6

7

class Solution:
    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

Continue Practicing

#781 rabbits in forest #782 transform to chessboard #789 escape the ghosts