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
Solution 1: Direct Implementation
According to the meaning of the question, we can find that a local inversion in an array must be a global inversion, but a global inversion is not necessarily a local inversion. In other words, the number of global inversions must be greater than or equal to the number of local inversions.
Therefore, we enumerate each number $nums[i]$, where $2 \leq i \leq n - 1$, maintain the maximum value in the prefix array $nums[0,..i-2]$, denoted as $mx$. If there is $mx$ greater than $nums[i]$, it means that the number of global inversions is greater than the number of local inversions, and false can be returned.
After the traversal is completed, true is returned.
Time complexity $O(n)$, space complexity $O(1)$. Where $n$ is the length of the array nums.
Solution 2
This question is actually a “reverse pair” problem.
The number of local inversions is equal to the number of reverse-order pairs between adjacent elements, which can be directly found in the process of traversing the array nums; while the number of global inversions is equal to the number of reverse-order pairs, a common way to find the number of reverse-order pairs is to use a Fenwick tree.
Fenwick tree, also called “Binary Indexed Tree” or Fenwick tree. It can efficiently implement the following two operations:
- Single point update: that is, the function
update(x, delta)adds a value $delta$ to the number at the position of the sequence $x$. Time complexity $O(\log n)$. - Prefix sum query: that is, the function
query(x)queries the interval sum of the sequence[1,...x]interval, that is, the prefix sum of the position $x$. Time complexity $O(\log n)$.
For this question, we define a variable $cnt$ to record the difference between the number of local inversions and the number of global inversions. If the value of $cnt$ is less than $0$ during the traversal process, it means that the number of global inversions is greater than the number of local inversions, and false can be returned.
Time complexity $O(n\times \log n)$, space complexity $O(n)$. Where $n$ is the length of the array nums.
-
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; } } // Solution 2 class BinaryIndexedTree { private int n; private int[] c; public BinaryIndexedTree(int n) { this.n = n; c = new int[n + 1]; } public void update(int x, int delta) { while (x <= n) { c[x] += delta; x += x & -x; } } public int query(int x) { int s = 0; while (x > 0) { s += c[x]; x -= x & -x; } return s; } } class Solution { public boolean isIdealPermutation(int[] nums) { int n = nums.length; BinaryIndexedTree tree = new BinaryIndexedTree(n); int cnt = 0; for (int i = 0; i < n && cnt >= 0; ++i) { cnt += (i < n - 1 && nums[i] > nums[i + 1] ? 1 : 0); cnt -= (i - tree.query(nums[i])); tree.update(nums[i] + 1, 1); } return cnt == 0; } } -
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; } }; // Solution 2 class BinaryIndexedTree { public: BinaryIndexedTree(int _n) : n(_n) , c(_n + 1) {} void update(int x, int delta) { while (x <= n) { c[x] += delta; x += x & -x; } } int query(int x) { int s = 0; while (x) { s += c[x]; x -= x & -x; } return s; } private: int n; vector<int> c; }; class Solution { public: bool isIdealPermutation(vector<int>& nums) { int n = nums.size(); BinaryIndexedTree tree(n); long cnt = 0; for (int i = 0; i < n && ~cnt; ++i) { cnt += (i < n - 1 && nums[i] > nums[i + 1]); cnt -= (i - tree.query(nums[i])); tree.update(nums[i] + 1, 1); } return cnt == 0; } }; -
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 # Solution 2 class BinaryIndexedTree: def __init__(self, n): self.n = n self.c = [0] * (n + 1) def update(self, x, delta): while x <= self.n: self.c[x] += delta x += x & -x def query(self, x): s = 0 while x: s += self.c[x] x -= x & -x return s class Solution: def isIdealPermutation(self, nums: List[int]) -> bool: n = len(nums) tree = BinaryIndexedTree(n) cnt = 0 for i, v in enumerate(nums): cnt += i < n - 1 and v > nums[i + 1] cnt -= i - tree.query(v) if cnt < 0: return False tree.update(v + 1, 1) 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 } // Solution 2 func isIdealPermutation(nums []int) bool { n := len(nums) tree := newBinaryIndexedTree(n) cnt := 0 for i, v := range nums { if i < n-1 && v > nums[i+1] { cnt++ } cnt -= (i - tree.query(v)) if cnt < 0 { break } tree.update(v+1, 1) } return cnt == 0 } type BinaryIndexedTree struct { n int c []int } func newBinaryIndexedTree(n int) BinaryIndexedTree { c := make([]int, n+1) return BinaryIndexedTree{n, c} } func (this BinaryIndexedTree) update(x, delta int) { for x <= this.n { this.c[x] += delta x += x & -x } } func (this BinaryIndexedTree) query(x int) int { s := 0 for x > 0 { s += this.c[x] x -= x & -x } return s }