Skip to main content
Back to problems
#775
Medium Algorithms

Global and local inversions

Array Math
42.7% acceptance
Feb 21, 2026
1875
382
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.

Solution

Rust
Time O(n)
Space O(1)
LeetCode
solution.rs
/*
 * 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.
 * 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].
 */
impl Solution {
  pub fn is_ideal_permutation(nums: Vec<i32>) -> bool {
    nums.iter().enumerate().all(|(i, &v)| (v - i as i32).abs() <= 1)
  }
}