Global and Local Inversions in C++

Suppose we have some permutation A of [0, 1, ..., N - 1], where N is the length of A. Now the number of (global) inversions is the number of i < j with 0 <= i < j < N and A[i] > A[j]. And the number of local inversions is the number of i with 0 <= i < N and A[i] > A[i+1]. We have to return true if and only if the number of global inversions is equal to the number of local inversions. So if the input is like [1,0,2], then return true, as there is only one local inversion and one global inversion.

To solve this, we will follow these steps −

• maxVal := -1, n := size of A
• for i in range 0 to n – 3
  • maxVal := max of A[i] and maxVal
  • if maxVal > A[i + 2], then return false
• return true

Let us see the following implementation to get better understanding −

Example

 Live Demo

#include <bits/stdc++.h> using namespace std; class Solution {    public:    bool isIdealPermutation(vector<int>& A) {       int maxVal = -1;       int n = A.size();       for(int i = 0; i < n - 2; i++){          maxVal = max(A[i], maxVal);          if(maxVal > A[i + 2])          return false;       }       return true;    } }; main(){    vector<int> v = {1,0,2};    Solution ob;    cout << (ob.isIdealPermutation(v)); }

Input

[1,0,2]

Output

1