# Global and Local Inversions
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/global-and-local-inversions)
Canonical: https://scaleengineer.com/dsa/problems/global-and-local-inversions
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Array
---
## Problem
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]`.

# Approaches
## 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.
**Time:** 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:** O(1), as we only use a few variables to store the counts.
**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.
### Explanation
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`.

```java
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;
    }
}
```
### 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`.

## Counting with Merge Sort
The bottleneck in the brute-force approach is the O(n^2) calculation of global inversions. A standard and more efficient way to count all inversions in an array is to use a modified Merge Sort algorithm. This approach improves the time complexity from quadratic to log-linear.
**Time:** O(n log n), which is the time complexity of the merge sort algorithm for counting inversions. The O(n) scan for local inversions does not change the overall complexity. · **Space:** O(n), for the temporary array required by the merge sort algorithm.
**Pros:** Much more efficient than the brute-force approach, with O(n log n) time complexity.; It's a classic application of the divide-and-conquer paradigm.
**Cons:** Requires O(n) auxiliary space for the merge sort algorithm.; More complex to implement correctly compared to the brute-force or linear scan approaches.
### Explanation
We still begin by counting the local inversions in O(n) time, as this is already efficient. The main change is how we count global inversions. The divide-and-conquer strategy of Merge Sort is perfectly suited for this. As we merge two sorted subarrays, say `left` and `right`, if we encounter a situation where `left[i] > right[j]`, it means that `right[j]` is smaller than all the remaining elements in the `left` subarray (from index `i` onwards). This allows us to count a batch of inversions at once instead of one by one.

The total number of global inversions is the sum of inversions within the left half, inversions within the right half, and the inversions that cross between the two halves (which are counted during the merge step).

```java
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[] temp = new int[n];
        long globalInversions = countGlobalInversions(nums, temp, 0, n - 1);

        return globalInversions == localInversions;
    }

    private long mergeAndCount(int[] nums, int[] temp, int left, int mid, int right) {
        System.arraycopy(nums, left, temp, left, right - left + 1);

        int i = left;
        int j = mid + 1;
        int k = left;
        long inversions = 0;

        while (i <= mid && j <= right) {
            if (temp[i] <= temp[j]) {
                nums[k++] = temp[i++];
            } else {
                nums[k++] = temp[j++];
                inversions += (mid - i + 1);
            }
        }

        while (i <= mid) {
            nums[k++] = temp[i++];
        }

        return inversions;
    }

    private long countGlobalInversions(int[] nums, int[] temp, int left, int right) {
        long inversions = 0;
        if (left < right) {
            int mid = left + (right - left) / 2;
            inversions += countGlobalInversions(nums, temp, left, mid);
            inversions += countGlobalInversions(nums, temp, mid + 1, right);
            inversions += mergeAndCount(nums, temp, left, mid, right);
        }
        return inversions;
    }
}
```
### Algorithm
*   Calculate the number of local inversions with a simple O(n) loop and store it.
*   Create a helper function for a modified merge sort that counts global inversions.
*   The main merge sort function recursively splits the array in half.
*   The merge function merges two sorted halves and counts inversions. When an element from the right half is chosen before an element from the left half, it signifies an inversion.
*   The number of inversions is the count of elements remaining in the left half.
*   Sum up the inversions from the recursive calls and the merge step.
*   Compare the final global inversion count with the local inversion count.

## One-Pass Linear Scan
This optimal approach is based on a crucial observation: every local inversion (where `nums[i] > nums[i+1]`) is, by definition, also a global inversion. Therefore, the total number of global inversions can only equal the number of local inversions if and only if there are no other types of global inversions. These 'other' types are non-local inversions: pairs `(i, j)` where `nums[i] > nums[j]` and `j > i + 1`.

The problem thus simplifies to checking if any non-local inversion exists. If we find even one, we can immediately say the counts are not equal and return `false`. If we scan the entire array and find none, we can return `true`.
**Time:** O(n), as we iterate through the array only once. · **Space:** O(1), as we only use a few variables to track state during the single pass.
**Pros:** Extremely efficient with optimal O(n) time complexity.; Uses constant O(1) extra space.; The implementation is very short and simple.
**Cons:** The underlying logic, while simple once understood, is less direct than the brute-force approach and requires a key insight into the problem structure.
### Explanation
To efficiently check for a non-local inversion, we can iterate through the array while keeping track of the maximum value encountered so far. A non-local inversion `(k, i)` exists if `nums[k] > nums[i]` for some `k <= i - 2`. This is equivalent to saying that for some `i`, `nums[i]` is smaller than the maximum value in the prefix `nums[0...i-2]`.

We can implement this with a single loop. We maintain a variable, let's call it `max_val`, which at the beginning of the loop for index `i`, will store `max(nums[0], ..., nums[i-2])`. We start the loop at `i = 2`. In each iteration, we check if `nums[i] < max_val`. If it is, we've found our non-local inversion and return `false`. After the check, we update `max_val` by taking `max(max_val, nums[i-1])` to prepare for the next iteration. If the loop finishes, no non-local inversions were found, and we return `true`.

A remarkably simple and equivalent check is to verify if `abs(nums[i] - i) <= 1` for all `i`. Any element `nums[i]` that is more than one position away from its sorted-order index `i` will create a non-local inversion.

```java
class Solution {
    public boolean isIdealPermutation(int[] nums) {
        // The condition is equivalent to checking if for any i,
        // nums[i] < max(nums[0], nums[1], ..., nums[i-2]).
        // Or, equivalently, if |nums[i] - i| <= 1 for all i.
        
        for (int i = 0; i < nums.length; i++) {
            if (Math.abs(nums[i] - i) > 1) {
                return false;
            }
        }
        return true;
    }
}

// Alternative implementation based on the max_so_far logic:
/*
class Solution {
    public boolean isIdealPermutation(int[] nums) {
        if (nums.length <= 2) {
            return true;
        }
        int maxVal = nums[0];
        for (int i = 2; i < nums.length; i++) {
            if (nums[i] < maxVal) {
                return false;
            }
            maxVal = Math.max(maxVal, nums[i - 1]);
        }
        return true;
    }
}
*/
```
### Algorithm
*   The core idea is that for the number of global and local inversions to be equal, there must be no non-local global inversions.
*   A non-local global inversion is a pair `(k, i)` where `k <= i - 2` and `nums[k] > nums[i]`.
*   We can check for such an inversion in a single pass from left to right.
*   Initialize a variable `max_so_far` to track the maximum value seen in `nums[0...k]`.
*   Iterate with `i` from `2` to `n-1`.
*   Before checking `nums[i]`, `max_so_far` should hold `max(nums[0], ..., nums[i-2])`.
*   If `nums[i] < max_so_far`, we have found a non-local inversion, so we can immediately return `false`.
*   After the check, update `max_so_far` to include `nums[i-1]` for the next iteration.
*   If the loop completes without returning `false`, it means no non-local inversions exist, so we return `true`.

# Solutions
### Java

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

```

### Python

```python
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

```

### CPP

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

```