Leetcode 775. Global and Local Inversions

Problem Explanation

Given an array, where N is the length of the array and the elements present are the numbers from 0 to N - 1 (i.e., a permutation of these numbers), we have to find if the number of global inversions is equal to the number of local inversions.

An inversion in an array is a pair of elements where the larger element comes before the smaller one.

• A global inversion is an inversion where the larger element is at index i and the smaller element is at index j such that 0 <= i < j < N and A[i] > A[j].
• A local inversion is a special case of global inversions where the larger element is at index i and the smaller element is at index i+1.

The task is to return true if the number of global inversions is equal to the number of local inversions else return false.

Solution Approach:

From the above definitions, we know that all local inversions are global inversions but the vice versa is not true. So, for the permutation to be ideal (number of global inversions equal to local inversions), there must not exist a pair (A[i],A[j]) such that A[i] > A[j] and j>i+1.

The approach that is being used in the solution, is to traverse the array and for each index i, it keeps track of the maximum element so far, and checks if it is greater than A[i+2]. If so, then there exists a pair (A[i],A[j]) such that A[i] > A[j] and j>i+1, so the function returns false. If no such pair exists, the function will return true.

This approach simply uses a single pass over the array, so the time complexity is linear, and only a few variables are used to store state, so the space complexity is constant.

C++ Solution:

1
2cpp
3class Solution {
4 public:
5  bool isIdealPermutation(vector<int>& nums) {
6    int maxi = -1;  // The most likely to be greater than nums[i + 2].
7
8    for (int i = 0; i + 2 < nums.size(); ++i) {
9      maxi = max(maxi, nums[i]);
10      if (maxi > nums[i + 2])
11        return false;
12    }
13
14    return true;
15  }
16};

In the C++ solution, maxi variable is used to keep track of the maximum element so far. The program iterates over the elements of the array starting from first element to the element 2 places before the last element. For each element, the maximum so far is updated and it is checked if it is greater than the element 2 places ahead. If so, a false is returned immediately, otherwise at the end of the loop a true is returned.

To follow along the solution, let's refer to a working example:

Let's consider the following example:

A = [1,3,0,2]

Traversing through the array:

• For i = 0, maxi would be max(-1, 1) = 1 and 1 is not greater than A[2] (0).
• For i = 1, maxi would be max(1, 3) = 3 and 3 is greater than A[3] (2). So, the function will return false immediately.

Note: The solution is not available in Python, Java, JavaScript, and C#. The solution provided is only in C++.Python Solution:

1
2python
3def isIdealPermutation(nums):
4    maxi = -1
5    for i in range(len(nums) - 2):
6        maxi = max(maxi, nums[i])
7        if maxi > nums[i + 2]:
8            return False
9    return True

In Python, similar to the C++ solution, we iterate over the elements of the array up to two indices before the end of the list, updating maxi and checking if it is greater than the value at index i + 2.

Java Solution:

1
2java
3public class Solution {
4    public boolean isIdealPermutation(int[] A) {
5        int maxi = -1;
6        for (int i = 0; i + 2 < A.length; ++i) {
7            maxi = Math.max(maxi, A[i]);
8            if (maxi > A[i + 2])
9                return false;
10        }
11        return true;
12    }
13}

In the Java solution, the approach is identical to the previous ones. We use a for loop to traverse the array and the Math.max function to find the maximum so far.

JavaScript Solution:

1
2javascript
3var isIdealPermutation = function(A) {
4    let maxi = -1;
5    for (let i = 0; i + 2 < A.length; ++i) {
6        maxi = Math.max(maxi, A[i]);
7        if (maxi > A[i + 2])
8            return false;
9    }
10    return true;
11};

The JavaScript solution is very similar to the other language solutions. It uses the Math.max function to find the maximum value between maxi and A[i] and then checks whether maxi is greater than A[i+2]. If so, it returns false.

All these solutions have a time complexity of O(n) where n is the length of the given array because we are doing a single pass over the given array. The space complexity is O(1) since we are only using a few variables.