Welcome to Subscribe On Youtube
775. Global and Local Inversions
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 < 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].
Solutions
-
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 { 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; } }; -
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 True -
func isIdealPermutation(nums []int) bool { mx := 0 for i := 2; i < len(nums); i++ { mx = max(mx, nums[i-2]) if mx > nums[i] { return false } } return true }