775. Global and Local Inversions Medium

1/**
2 * [775] Global and Local Inversions
3 *
4 * You are given an integer array nums of length n which represents a permutation of all the integers in the range [0, n - 1].
5 * The number of global inversions is the number of the different pairs (i, j) where:
6 * 
7 * 	0 <= i < j < n
8 * 	nums[i] > nums[j]
9 * 
10 * The number of local inversions is the number of indices i where:
11 * 
12 * 	0 <= i < n - 1
13 * 	nums[i] > nums[i + 1]
14 * 
15 * Return true if the number of global inversions is equal to the number of local inversions.
16 *  
17 * Example 1:
18 * 
19 * Input: nums = [1,0,2]
20 * Output: true
21 * Explanation: There is 1 global inversion and 1 local inversion.
22 * 
23 * Example 2:
24 * 
25 * Input: nums = [1,2,0]
26 * Output: false
27 * Explanation: There are 2 global inversions and 1 local inversion.
28 * 
29 *  
30 * Constraints:
31 * 
32 * 	n == nums.length
33 * 	1 <= n <= 10^5
34 * 	0 <= nums[i] < n
35 * 	All the integers of nums are unique.
36 * 	nums is a permutation of all the numbers in the range [0, n - 1].
37 * 
38 */
39pub struct Solution {}
40
41// problem: https://leetcode.com/problems/global-and-local-inversions/
42// discuss: https://leetcode.com/problems/global-and-local-inversions/discuss/?currentPage=1&orderBy=most_votes&query=
43
44// submission codes start here
45
46impl Solution {
47    pub fn is_ideal_permutation(nums: Vec<i32>) -> bool {
48        false
49    }
50}
51
52// submission codes end
53
54#[cfg(test)]
55mod tests {
56    use super::*;
57
58    #[test]
59    fn test_775() {
60    }
61}
62