Global and Local Inversions

MEDIUM

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 < 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 <= 10⁵
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].

Approaches

Checkout 3 different approaches to solve Global and Local Inversions. Click on different approaches to view the approach and algorithm in detail.

Brute Force Comparison

This approach directly translates the problem's definitions into code. It involves two separate counting processes: one for local inversions and one for global inversions. After counting both, it compares them to get the result.

Algorithm

Initialize local_inversions = 0 and global_inversions = 0.
Iterate through the array from i = 0 to n-2 to count local inversions:
- If nums[i] > nums[i+1], increment local_inversions.
Use a nested loop to count global inversions:
- The outer loop runs from i = 0 to n-1.
- The inner loop runs from j = i+1 to n-1.
- If nums[i] > nums[j], increment global_inversions.
Return true if local_inversions == global_inversions, otherwise return false.

First, we calculate the number of local inversions. A single loop from the beginning to the second-to-last element is sufficient. Inside the loop, we check if nums[i] > nums[i+1]. If it is, we increment a local_inversions counter.

Next, we calculate the number of global inversions. This requires checking every possible pair of indices (i, j) where i < j. A nested loop structure is a natural fit for this. The outer loop iterates i from 0 to n-1, and the inner loop iterates j from i+1 to n-1. Inside the inner loop, we check if nums[i] > nums[j] and increment a global_inversions counter if the condition is true.

Finally, we compare the two counts. If they are equal, we return true; otherwise, we return false.

class Solution {
    public boolean isIdealPermutation(int[] nums) {
        int n = nums.length;
        int localInversions = 0;
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                localInversions++;
            }
        }

        int globalInversions = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] > nums[j]) {
                    globalInversions++;
                }
            }
        }

        return globalInversions == localInversions;
    }
}

Complexity Analysis

Time Complexity: O(n^2), due to the nested loops for counting global inversions. The O(n) loop for local inversions is dominated by the quadratic part.Space Complexity: O(1), as we only use a few variables to store the counts.

Pros and Cons

Pros:

Very simple to understand and implement as it follows the problem definition literally.

Cons:

The time complexity is O(n^2), which is too slow for the given constraints (n up to 10^5) and will likely result in a 'Time Limit Exceeded' error.

Code Solutions

Checking out 3 solutions in different languages for Global and Local Inversions. Click on different languages to view the code.

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;
  }
}

Video Solution

Watch the video walkthrough for Global and Local Inversions

Patterns:

Math

Data Structures:

Array