Global and Local Inversions

Medium
1125.

Global and Local Inversions

Global and Local Inversions is a medium coding problem on arrays and math, asked in Amazon and Google interviews.

nums is a permutation of the integers 0 to n - 1.

  • A global inversion is a pair of indices i < j with nums[i] > nums[j].
  • A local inversion is an index i with nums[i] > nums[i + 1].

Every local inversion is also a global one. Return true if the number of global inversions equals the number of local inversions.

Example 1

Input
nums = [0,2,1,3]
Output
true
Explanation
The only inversion is `(2, 1)`, and it is adjacent.

Example 2

Input
nums = [2,0,1]
Output
false
Explanation
Global inversions: `(2, 0)` and `(2, 1)`. Local: only `(2, 0)`.

Example 3

Input
nums = [0]
Output
true

Constraints

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] < nums.length
  • All the integers of nums are unique.
  • `nums is a permutation of all the numbers in the range [0, n - 1].`
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var isIdealPermutation = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Global and Local Inversions — Solution in Python, Java & C++

Global and Local Inversions solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Global and Local Inversions is a medium coding problem on arrays and math, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Math
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

nums is a permutation of the integers 0 to n - 1.

  • A global inversion is a pair of indices i < j with nums[i] > nums[j].
  • A local inversion is an index i with nums[i] > nums[i + 1].

Every local inversion is also a global one. Return true if the number of global inversions equals the number of local inversions.

Example 1

Input: nums = [0,2,1,3]
Output: true
Explanation: The only inversion is `(2, 1)`, and it is adjacent.

Example 2

Input: nums = [2,0,1]
Output: false
Explanation: Global inversions: `(2, 0)` and `(2, 1)`. Local: only `(2, 0)`.

Example 3

Input: nums = [0]
Output: true

Constraints

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

Hints for Global and Local Inversions

  1. Hint 1

    Since every local inversion is global, the counts are equal exactly when there is no global inversion that is not local.

  2. Hint 2

    A non-local inversion is a pair i < j with j >= i + 2 and nums[i] > nums[j].

  3. Hint 3

    Scan left to right keeping the maximum of nums[0..j-2]; if it ever exceeds nums[j], the answer is false.

How to solve Global and Local Inversions

Local inversions are a subset of global ones, so the counts match exactly when no inversion spans a gap of two or more positions.

Approach

  1. Keep maxSeen, the largest value among nums[0..j-2].
  2. For each j from 2 upward, first fold nums[j-2] into maxSeen.
  3. If maxSeen > nums[j], some i <= j - 2 forms a non-local inversion with j — return false.
  4. If the scan finishes, return true.

Why it works

Global = local + (number of inversions with distance at least 2). The difference is zero precisely when that second set is empty. For a fixed j, such an inversion exists iff some earlier value at distance two or more is larger, i.e. iff the prefix maximum up to j - 2 exceeds nums[j]. Checking each j once covers every candidate pair.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Counting global inversions directly is O(n^2) (or O(n log n) with merge sort) and unnecessary.
  • The prefix maximum must stop two positions back — including nums[j-1] would flag legal local inversions.
  • An equivalent test is |nums[i] - i| <= 1 for every i, which holds because the values are exactly 0..n-1.

Reference solution

Python

from typing import List

def isIdealPermutation(nums: List[int]) -> bool:
    max_seen = -1
    for j in range(2, len(nums)):
        max_seen = max(max_seen, nums[j - 2])
        if max_seen > nums[j]:
            return False
    return True

Java

public static boolean isIdealPermutation(int[] nums) {
    int maxSeen = -1;
    for (int j = 2; j < nums.length; j++) {
        maxSeen = Math.max(maxSeen, nums[j - 2]);
        if (maxSeen > nums[j]) return false;
    }
    return true;
}

C++

bool isIdealPermutation(vector<int>& nums) {
    int maxSeen = -1;
    for (int j = 2; j < (int)nums.size(); j++) {
        maxSeen = max(maxSeen, nums[j - 2]);
        if (maxSeen > nums[j]) return false;
    }
    return true;
}

JavaScript

var isIdealPermutation = function(nums) {
    var maxSeen = -1;
    for (var j = 2; j < nums.length; j++) {
        if (nums[j - 2] > maxSeen) maxSeen = nums[j - 2];
        if (maxSeen > nums[j]) return false;
    }
    return true;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays