Equal global and local inversions

A simple approach would be to use two nested loops to count the number of global inversions and a single loop to count the number of local inversions.

Algorithm:

• Set ‘GLOBALINV' = 0 and ‘LOCALINV' = 0. To count the global and local inversions.
• Run a loop where ‘i’ ranges from ‘0’ to ‘N - 2’:
  • If ‘ARR[i] > ARR[i + 1]’, then index ‘i’ is a local inversion:
    • ‘LOCALINV' += 1.
  • Run a loop where ‘j’ ranges from ‘i + 1’ to ‘N - 1’:
    • If ‘ARR[i] > ARR[j]’, then the pair of indexes ‘(i, j)’ is a global inversion:
      • ‘GLOBALINV' += 1.
• If ‘GLOBALINV’ is equal to ‘LOCALINV’, then:
  • Return ‘True’ as the answer.
• Return ‘False’ as the answer.

Observe that all the local inversions are also global inversions. So, we can greedily check if there exists at least one global inversion that is not a local inversion. In such a scenario, the local inversions will never be equal to global inversions.

Store the maximum value in ‘ARR’ up to ‘i’ (including ‘i’), let’s say 'CUR_MAX'. If 'CUR_MAX' is greater than ‘ARR[i + 2]’ (as ‘i + 1’ is a local inversion), then there exists at least one global inversion, which is not a local inversion. If 'CUR_MAX' is smaller than ‘ARR[i + 2]’, then all the values before ‘i + 1’ are also smaller, so we will always find that extra global inversion if it exists.

Algorithm:

• Set 'CUR_MAX'. Use it to store the maximum value up to the current index.
• Run a loop where ‘i’ ranges from ‘0’ to ‘N - 3’:
  • ‘CUR_MAX = max(CUR_MAX, ARR[i])’. Update 'CUR_MAX'.
  • If ‘CUR_MAX > ARR[i + 2]’, then there is an extra global inversion:
    • Return ‘False’ as the answer.
• Return ‘True’ as the answer.

We stated in the previous approach: “If there is at least one global inversion that is not a local inversion, then the total global inversions will never be equal to the local inversions”. Also, any index can have at most one local inversion. So, if we find an index that is part of more than one global inversion, we should return ‘False’ as the answer.

Consider ‘ARR = [0, 1, 2, 3, 4, 5, 6]’, i.e., in sorted order. We try to place the integer ‘3’ at different locations:

• Shift ‘3’ to the left by one position,
  • ‘ARR = [0, 1, 3, 2, 4, 5, 6]’
  • If we fix the position of ‘3’ and no matter how we rearrange the other integers, there will always be an integer between index [3, 6] that is smaller than ‘3’. Thus, ‘3’ will always have at least one global inversion.
• Shift ‘3’ to the left by two positions,
  • ‘ARR = [0, 3, 1, 2, 4, 5, 6]’
  • Similarly, no matter what positions the other integers have, there will always be two integers between index [2, 6] that will be smaller than ‘3’. Thus, ‘3’ will always have at least two global inversions.

We can generalize these for the right shifts. Let’s ‘DIST[i]’ be the distance of ‘ARR[i]’ from its position in the sorted order. So, for every ‘i’, ‘ARR[i]’ will be part of at least ‘DIST[i]’ global inversions.

As per the question, the array ‘ARR’ is a permutation of the integers from ‘[0, N - 1]’. So, the position of ‘ARR[i]’ in sorted order is ‘ARR[i]’. 

We have ‘DIST[i] = abs(ARR[i] - i)’, where ‘abs(X)’ is the absolute value of 'X'.

As per our previous analysis, if ‘DIST[i] > 1’, we should return ‘False’. Also, if for every ‘i’ we have ‘DIST[i] <= 1’, then no integer has moved more than one distance from its sorted position, so every inversion has to be a local inversion.

Algorithm:

• Run a loop where ‘i’ ranges from ‘0’ to ‘N - 2’:
  • If ‘abs(ARR[i] - i) > 1’, then there is at least one extra global inversion:
    • Return ‘False’ as the answer.
• Return ‘True’ as the answer.