Jobs

Interviews

Discussions

Global and Local Inversions

Medium

Asked by:

2 views

Topics:

Arrays

You are given an integer array nums of length n which represents a permutation of all the integers in the range [0, n - 1].

The number of global inversions is the number of the different pairs (i, j) where:

0 <= i < j < n
nums[i] > nums[j]

The number of local inversions is the number of indices i where:

0 <= i < n - 1
nums[i] > nums[i + 1]

Return true if the number of global inversions is equal to the number of local inversions.

Example 1:

Input: nums = [1,0,2]
Output: true
Explanation: There is 1 global inversion and 1 local inversion.

Example 2:

Input: nums = [1,2,0]
Output: false
Explanation: There are 2 global inversions and 1 local inversion.

Constraints:

n == nums.length
1 <= n <= 10⁵
0 <= nums[i] < n
All the integers of nums are unique.
nums is a permutation of all the numbers in the range [0, n - 1].

Try coding it in LeetCode

Global and Local Inversions

Medium

Asked by:

2 views

Topics:

Arrays

You are given an integer array nums of length n which represents a permutation of all the integers in the range [0, n - 1].

The number of global inversions is the number of the different pairs (i, j) where:

0 <= i < j < n
nums[i] > nums[j]

The number of local inversions is the number of indices i where:

0 <= i < n - 1
nums[i] > nums[i + 1]

Return true if the number of global inversions is equal to the number of local inversions.

Example 1:

Input: nums = [1,0,2]
Output: true
Explanation: There is 1 global inversion and 1 local inversion.

Example 2:

Input: nums = [1,2,0]
Output: false
Explanation: There are 2 global inversions and 1 local inversion.

Constraints:

n == nums.length
1 <= n <= 10⁵
0 <= nums[i] < n
All the integers of nums are unique.
nums is a permutation of all the numbers in the range [0, n - 1].

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers within the input array?
Can the input array be empty, or can it contain only one element?
Are duplicate numbers allowed in the input array, and if so, how should they be handled when determining inversions?
Could you define more precisely what constitutes a 'global' versus a 'local' inversion, especially concerning edge cases at the beginning and end of the array?
Is it possible for the array to be very large, and should I optimize for space complexity as well as time complexity (within reason, of course)?
Can you please give a couple of examples of an array with and without global/local inversions to fully understand your definitions?
If the number of global and local inversions is the same, should I return `true` or `false`?
Is the input array guaranteed to be valid? Should I validate the input?
Are we concerned about integer overflow during calculations of inversion counts?
What data type is the input array? Is it an `ArrayList`?

Brute Force Solution

Approach

The brute force method is the simplest way to check if two types of unusual orderings are the same. We will directly count how many times each type of unusual ordering occurs and then compare those counts to each other to verify they're equal.

Here's how the algorithm would work step-by-step:

First, we need to figure out how many 'unusual orderings' exist in the standard order, specifically the 'close by' unusual orderings.
We can do this by comparing each number with the one directly next to it. If the number is bigger than the next one, we count that as one 'close by' unusual ordering.
Next, we need to find out how many 'unusual orderings' there are in total, not just the 'close by' ones.
To do this, we compare each number with every number that comes after it. Every time a number is bigger than a number that comes later, we count that as an 'unusual ordering'.
Finally, if the number of 'close by' unusual orderings is the same as the total number of 'unusual orderings', then the answer is yes. Otherwise, it's no.

Code Implementation

def global_and_local_inversions_brute_force(numbers):
    local_inversion_count = 0

    # Count local inversions (adjacent inversions).
    for index in range(len(numbers) - 1):
        if numbers[index] > numbers[index + 1]:

            # Local inversion found. Increment the counter.
            local_inversion_count += 1

    global_inversion_count = 0

    # Count global inversions (all inversions).
    for first_index in range(len(numbers)):
        for second_index in range(first_index + 1, len(numbers)):

            # Comparing each number to every number after it.
            if numbers[first_index] > numbers[second_index]:

                # Increment global inversion count.
                global_inversion_count += 1

    # Determining if local and global inversions are equal.
    return local_inversion_count == global_inversion_count

Big(O) Analysis

Time Complexity

O(n²) – The algorithm calculates the number of local inversions by iterating through the array of size n, comparing adjacent elements, resulting in O(n) complexity. Then, the algorithm calculates the number of global inversions by comparing each element with every element that follows it. This requires nested loops, where the outer loop iterates n times and the inner loop iterates up to n times. The total number of comparisons approximates n * n/2, which simplifies to O(n²).

Space Complexity

O(1) – The provided solution calculates the number of local and global inversions by iterating through the input array and maintaining counts. No additional data structures like arrays, hash maps, or recursion are employed. Only a few integer variables are used to store the counts and loop indices, and the number of these variables is independent of the input size N. Therefore, the auxiliary space complexity is constant, O(1).

Optimal Solution

Approach

The key insight is that a global inversion is always a local inversion. So, to determine if the number of global inversions is equal to the number of local inversions, we only need to check if there is a global inversion that is *not* a local inversion. If we find one, we know the counts are different.

Here's how the algorithm would work step-by-step:

Go through the numbers one by one.
For each number, check if there is a number further along that is smaller than it but not right next to it. In other words, look for a global inversion that is not a local inversion.
If you find such a pair of numbers, you know the number of global inversions is different than the number of local inversions, and you can immediately say 'no, they are not equal'.
If you get through all the numbers without finding such a pair, it means all global inversions are also local inversions, and you can confidently say 'yes, they are equal'.

Code Implementation

def global_and_local_inversions(numbers) -> bool:
    list_length = len(numbers)

    for i in range(list_length): 
        # Check each number for non-local global inversions
        for j in range(i + 2, list_length):

            #Found a global inversion that is not a local inversion
            if numbers[i] > numbers[j]:
                return False

    # No non-local global inversions were found
    return True

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through the input array of size n. For each element at index i, it iterates through the remaining elements from index i+2 to n-1, searching for a global inversion that isn't a local inversion. Therefore, for each of the n elements, in the worst case, we perform a comparison with potentially n-2 other elements. Thus, the total number of operations approximates to n * (n-2), which simplifies to O(n²).

Space Complexity

O(1) – The algorithm iterates through the input array but doesn't create any auxiliary data structures like arrays, lists, or hash maps to store intermediate results. It uses a fixed number of variables (loop index, comparison variable) regardless of the input size N, where N is the number of elements in the input array. Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
Null or empty input array	Return true since an empty array trivially satisfies the condition of equal global and local inversions.
Array with only one element	Return true since there are no inversions at all.
Array with two elements in sorted order	Return true since there are no inversions.
Array with two elements in reverse order	Return true since the one global inversion is also a local inversion.
Array with many elements already sorted except for one local inversion at the end	The solution needs to correctly identify that the single local inversion at the end results in only one global inversion as well.
Array with elements in strictly decreasing order	This worst case must be handled carefully as every adjacent pair constitutes a global inversion, so it has to be checked if all global inversions are local.
Array with all identical elements	Return true as there are no global or local inversions.
Integer overflow during comparisons with large values	Use long data type to handle potential integer overflow.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers within the input array?
Can the input array be empty, or can it contain only one element?
Are duplicate numbers allowed in the input array, and if so, how should they be handled when determining inversions?
Could you define more precisely what constitutes a 'global' versus a 'local' inversion, especially concerning edge cases at the beginning and end of the array?
Is it possible for the array to be very large, and should I optimize for space complexity as well as time complexity (within reason, of course)?
Can you please give a couple of examples of an array with and without global/local inversions to fully understand your definitions?
If the number of global and local inversions is the same, should I return `true` or `false`?
Is the input array guaranteed to be valid? Should I validate the input?
Are we concerned about integer overflow during calculations of inversion counts?
What data type is the input array? Is it an `ArrayList`?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, we need to figure out how many 'unusual orderings' exist in the standard order, specifically the 'close by' unusual orderings.
We can do this by comparing each number with the one directly next to it. If the number is bigger than the next one, we count that as one 'close by' unusual ordering.
Next, we need to find out how many 'unusual orderings' there are in total, not just the 'close by' ones.
To do this, we compare each number with every number that comes after it. Every time a number is bigger than a number that comes later, we count that as an 'unusual ordering'.
Finally, if the number of 'close by' unusual orderings is the same as the total number of 'unusual orderings', then the answer is yes. Otherwise, it's no.

Code Implementation

def global_and_local_inversions_brute_force(numbers):
    local_inversion_count = 0

    # Count local inversions (adjacent inversions).
    for index in range(len(numbers) - 1):
        if numbers[index] > numbers[index + 1]:

            # Local inversion found. Increment the counter.
            local_inversion_count += 1

    global_inversion_count = 0

    # Count global inversions (all inversions).
    for first_index in range(len(numbers)):
        for second_index in range(first_index + 1, len(numbers)):

            # Comparing each number to every number after it.
            if numbers[first_index] > numbers[second_index]:

                # Increment global inversion count.
                global_inversion_count += 1

    # Determining if local and global inversions are equal.
    return local_inversion_count == global_inversion_count

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Go through the numbers one by one.
For each number, check if there is a number further along that is smaller than it but not right next to it. In other words, look for a global inversion that is not a local inversion.
If you find such a pair of numbers, you know the number of global inversions is different than the number of local inversions, and you can immediately say 'no, they are not equal'.
If you get through all the numbers without finding such a pair, it means all global inversions are also local inversions, and you can confidently say 'yes, they are equal'.

Code Implementation

def global_and_local_inversions(numbers) -> bool:
    list_length = len(numbers)

    for i in range(list_length): 
        # Check each number for non-local global inversions
        for j in range(i + 2, list_length):

            #Found a global inversion that is not a local inversion
            if numbers[i] > numbers[j]:
                return False

    # No non-local global inversions were found
    return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return true since an empty array trivially satisfies the condition of equal global and local inversions.
Array with only one element	Return true since there are no inversions at all.
Array with two elements in sorted order	Return true since there are no inversions.
Array with two elements in reverse order	Return true since the one global inversion is also a local inversion.
Array with many elements already sorted except for one local inversion at the end	The solution needs to correctly identify that the single local inversion at the end results in only one global inversion as well.
Array with elements in strictly decreasing order	This worst case must be handled carefully as every adjacent pair constitutes a global inversion, so it has to be checked if all global inversions are local.
Array with all identical elements	Return true as there are no global or local inversions.
Integer overflow during comparisons with large values	Use long data type to handle potential integer overflow.