775. Global and Local Inversions Solution

The 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 of global inversions is equal to the number of local inversions.

Example 1:

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

Example 2:

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

Constraints:

n == nums.length
1 <= n <= 10⁵
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].

Approach overview

Problem Overview: You are given a permutation of numbers from 0 to n-1. A local inversion occurs when nums[i] > nums[i+1], while a global inversion occurs when nums[i] > nums[j] for any i < j. The task is to check whether the total number of global inversions is exactly equal to the number of local inversions.

For the two counts to match, every global inversion must also be a local inversion. That means the array cannot contain any inversion where the distance between indices is greater than one. Any such pair automatically makes global inversions exceed local inversions.

Approach 1: Max Constraint Check (O(n) time, O(1) space)

This approach scans the array while tracking the maximum value seen so far up to index i. For each position, compare that maximum with nums[i+2]. If the previous maximum is greater than nums[i+2], a non-local global inversion exists because the larger element appears at least two indices before a smaller one. That directly violates the condition that all global inversions must be local.

The algorithm performs a single pass through the array and maintains only one running maximum. The moment a violation is detected, you can return false. If no such pair appears, every inversion is adjacent. This method is efficient because it avoids explicitly counting inversions and relies on a simple constraint check derived from the permutation structure. Problems involving permutation properties and constraints like this often appear in array reasoning tasks.

Approach 2: Compare Positions (O(n) time, O(1) space)

This method uses a key property of ideal permutations. If global inversions equal local inversions, each element can be displaced from its sorted position by at most one index. In other words, for every index i, the condition |nums[i] - i| ≤ 1 must hold.

You iterate through the array and compute the absolute difference between the value and its index. If any element is more than one position away from where it belongs in the sorted order, that displacement necessarily creates a non-local global inversion. Because the array is a permutation of 0..n-1, this check works in constant space and linear time. The reasoning relies on simple permutation math, which is common in math and array interview problems.

Recommended for interviews: The Max Constraint Check approach is typically expected in interviews because it demonstrates understanding of how global inversions extend beyond adjacent indices. It directly proves that no element two positions ahead violates the ordering constraint. The position comparison trick is shorter and elegant, but explaining the reasoning behind the displacement rule is essential to show deeper insight.

Approach 1: Approach 1: Max Constraint Check

This approach checks the condition if there is any inversion other than local inversions by checking for the maximum value condition constraint. We assume that if there exists any i such that nums[i] > nums[j] and j > i + 1, then it implies that the number of global inversions is greater than the number of local inversions.

Therefore, ensure for all i, nums[i] > nums[i+2] does not hold since, for it, nums[i] should be larger than any of the elements up to at least i + 2.

Python

def isIdealPermutation(nums):
    max_val = -1
    for i in range(len(nums) - 2):
        max_val = max(max_val, nums[i])
        if max_val > nums[i + 2]:
            return False
    return True

Java

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

C++

#include <vector>
using namespace std;

class Solution {
public:
    bool isIdealPermutation(vector<int>& nums) {
        int maxVal = -1;
        for (int i = 0; i < nums.size() - 2; i++) {
            maxVal = max(maxVal, nums[i]);
            if (maxVal > nums[i + 2]) return false;
        }
        return true;
    }
};

JavaScript

function isIdealPermutation(nums) {
    let maxVal = -1;
    for (let i = 0; i < nums.length - 2; i++) {
        maxVal = Math.max(maxVal, nums[i]);
        if (maxVal > nums[i + 2]) return false;
    }
    return true;
}

#include <stdbool.h>

bool isIdealPermutation(int* nums, int numsSize){
    int max = -1;
    for (int i = 0; i < numsSize - 2; i++) {
        if (max < nums[i]) {
            max = nums[i];
        }
        if (max > nums[i + 2]) {
            return false;
        }
    }
    return true;
}

public class Solution {
    public bool IsIdealPermutation(int[] nums) {
        int maxVal = -1;
        for (int i = 0; i < nums.Length - 2; i++) {
            maxVal = Math.Max(maxVal, nums[i]);
            if (maxVal > nums[i + 2]) return false;
        }
        return true;
    }
}

The Python solution follows the same logic, where we dynamically compute the maximum value seen so far and ensure correctness by checking against values two indices ahead.

Complexity

Time Complexity: O(n).
Space Complexity: O(1).

Try this approach in the editor

Approach 2: Approach 2: Compare Positions

In this method, we will check each element if it is in a permissible range, conditionally permitting swaps with one element left or right, as can occur with local inversions. Assume an element is misplaced if it is not at i or i ± 1.

Python

def isIdealPermutation(nums):
    return all(abs(num - i) <= 1 for i, num in enumerate(nums))

Java

class Solution {
    public boolean isIdealPermutation(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (Math.abs(nums[i] - i) > 1) {
                return false;
            }
        }
        return true;
    }
}

C++

#include <vector>
#include <cmath>

class Solution {
public:
    bool isIdealPermutation(std::vector<int>& nums) {
        for (int i = 0; i < nums.size(); i++) {
            if (std::abs(nums[i] - i) > 1) {
                return false;
            }
        }
        return true;
    }
};

JavaScript

function isIdealPermutation(nums) {
    for (let i = 0; i < nums.length; i++) {
        if (Math.abs(nums[i] - i) > 1) {
            return false;
        }
    }
    return true;
}

#include <stdbool.h>

bool isIdealPermutation(int* nums, int numsSize){
    for (int i = 0; i < numsSize; i++) {
        if (abs(nums[i] - i) > 1) {
            return false;
        }
    }
    return true;
}

public class Solution {
    public bool IsIdealPermutation(int[] nums) {
        for (int i = 0; i < nums.Length; i++) {
            if (Math.Abs(nums[i] - i) > 1) {
                return false;
            }
        }
        return true;
    }
}

Python's solution uses a simple comprehension to filter check where each number lies within an acceptable index offset, streamlined for clarity and performance.

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Try this approach in the editor

Approach 3: Default Approach

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

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Max Constraint Check	Time Complexity: O(n). Space Complexity: O(1).
Approach 2: Compare Positions	Time Complexity: O(n) Space Complexity: O(1)
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Max Constraint Check	O(n)	O(1)	Best general solution; detects non-local global inversions during a single pass
Compare Positions	O(n)	O(1)	When the permutation property (0..n-1) is guaranteed and you want the shortest logic

Frequently asked questions

Is Global and Local Inversions easy or hard?

The problem is typically classified as Medium difficulty. The brute understanding of inversions is straightforward, but recognizing the constraint that eliminates non-local inversions requires pattern recognition with permutations.

Global and Local Inversions Python/Java solution

Both Python and Java implementations follow the same O(n) logic. Iterate through the array and check either the max-prefix constraint or verify that abs(nums[i] - i) ≤ 1 for every index. Both approaches require constant extra space and a single linear pass.

How to solve Global and Local Inversions in O(n)?

Use a single pass with a constraint check. Track the maximum value up to index i and compare it with nums[i+2]. If the earlier maximum is larger than the element two positions ahead, a non-local inversion exists and the permutation is not ideal. If the scan finishes without violations, global and local inversions are equal.

What is the best approach for Global and Local Inversions?

The most common solution is the Max Constraint Check approach. Traverse the array while keeping the maximum value seen so far and compare it with elements two indices ahead. If max(nums[0..i]) is greater than nums[i+2], a non-local global inversion exists. This runs in O(n) time and O(1) space.

Is Global and Local Inversions asked at Google/Amazon/Meta?

Permutation and inversion-related array problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants involving inversion counting, permutation validation, or displacement constraints are common mid-level interview questions.

What data structure is used in Global and Local Inversions?

The problem mainly relies on array traversal and simple numeric comparisons. No additional data structures are required because the optimal solutions track a running maximum or check element positions directly.

What is the time complexity of Global and Local Inversions?

The optimal algorithms run in O(n) time with O(1) extra space. Both the max constraint method and the position comparison method scan the array once and perform constant-time checks per element.

Global and Local Inversions solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Max Constraint Check

Approach 2: Approach 2: Compare Positions

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Global and Local Inversions solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Max Constraint Check

Approach 2: Approach 2: Compare Positions

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems