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] < nnums are unique.nums is a permutation of all the numbers in the range [0, n - 1].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.
We iterate through the array while keeping track of the maximum number seen so far. The core idea is to ensure that the maximum value we pass is less than or equal to both the current value and the follow-up after skipping one (e.g., nums[i+2]).
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) because it requires a single traversal of the array.
Space Complexity: O(1) as no additional data structures are used.
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.
Iterate the array and verify every element index difference from the original is no greater than 1, suggesting only local inversions exist.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n)
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Approach 1: Max Constraint Check | Time Complexity: O(n) because it requires a single traversal of the array. |
| Approach 2: Compare Positions | Time Complexity: O(n) |
Count Inversions in an Array | Brute and Optimal • take U forward • 311,976 views views
Watch 9 more video solutions →Practice Global and Local Inversions with our built-in code editor and test cases.
Practice on FleetCode