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.
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; }}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.