775. Global and Local Inversions LeetCode Solution
In this guide, you will get 775. Global and Local Inversions LeetCode Solution with the best time and space complexity. The solution to Global and Local Inversions problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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 nums[j]
The number of local inversions is the number of indices i where:
0 <= 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.length
1 <= n <= 105
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].
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
775. Global and Local Inversions LeetCode Solution in C++
class Solution {
public:
bool isIdealPermutation(vector<int>& nums) {
int mx = -1; // the number that is most likely > nums[i + 2]
for (int i = 0; i + 2 < nums.size(); ++i) {
mx = max(mx, nums[i]);
if (mx > nums[i + 2])
return false;
}
return true;
}
}; /* code provided by PROGIEZ */
775. Global and Local Inversions LeetCode Solution in Java
class Solution {
public boolean isIdealPermutation(int[] nums) {
int mx = -1; // the number that is most likely > nums[i + 2]
for (int i = 0; i + 2 < nums.length; ++i) {
mx = Math.max(mx, nums[i]);
if (mx > nums[i + 2])
return false;
}
return true;
}
} // code provided by PROGIEZ
775. Global and Local Inversions LeetCode Solution in Python
class Solution:
def isIdealPermutation(self, nums: list[int]) -> bool:
mx = -1 # the number that is most likely > nums[i + 2]
for i in range(len(nums) - 2):
mx = max(mx, nums[i])
if mx > nums[i + 2]:
return False
return True # code by PROGIEZ
