Solution: Global and Local Inversions
Tags: algorithms, javascript, java, python
Published: 2021-04-05 08:27:07

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/global-and-local-inversions/discuss/1143422).*

---

#### [Leetcode Problem #775 (*Medium*): Global and Local Inversions](https://leetcode.com/problems/global-and-local-inversions/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
We have some permutation `A` of `[0, 1, ..., N - 1]`, where `N` is the length of `A`.
>
The number of (global) inversions is the number of `i < j` with `0 <= i < j < N` and `A[i] > A[j]`.
>
The number of local inversions is the number of `i` with `0 <= i < N` and `A[i] > A[i+1]`.
>
Return `true` if and only if the number of global inversions is equal to the number of local inversions.

---

#### ***Examples:***
>
Example 1:||
|---:|---|
Input:|A = [1,0,2]
Output:|true
Explanation:|There is 1 global inversion, and 1 local inversion.
>
Example 2:||
|---:|---|
Input:|A = [1,2,0]
Output:|false
Explanation:|There are 2 global inversions, and 1 local inversion.

---

#### ***Constraints:***
>
 - `A` will be a permutation of `[0, 1, ..., A.length - 1]`.
 - `A` will have length in range `[1, 5000]`.

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

So the critical thing to understand here is that *every local inversion is also, by definition, a global inversion*. Any number that represents part of a global inversion, however, could represent more than one global inversion.

So then we should consider that the ideal version of **A** without any inversions would be one which is **strictly increasing**, which means that for all **i**, **A[i] = i**. *Any deviation from this results in an inversion*.

Also, the further **A[i]** deviates from **i**, the more global inversions are ultimately triggered. In fact, *the only possible way for the number of global inversions to be equal to the number of local inversions is if each number has a maximum deviation from ideal of only __1__, meaning that it represents only a single global inversion and a single local inversion*.

Consider the two cases:

**Case A**) A number is more than one *higher* than the ideal; for example, **i = 3**, **A[i] = 5**.

When **i** is **3**, that means we've seen **3** numbers already, yet there are **5** numbers that are less than **5**. That then means that there are **at least 2** numbers that are less than **5** that we have not yet seen, which in turn means that there are **at least 2** global inversions triggered by this one deviation.

**Case B**) A number is more than one *lower* than the ideal; for example, **i = 3**, **A[i] = 1**.

When **i** is **3**, that means we've seen **3** numbers already, yet only **1** number is less than **1**. That then means that **at least 2** of the numbers we've seen are higher than **1**, which in turn means that we've already triggered **at least 2** gobal inversions because of this one deviation.

Any move to offset these extra global inversions with additional local inversions would only trigger at least as many more global inversions.

So if we iterate through **A** and find any number that deviates more than **1** from its ideal, we can immediately **return false**. If we reach the end without triggering this, we can **return true**.

---

#### ***Implementation:***

This code is very basic in all languages.

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
var isIdealPermutation = function(A) {
    for (let i = 0; i < A.length; i++)
        if (i - A[i] > 1 || i - A[i] < -1) return false
    return true
};
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def isIdealPermutation(self, A: List[int]) -> bool:
        for i in range(len(A)):
            if i - A[i] > 1 or i - A[i] < -1: return False
        return True
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class Solution {
    public boolean isIdealPermutation(int[] A) {
        for (int i = 0; i < A.length; i++)
            if (i - A[i] > 1 || i - A[i] < -1) return false;
        return true;
    }
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
public:
    bool isIdealPermutation(vector<int>& A) {
        for (int i = 0; i < A.size(); i++)
            if (i - A[i] > 1 || i - A[i] < -1) return false;
        return true;
    }
};
```