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 < jwithnums[i] > nums[j]. - A local inversion is an index
iwithnums[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^50 <= nums[i] < nums.lengthAll the integers ofnumsare unique.- `
numsis a permutation of all the numbers in the range[0, n - 1].`
Hints for Global and Local Inversions
Hint 1
Since every local inversion is global, the counts are equal exactly when there is no global inversion that is not local.
Hint 2
A non-local inversion is a pair
i < jwithj >= i + 2andnums[i] > nums[j].Hint 3
Scan left to right keeping the maximum of
nums[0..j-2]; if it ever exceedsnums[j], the answer isfalse.
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
- Keep
maxSeen, the largest value amongnums[0..j-2]. - For each
jfrom 2 upward, first foldnums[j-2]intomaxSeen. - If
maxSeen > nums[j], somei <= j - 2forms a non-local inversion withj— returnfalse. - 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| <= 1for everyi, which holds because the values are exactly0..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 TrueJava
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