Global and Local Inversions
MedPrompt
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 < nnums[i] > nums[j]
The number of local inversions is the number of indices i where:
0 <= i < n - 1nums[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.length1 <= n <= 1050 <= nums[i] < n- All the integers of
numsare unique. numsis a permutation of all the numbers in the range[0, n - 1].
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly translates the problem's definitions into code. It involves two separate counting processes: one for local inversions and one for global inversions. After counting both, it compares them to get the result.
Algorithm
- Initialize
local_inversions = 0andglobal_inversions = 0. - Iterate through the array from
i = 0ton-2to count local inversions:- If
nums[i] > nums[i+1], incrementlocal_inversions.
- If
- Use a nested loop to count global inversions:
- The outer loop runs from
i = 0ton-1. - The inner loop runs from
j = i+1ton-1. - If
nums[i] > nums[j], incrementglobal_inversions.
- The outer loop runs from
- Return
trueiflocal_inversions == global_inversions, otherwise returnfalse.
Walkthrough
First, we calculate the number of local inversions. A single loop from the beginning to the second-to-last element is sufficient. Inside the loop, we check if nums[i] > nums[i+1]. If it is, we increment a local_inversions counter.
Next, we calculate the number of global inversions. This requires checking every possible pair of indices (i, j) where i < j. A nested loop structure is a natural fit for this. The outer loop iterates i from 0 to n-1, and the inner loop iterates j from i+1 to n-1. Inside the inner loop, we check if nums[i] > nums[j] and increment a global_inversions counter if the condition is true.
Finally, we compare the two counts. If they are equal, we return true; otherwise, we return false.
class Solution { public boolean isIdealPermutation(int[] nums) { int n = nums.length; int localInversions = 0; for (int i = 0; i < n - 1; i++) { if (nums[i] > nums[i + 1]) { localInversions++; } } int globalInversions = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (nums[i] > nums[j]) { globalInversions++; } } } return globalInversions == localInversions; }}Complexity
Time
O(n^2), due to the nested loops for counting global inversions. The O(n) loop for local inversions is dominated by the quadratic part.
Space
O(1), as we only use a few variables to store the counts.
Trade-offs
Pros
Very simple to understand and implement as it follows the problem definition literally.
Cons
The time complexity is O(n^2), which is too slow for the given constraints (n up to 10^5) and will likely result in a 'Time Limit Exceeded' error.
The bottleneck in the brute-force approach is the O(n^2) calculation of global inversions. A standard and more efficient way to count all inversions in an array is to use a modified Merge Sort algorithm. This approach improves the time complexity from quadratic to log-linear.
Algorithm
- Calculate the number of local inversions with a simple O(n) loop and store it.
- Create a helper function for a modified merge sort that counts global inversions.
- The main merge sort function recursively splits the array in half.
- The merge function merges two sorted halves and counts inversions. When an element from the right half is chosen before an element from the left half, it signifies an inversion.
- The number of inversions is the count of elements remaining in the left half.
- Sum up the inversions from the recursive calls and the merge step.
- Compare the final global inversion count with the local inversion count.
Walkthrough
We still begin by counting the local inversions in O(n) time, as this is already efficient. The main change is how we count global inversions. The divide-and-conquer strategy of Merge Sort is perfectly suited for this. As we merge two sorted subarrays, say left and right, if we encounter a situation where left[i] > right[j], it means that right[j] is smaller than all the remaining elements in the left subarray (from index i onwards). This allows us to count a batch of inversions at once instead of one by one.
The total number of global inversions is the sum of inversions within the left half, inversions within the right half, and the inversions that cross between the two halves (which are counted during the merge step).
class Solution { public boolean isIdealPermutation(int[] nums) { int n = nums.length; int localInversions = 0; for (int i = 0; i < n - 1; i++) { if (nums[i] > nums[i + 1]) { localInversions++; } } int[] temp = new int[n]; long globalInversions = countGlobalInversions(nums, temp, 0, n - 1); return globalInversions == localInversions; } private long mergeAndCount(int[] nums, int[] temp, int left, int mid, int right) { System.arraycopy(nums, left, temp, left, right - left + 1); int i = left; int j = mid + 1; int k = left; long inversions = 0; while (i <= mid && j <= right) { if (temp[i] <= temp[j]) { nums[k++] = temp[i++]; } else { nums[k++] = temp[j++]; inversions += (mid - i + 1); } } while (i <= mid) { nums[k++] = temp[i++]; } return inversions; } private long countGlobalInversions(int[] nums, int[] temp, int left, int right) { long inversions = 0; if (left < right) { int mid = left + (right - left) / 2; inversions += countGlobalInversions(nums, temp, left, mid); inversions += countGlobalInversions(nums, temp, mid + 1, right); inversions += mergeAndCount(nums, temp, left, mid, right); } return inversions; }}Complexity
Time
O(n log n), which is the time complexity of the merge sort algorithm for counting inversions. The O(n) scan for local inversions does not change the overall complexity.
Space
O(n), for the temporary array required by the merge sort algorithm.
Trade-offs
Pros
Much more efficient than the brute-force approach, with O(n log n) time complexity.
It's a classic application of the divide-and-conquer paradigm.
Cons
Requires O(n) auxiliary space for the merge sort algorithm.
More complex to implement correctly compared to the brute-force or linear scan approaches.
This optimal approach is based on a crucial observation: every local inversion (where nums[i] > nums[i+1]) is, by definition, also a global inversion. Therefore, the total number of global inversions can only equal the number of local inversions if and only if there are no other types of global inversions. These 'other' types are non-local inversions: pairs (i, j) where nums[i] > nums[j] and j > i + 1.
The problem thus simplifies to checking if any non-local inversion exists. If we find even one, we can immediately say the counts are not equal and return false. If we scan the entire array and find none, we can return true.
Algorithm
- The core idea is that for the number of global and local inversions to be equal, there must be no non-local global inversions.
- A non-local global inversion is a pair
(k, i)wherek <= i - 2andnums[k] > nums[i]. - We can check for such an inversion in a single pass from left to right.
- Initialize a variable
max_so_farto track the maximum value seen innums[0...k]. - Iterate with
ifrom2ton-1. - Before checking
nums[i],max_so_farshould holdmax(nums[0], ..., nums[i-2]). - If
nums[i] < max_so_far, we have found a non-local inversion, so we can immediately returnfalse. - After the check, update
max_so_farto includenums[i-1]for the next iteration. - If the loop completes without returning
false, it means no non-local inversions exist, so we returntrue.
Walkthrough
To efficiently check for a non-local inversion, we can iterate through the array while keeping track of the maximum value encountered so far. A non-local inversion (k, i) exists if nums[k] > nums[i] for some k <= i - 2. This is equivalent to saying that for some i, nums[i] is smaller than the maximum value in the prefix nums[0...i-2].
We can implement this with a single loop. We maintain a variable, let's call it max_val, which at the beginning of the loop for index i, will store max(nums[0], ..., nums[i-2]). We start the loop at i = 2. In each iteration, we check if nums[i] < max_val. If it is, we've found our non-local inversion and return false. After the check, we update max_val by taking max(max_val, nums[i-1]) to prepare for the next iteration. If the loop finishes, no non-local inversions were found, and we return true.
A remarkably simple and equivalent check is to verify if abs(nums[i] - i) <= 1 for all i. Any element nums[i] that is more than one position away from its sorted-order index i will create a non-local inversion.
class Solution { public boolean isIdealPermutation(int[] nums) { // The condition is equivalent to checking if for any i, // nums[i] < max(nums[0], nums[1], ..., nums[i-2]). // Or, equivalently, if |nums[i] - i| <= 1 for all i. for (int i = 0; i < nums.length; i++) { if (Math.abs(nums[i] - i) > 1) { return false; } } return true; }} // Alternative implementation based on the max_so_far logic:/*class Solution { public boolean isIdealPermutation(int[] nums) { if (nums.length <= 2) { return true; } int maxVal = nums[0]; for (int i = 2; i < nums.length; i++) { if (nums[i] < maxVal) { return false; } maxVal = Math.max(maxVal, nums[i - 1]); } return true; }}*/Complexity
Time
O(n), as we iterate through the array only once.
Space
O(1), as we only use a few variables to track state during the single pass.
Trade-offs
Pros
Extremely efficient with optimal O(n) time complexity.
Uses constant O(1) extra space.
The implementation is very short and simple.
Cons
The underlying logic, while simple once understood, is less direct than the brute-force approach and requires a key insight into the problem structure.
Solutions
Solution
class Solution {public boolean isIdealPermutation(int[] nums) { int mx = 0; for (int i = 2; i < nums.length; ++i) { mx = Math.max(mx, nums[i - 2]); if (mx > nums[i]) { return false; } } return true; }}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 Trueclass Solution {public: bool isIdealPermutation(vector<int> &nums) { int mx = 0; for (int i = 2; i < nums.size(); ++i) { mx = max(mx, nums[i - 2]); if (mx > nums[i]) return false; } return true; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.