775. Global and Local Inversions
1. Description
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.
2. Example
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.
3. Constraints
- n == nums.length
- 1 <= n <= 5000
- 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].
4. Solutions
4.1 Brute Force
n = i_nums.size()
Time complexity: O($n^2$)
Space complexity: O(1)
class Solution {
public:
// bool isIdealPermutation(vector<int>& nums)
bool isIdealPermutation(const vector<int>& i_nums) {
for (int i = 0; i < i_nums.size(); ++i) {
for (int j = i + 2; j < i_nums.size(); ++j) {
if (i_nums[i] > i_nums[j]) {
return false;
}
}
}
return true;
}
};
4.2 Iteration
n = i_nums.size()
Time complexity: O(n)
Space complexity: O(1)
class Solution {
public:
// bool isIdealPermutation(vector<int>& nums)
bool isIdealPermutation(const vector<int>& i_nums) {
int minRightValue = INT_MAX;
for (int i = i_nums.size() - 1; i > 1; --i) {
minRightValue = min(i_nums[i], minRightValue);
if (i_nums[i - 2] > minRightValue) { // we could find a nonglobal inversion
return false;
}
}
return true;
}
};
4.3 Iteration
n = i_nums.size()
Time complexity: O(n)
Space complexity: O(1)
class Solution {
public:
// bool isIdealPermutation(vector<int>& nums)
bool isIdealPermutation(const vector<int>& i_nums) {
for (int i = 0; i < i_nums.size(); ++i) {
// a value could be its correct position, like number 5's index should be 5
// also, its position could be the previous one, like number 5's index could be 4
// because it could exchange its position with the previous value also, its position
// could be the following one because it could exchange its position with the following
// value if its index is not locate at these three positions, it must be invalid
if (i_nums[i] > i + 1 || i_nums[i] < i - 1) {
return false;
}
}
return true;
}
};