GlobalAndLocalInversions [source code]

public class GlobalAndLocalInversions {
static
/******************************************************************************/
class Solution {
    public boolean isIdealPermutation(int[] A) {
        for (int i = 0; i < A.length - 1; i++) {
            if (A[i] > A[i + 1]) {
                if (i - 1 >= 0 && A[i - 1] > A[i + 1])
                    return false;
                if (i + 2 < A.length && A[i + 2] < A[i])
                    return false;
            } else {
                if (i - 1 >= 0 && i + 2 < A.length && A[i - 1] > A[i + 2])
                    return false;
            }
        }
        return true;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        GlobalAndLocalInversions.Solution tester = new GlobalAndLocalInversions.Solution();
        int[][] inputs = {
            {1,0,2}, {1},
            {1,2,0}, {0},
            {2,0,3,1}, {0}, 
            {20, 0, 30, 10}, {0},
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            int[] A = inputs[2 * i];
            boolean ans = inputs[2 * i + 1][0] == 1;
            System.out.println (Printer.separator ());
            boolean output = tester.isIdealPermutation (A);
            System.out.printf ("[%s] -> %s, expected: %b\n", 
                Printer.array (A), Printer.wrapColor (output + "", output == ans ? "green" : "red"), ans
            );
        }
    }
}

contest的时候做的, 速度是20ms (NA);

这个题目一开始也是以为做不出来了, 不过最后居然神奇的做出来了; 最大的收获是, 想算法的时候, 真的是笔头要动的飞快! 大胆的笔算, 总结, 猜想一个方法是否可能; 实际上, 这个算法最后写出来的时候我都是不知道怎么证明的, 但是就是AC了; 做算法题和做数学题很大的一个不同就在于, 很多时候真的就是先猜后证: 算法出来了你才去考虑是否correct;

这个题目很明显是必须要做到O(N)的; 这个题目我想的时候还是比较认真的, 首先我注意到一个问题, 所有的local都是一个global; 所以我们最后求的实际上是{inversion | global but not local}是一个空集. 那么怎么证明? 我一开始的思路是找所有距离至少是2的index pair, 然后看是否是iversion; 但是这个方法还是TLE;

最后大概想到这个思路, 在每一个相邻位置, 判断是uptick还是downtick; 如果是downtick, 那么只要证明再往左或者往右一位的数字不能太小(太大)就行了; 但是这个还不够, 后来加上一条, 在uptick的时候发现也要判断一下, 这个是被第三个test给break出来的; 当时只是大概分析了一下这个例子, 发现uptick也不是那么安全, uptick的两头也可能在任何的位置出现一个global; 这个时候就卡住了; 然后我就猜想, 这个任意长度的global, 可能是因为一个较小范围内的condition导致的, 不然你只知道一个不确定长度的, 就无法解决了; 大概画图之后, 感觉这里用的这个对uptick的逻辑判断好像可能性, 试了一下就AC了; 但是时候自己思考一下, 其实并不知道怎么证明;

后来大概想到了一个证明思路, 首先, 这个算法改写成这样:

class Solution {  
    public boolean isIdealPermutation(int[] A) {  
        for (int i = 0; i < A.length - 1; i++) {  
            if (A[i] > A[i + 1]) {  
                if (i - 1 >= 0 && A[i - 1] > A[i + 1])  
                    return false;  
                if (i + 2 < A.length) {  
                    if (A[i + 2] < A[i])  
                        return false;  
                    if (i + 3 < A.length && A[i + 3] < A[i])  
                        return false;  
                }  
            }  
        }  
        return true;  
    }  
}

这个改写是没问题的, 还是AC; 可以看到, 我们现在关键还是判断一个local; 当我们发现一个local downtick, 我们先判断想左右各走一步的端点的正确性; 然后我们还要多追加一个向右走两步的正确性; 这些都保证, 就可以保证没有global;

感觉这个算法应该是直观了很多, 但是严格的证明, 还没想好怎么写;

没有editorial;

discussion最优解, 很有意思:

@erjoalgo said in check if we can sort the array with only local inversions:

Key insights:

every local inversion is also a global inversion

so "local inversions == global inversions" can be interpreted as "there are only local inversions"

if there are only local inversions, the array will be sorted after making all local inversions

if there are inversions that are not local, the array won't be sorted after making all local inversions

class Solution(object):  
    def isIdealPermutation(self, A):  
        """  
        :type A: List[int]  
        :rtype: bool  
        """  
        N=len(A)  
        for i in xrange(1, N):  
            if A[i-1]==A[i]+1:  
                A[i], A[i-1]=A[i-1], A[i]  
            elif A[i-1]!=i-1:  
                return False  
        return True

暂时还是不理解他这个算法, 感觉他后来改了一点东西, 加了一点下面的其他解法里面提到的东西(offset最大为1);

不过他上面自己给的文字的最后两条我感觉也不好证明;

我后来把他上面这个思路去掉了那个offset1的优化, 得到这个版本:

class Solution(object):  
    def isIdealPermutation(self, A):  
        """  
        :type A: List[int]  
        :rtype: bool  
        """  
        N = len(A)  
        for i in xrange(1, N):  
            if A[i-1] > A[i]:  
                A[i], A[i-1] = A[i-1], A[i]  
                if A[i] != i:  
                    return False  
            if A[i-1] != i-1:  
                return False  
        return True

是AC的;

后来想了一个不知道是否完全正确的证明, 发帖在下面了:

@vegito2002 said in check if we can sort the array with only local inversions:

This is a nice and organized solution, and here is my attempt to prove it.

First, I think OP included another insight:
@grandyang said in My 3 lines C++ Solution:

The original order should be [0, 1, 2, 3, 4...], the number i should be on the position i. We just check the offset of each number, if the absolute value is larger than 1, means the number of global inversion must be bigger than local inversion, because a local inversion is a global inversion, but a global one may not be local.

I posted some explanation for this insight in that post. As shown in that post, this insight alone is actually enough to solve this problem.

But here, I still want to address OP's insights. I did some backing up and here is the solution that is relevant to only the four points that OP mentioned, that is, with the aforementioned 5th insight removed:
class Solution(object):  
    def isIdealPermutation(self, A):  
        """  
        :type A: List[int]  
        :rtype: bool  
        """  
        N = len(A)  
        for i in xrange(1, N):  
            if A[i-1] > A[i]:  
                A[i], A[i-1] = A[i-1], A[i]  
                if A[i] != i:  
                    return False  
            if A[i-1] != i-1:  
                return False  
        return True
This algorithm goes left to right, doing swap if possible, and maintains A[0..i] as sorted.

Lemma1: If there are only local inversions, then when we do swapping left to right, each index would participate in at most one swap operation.
Proof: Suppose we have something like 2 in 2, 0, 1, which would get involved in both swaps carried out, we sure know there would not be only local inversions.
First, if x is involved in at least 2 swaps, then there has to be at least two consecutive swaps that involved x. This is obvious: once you skipped x, you can never reach it again in future iterations.
So x is involved in both of these 2 consecutive swaps starting from something like x, y, z, then we know for sure that x > y && x > z, that contradicts the assumption of local inversions only.
End of Proof

This also explains why in the code above, we can check whether i is in place immediately if a swap occurs: [i] will never participate in any further swap in a local-only array anyway and now it's position should be final already. If it's not in place, then it won't be ever.

Lemma2: If there are only local inversions, then there can't be consecutive downticks (local inversions).
Proof: that is, you can't have i s.t. A[i] > A[i + 1] > A[i + 2]. This should be obvious.
End of Proof.

Lemma3: If there are only local inversions, after the one-pass swap iteration as shown in the code, the array must be sorted.
Proof: I have to admit my proof for this is not all that clean, so take it with a grain of salt. First, according to Lemma2, we know that there will only be separate downticks: A[l_k] > A[r_k], with some k, and no r_k1 == l_k2, that is, no overlapping. So during the 1-pass, we would be able to correct every local inversion (downtick) independently. Wait, there is a problem: if you have 2,0,1, correcting the first downtick will actually create another new downtick as in 0,2,1. But if there are only local inversions, will this happen?
I claim that during the swap loop, each downtick A[l_k] > A[r_k] would be inverted back to a uptick, and such a swap would not result in a new downtick (starting at A[r_k]). If this is true, then we know that Lemma3 holds: no downticks will exist if there were only local inversions: old ones are gone, no new ones are created.
Now the rest is to prove this conclusion. Suppose that after swapping A[l_k] > A[r_k], we have a new inversion, that is: A[r_k] > A[r_k + 1], then this would contradicts with Lemma1: at next iteration, A[r_k] would participate in its second swap.
End Of Proof

I think Lemma3 is enough to explain the correctness of the algorithm.

To be honest, I am not feeling one hundred percent confident about this chain of proof. There is a vestigial feeling of mistake. But gotta start somewhere.

discussion里面好像很多人提到用merge sort来做这题, 大概搜了一下, 好像跟这个有关系: https://www.geeksforgeeks.org/counting-inversions/

discussion另外一个有意思的解法:

@lee215 said in Easy and Concise Solution [C++/Java/Python]:

All local inversions are global inversions.
If the number of global inversions is equal to the number of local inversions,
it means that all global inversions in permutations are local inversions.
It also means that we can not find A[i] > A[j] with i+2<=j.
In other words, max(A[i]) < A[i+2]

In this first solution, I traverse A and keep the current biggest number cmax.
Then I check the condition cmax < A[i+2]

这个想法很有意思, 你知道怎么证明吗? 事实上, 我们上面一句的论断是, there does not exist i + 2 <= j s.t. A[i] > A[j]. 但是我们不知道i和j到底在哪里, 他这里的一个技巧就是, 用max来处理这个位置的不确定性. 只要有任何的这样的一个i, j, 那么当我们走到j - 2的位置的时候, max[j - 2]一定比A[j]大;

我自己给的解释:

@vegito2002 said in Easy and Concise Solution [C++/Java/Python]:

@lee215 said in Easy and Concise Solution [C++/Java/Python]:

It also means that we can not find A[i] > A[j] with i+2<=j.
In other words, max(A[i]) < A[i+2]

Slight explanation for this: if there exists i + 2 <= j s.t. A[i] > A[j], then we must have max[j - 2] > A[j] because i is within 0..j-2.

总体来说这个思路真的是很聪明的;

Here come this solutions:

C++:

bool isIdealPermutation(vector<int>& A) {  
        int cmax = 0, n = A.size();  
        for (int i = 0; i < n - 2; ++i) {  
            cmax = max(cmax, A[i]);  
            if (cmax > A[i + 2]) return false;  
        }  
        return true;  
    }

Java:

public boolean isIdealPermutation(int[] A) {  
        int cmax = 0;  
        for (int i = 0; i < A.size() - 2; ++i) {  
            cmax = Math.max(cmax, A[i]);  
            if (cmax > A[i + 2]) return false;  
        }  
        return true;  
    }

Python:

def isIdealPermutation(self, A):  
        cmax = 0  
        for i in range(len(A) - 2):  
            cmax = max(cur, A[i])  
            if cmax > A[i + 2]:  
                return False  
        return True

Basic on this idea, I tried to arrange an ideal permutation. Then I found that to place number i,
I could only place i at A[i-1],A[i] or A[i+1]. So it came up to me, It will be easier just to check if all A[i] - i equals to -1, 0 or 1.

我自己给的解释:

@lee215 said in Easy and Concise Solution [C++/Java/Python]:

I could only place i at A[i-1],A[i] or A[i+1]. So it came up to me, It will be easier just to check if all A[i] - i equals to -1, 0 or 1.

Take 0, 1, 2, 3, 4, 5, 6, 7, 8 as an example, imaging where you would place 3. You can actually place it at one of [2], [3], [4]. Proof by contradiction:

If we placed it at index 0..1, then one of 0..2 would have to be in the index of 3..5, we call it x. And we also know that max[1] is 3, that means we know for sure that we have a global inversion: 3 is in index 0..1, x = 0..2 is in index 3..5, and 3 > x, their distance is at least 2.

If we place 3 at index 5..8, then there must exist one x in the range of 4..8 such that it's placed now in 0..3. By an analysis similar to the one above, we know that x = 4..8 is in index 0..3, and 3 is in index 5..8. There has to be an at-least-distance-2 inversion.

C++:
bool isIdealPermutation(vector<int>& A) {  
        for (int i = 0; i < A.size(); ++i) if (abs(A[i] - i) > 1) return false;  
        return true;  
 }
Java:
public boolean isIdealPermutation(int[] A) {  
        for (int i = 0; i < A.length; ++i) if (Math.abs(A[i] - i) > 1) return false;  
        return true;  
}
Python:
def isIdealPermutation(self, A):  
        return all(abs(i - v) <= 1 for i, v in enumerate(A))

总体来说这个人的两个方法都是观察力十足的;

另外一个跟这个很类似的算法;

@grandyang said in My 3 lines C++ Solution:

The original order should be [0, 1, 2, 3, 4...], the number i should be on the position i. We just check the offset of each number, if the absolute value is larger than 1, means the number of global inversion must be bigger than local inversion, because a local inversion is a global inversion, but a global one may not be local.

class Solution {  
public:  
    bool isIdealPermutation(vector<int>& A) {  
  for (int i = 0; i < A.size(); ++i) {  
            if (abs(A[i] - i) > 1) return false;  
        }  
  return true;  
    }  
};  

但是这个人感觉给的解释还是不够让人信服;   


---

这个是一个更加general的sort思路:   

@fb1 said in [Generalize to any integer array \(not necessarily a 0\-&gt;N permutation\)](https://discuss.leetcode.com/post/244296):  
```java

class Solution {  
    public boolean isIdealPermutation(int[] A) {  
        // Check if local inversion is enough to sort the array.  
        if (A.length <= 1) return true;  
        for (int i = 1; i < A.length; i++) {  
            if (A[i-1] > A[i]) {  
                // Swap if you see local inversions.   
                int tmp = A[i];  
                A[i] = A[i-1];  
                A[i-1] = tmp;  
                // The recently swapped element can no longer get swapped.  
                // Otherwise we would be doing global swaps.  
                i = i + 1;  
            }  
        }  

        // check if the array is sorted afterward.   
        int num = A[0];  
        for (int i = 1; i < A.length; i++) {  
            if (A[i] < num) return false;  
            num = A[i];  
        }  
        return true;  
    }  
}

注意他这里的一个核心操作是swap之后要给i一个+1操作; 所以实际上这里谈的swap并不是bubble sort或者insertion sort的时候谈论的那种sort; 比如0, 4, 1, 2, 3一个iteration的bubble swap就能sorted, 但是这个实际上是不符合题目要求的;

他这个算法的证明其实也是有点问题的, 比如2,1,0这个, 他这里的swap是eager的, 所以他最后invert的只有第一个downtick, 然后结果发现不是sorted; 那么你怎么证明如果我们swap的实际上是第二个downtick, 不会产生一个sorted的呢? 在更大的范围内, 我认为他这里其实并没有给出严谨的证明;

不对, 好像是对的? 如果有我给的这个情况, 更general的描述是, one node has downticks on both ends, 那么这种肯定最后是FALSE; 不对, 这个无法证明他的算法的正确性; 虽然我自己知道这种例子肯定是FALSE, 但是我并不知道他的这个算法一定可以return false? actually, you can. 连续的两个downtick, invert第一个, 保留第二个, 最后肯定不sorted, 所以最后肯定会return FALSE;

然后就是没有这种连续downtick的情况下的正确性了; 这个其实很好证明; 假如有i和j, 距离至少为2, 那么我们现在这种swap, 只会改变两个相邻的index之间的关系, 所以这样的swap完之后, i和j之间的inversion关系不会被改变(可能会从global变成local, 但是不会被消除).

还是不对, 看我对discussion第一个的证明, 上面;

@ashish53v said in Simple O(n) Java Solution (Linear scan) with explanation:

All local inversions are also global inversion. So if find an extra global inversion, we return false.
So if find a number which is not correctly placed i.e. if(A[i] != i)
then it is ok as long as A[i+1] = i and A[i] = i+1
But if this condition is not true
it means that either
a) i is placed at some postion j > i+1 and A[i] and A[i+1] are greater than i, i.e. A[i] > i , A[i+1] > i
b) i+1 is placed at some position j > i+1 , so A[i] > i+1 , A[i+1] = i and i+1 is at some j > i+1
so A[i] is greater than A[i+1] and A[i] > A[j]
so we get an extra global inversion so we return false;
```c++

class Solution {
public boolean isIdealPermutation(int[] A) {
int l = A.length;
if(l < 3){
return true;
}
for(int i=0;i<l-1;i++){
if(A[i] != i){
if(A[i] == i+1 && A[i+1] == i){
i++;
}else{
return false;
}
}
}
return true;
}
}


这个跟第一个解法好像是差不多的, 不过看到一个local之后, 那个Python的做法是swap回来, 而这里的做法是直接跳过就行了;   

@SkandaB said in [Simple O\(n\) Java Solution \(Linear scan\) with explanation](https://discuss.leetcode.com/post/244152):  
> @ashish53v Why are you incrementing i by 2 if both conditions are true?  

@ashish53v said in [Simple O\(n\) Java Solution \(Linear scan\) with explanation](https://discuss.leetcode.com/post/244155):  
> @SkandaB   
> Because,  
>   
> if A[i] != A[i+1],  
>  and if(A[i] == i+1 && A[i+1] == i)  
>   then it means that all the numbers from j > i+1 are greater than A[i+1] and A[i],  
> so we can not get any inversions that is why I am incrementing i, so that it skips A[i+1]  

因为假如后面有比[i]和[i+1]小的, 那么就肯定有long inversion了;   


---

submission看不见东西;   



---
### Problem Description
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.  

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.

``` Note:

A will be a permutation of [0, 1, ..., A.length - 1].
A will have length in range [1, 5000].
The time limit for this problem has been reduced.

Difficulty:Medium
Total Accepted:1.5K
Total Submissions:6K
Contributor:lokendrajain1994
Companies
amazon
Related Topics
arraymath

Hint 1
Where can the 0 be placed in an ideal permutation? What about the 1?

LC790 GlobalAndLocalInversions

GlobalAndLocalInversions [source code]

results matching ""

No results matching ""