Equal global and local inversions

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
3 upvotes
Asked in companies
AmazonOYO

Problem statement

You are given an integer array ‘ARR’ of size ‘N’ which is a permutation of the integers in the range [0, N-1].

Global inversions are defined as the number of unique pairs of the form ‘(i, j)’ where:

‘0 <= i < j < N’.
‘ARR[i] > ARR[j]’.

Local inversions are defined as the number of indexes ‘i’ where:

‘0 <= i < N - 1’.
‘ARR[i] > ARR[i + 1]’

Your task is to return ‘True’ if the number of global inversions is equal to the number of local inversions. Otherwise, return ‘False’.

Example: 
‘N = 6’
‘ARR’ = [2, 0, 1, 5, 6, 3]’   

Pair of indexes that are global inversions: ‘(0, 1)’, ‘(0, 2)’, ‘(3, 5)’, ‘(4, 5)’.
Indexes that are local inversions: ‘0’, ‘4’.
Thus, you should return ‘False’ as the answer as the number of global inversions, and the number of local inversions is not equal.
Note: 
1. All integers in ‘ARR’ are unique and ‘ARR’ is a permutation of the integers in the range [0, N - 1].
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of input contains an integer ‘T’ which denotes the number of test cases. 
Then, the ‘T’ test cases follow.

The first line of each test case contains an integer ‘N’ denoting the size of the array ‘ARR’.

The second line of each test case contains ‘N’ integers representing the array ‘ARR’.
Output format: 
For every test case, return ‘True' if the number of global inversions is equal to the number of local inversions. Otherwise, return ‘False’.

Output for every test case will be printed in a separate line.
Note: 
You do not need to print anything; it has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 100
1 <= N <= 1000

Elements of ‘ARR’ are in the range [0, N - 1].

Time limit: 1 sec

Sample input 1:

2
4
1 0 3 2 
3
1 2 0

Sample output 1:

True
False

Explanation of sample input 1:

Test Case 1:

Pair of indexes that are global inversions: ‘(0, 1)’, ‘(2, 3)’.
Indexes that are local inversions: ‘0’, ‘2’.
Thus, you should return ‘True’ as the answer as the global inversions, and the local inversions are equal. 

Test Case 2:

Pair of indexes that are global inversions: ‘(0, 2)’, ‘(1, 2)’.
Indexes that are local inversions: ‘1’.
Thus, you should return ‘False’ as the answer as the number of global inversions and the local inversions are not equal.

Sample input 2:

2
4
3 0 2 1 
3
0 1 2

Sample output 2:

False
True
Hint

Count the global and local inversions by generating all ‘(i, j)’ pairs.

Approaches (3)
Brute force

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.
Time Complexity

O(N^2), where ‘N’ is the size of array ‘ARR’.

 

The outer loop runs for ‘N’ iterations, and the inner loop runs for a total of ‘N*(N-1)/2’ iterations. Thus, the time complexity is ‘O(N^2)’.

Space Complexity

O(1).

 

Since we are not using any extra space, space complexity is constant.

Code Solution
(100% EXP penalty)
Equal global and local inversions
Full screen
Console