Count the Number of Inversions

Hard

Google

6 views

Topics:

Dynamic ProgrammingArrays

You are given an integer n and a 2D array requirements, where requirements[i] = [end_i, cnt_i] represents the end index and the inversion count of each requirement.

A pair of indices (i, j) from an integer array nums is called an inversion if:

i < j and nums[i] > nums[j]

Return the number of permutations perm of [0, 1, 2, ..., n - 1] such that for all requirements[i], perm[0..end_i] has exactly cnt_i inversions.

Since the answer may be very large, return it modulo 10⁹ + 7.

Example 1:

Input: n = 3, requirements = [[2,2],[0,0]]

Output: 2

Explanation:

The two permutations are:

[2, 0, 1]
- Prefix [2, 0, 1] has inversions (0, 1) and (0, 2).
- Prefix [2] has 0 inversions.
[1, 2, 0]
- Prefix [1, 2, 0] has inversions (0, 2) and (1, 2).
- Prefix [1] has 0 inversions.

Example 2:

Input: n = 3, requirements = [[2,2],[1,1],[0,0]]

Output: 1

Explanation:

The only satisfying permutation is [2, 0, 1]:

Prefix [2, 0, 1] has inversions (0, 1) and (0, 2).
Prefix [2, 0] has an inversion (0, 1).
Prefix [2] has 0 inversions.

Example 3:

Input: n = 2, requirements = [[0,0],[1,0]]

Output: 1

Explanation:

The only satisfying permutation is [0, 1]:

Prefix [0] has 0 inversions.
Prefix [0, 1] has an inversion (0, 1).

Constraints:

2 <= n <= 300
1 <= requirements.length <= n
requirements[i] = [end_i, cnt_i]
0 <= end_i <= n - 1
0 <= cnt_i <= 400
The input is generated such that there is at least one i such that end_i == n - 1.
The input is generated such that all end_i are unique.

Try coding it in LeetCode

Count the Number of Inversions

Hard

Google

6 views

Topics:

Dynamic ProgrammingArrays

You are given an integer n and a 2D array requirements, where requirements[i] = [end_i, cnt_i] represents the end index and the inversion count of each requirement.

A pair of indices (i, j) from an integer array nums is called an inversion if:

i < j and nums[i] > nums[j]

Return the number of permutations perm of [0, 1, 2, ..., n - 1] such that for all requirements[i], perm[0..end_i] has exactly cnt_i inversions.

Since the answer may be very large, return it modulo 10⁹ + 7.

Example 1:

Input: n = 3, requirements = [[2,2],[0,0]]

Output: 2

Explanation:

The two permutations are:

[2, 0, 1]
- Prefix [2, 0, 1] has inversions (0, 1) and (0, 2).
- Prefix [2] has 0 inversions.
[1, 2, 0]
- Prefix [1, 2, 0] has inversions (0, 2) and (1, 2).
- Prefix [1] has 0 inversions.

Example 2:

Input: n = 3, requirements = [[2,2],[1,1],[0,0]]

Output: 1

Explanation:

The only satisfying permutation is [2, 0, 1]:

Prefix [2, 0, 1] has inversions (0, 1) and (0, 2).
Prefix [2, 0] has an inversion (0, 1).
Prefix [2] has 0 inversions.

Example 3:

Input: n = 2, requirements = [[0,0],[1,0]]

Output: 1

Explanation:

The only satisfying permutation is [0, 1]:

Prefix [0] has 0 inversions.
Prefix [0, 1] has an inversion (0, 1).

Constraints:

2 <= n <= 300
1 <= requirements.length <= n
requirements[i] = [end_i, cnt_i]
0 <= end_i <= n - 1
0 <= cnt_i <= 400
The input is generated such that there is at least one i such that end_i == n - 1.
The input is generated such that all end_i are unique.

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 numbers in the input array?
Can the input array contain duplicate values, and if so, how should they be handled when counting inversions?
What should I return if the input array is null or empty?
Is the input array guaranteed to be an array of integers, or could it contain other data types?
Can you define more precisely what constitutes an 'inversion' in the case of equal numbers at different indices?

Brute Force Solution

Approach

The brute force way to count inversions is to check every possible pair of items in the list. We compare each item to all the items that come after it to see if they are out of order. If they are, we count them.

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

Take the first item in the list.
Compare it to every item that comes after it in the list.
If an item that comes later is smaller than the first item, count it as an inversion.
Move to the second item in the list.
Compare it to every item that comes after it.
If an item that comes later is smaller than the second item, count it as another inversion.
Keep doing this for each item in the list, comparing it to all the items that come after it.
Add up all the inversions you found to get the total number of inversions.

Code Implementation

def count_inversions_brute_force(number_list):
    inversion_count = 0

    list_length = len(number_list)

    for first_index in range(list_length):
        # Iterate through the list.

        for second_index in range(first_index + 1, list_length):
            # Compare the current element to all subsequent elements.

            if number_list[first_index] > number_list[second_index]:
                # If a later element is smaller, it's an inversion.

                inversion_count += 1

    return inversion_count

Big(O) Analysis

Time Complexity

O(n²) – The described algorithm iterates through each of the n elements in the input array. For each element, it compares it with all subsequent elements to find inversions. In the worst case, each element will be compared with approximately n other elements. Therefore, the total number of comparisons will be proportional to n * n/2. This simplifies to a time complexity of O(n²).

Space Complexity

O(1) – The brute force approach iterates through the input list using nested loops. It only uses a few integer variables to store the current indices and the inversion count. The space required for these variables remains constant regardless of the size of the input list, N. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

To count inversions efficiently, we'll use a divide-and-conquer strategy. We'll break the problem into smaller, easier-to-solve subproblems, and then combine the results in a way that also counts the inversions created during the merging process.

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

Split the list of numbers into two smaller lists of roughly equal size.
Recursively apply this splitting process to each of the smaller lists until you have lists that contain only one number. A list with only one number has zero inversions.
Now, start merging the smaller lists back together. While merging, count the number of inversions. An inversion occurs when a number from the right sublist is smaller than a number from the left sublist.
When an inversion is detected during the merging step, it means all the remaining elements in the left sublist are also greater than the current element of the right sublist. So, add the count of the remaining elements in the left sublist to the total inversion count.
Continue merging the lists and counting inversions until you have merged everything back into the original list.
The final inversion count is the sum of inversions counted during each merging step.

Code Implementation

def count_inversions(number_list):
    return count_inversions_recursive(number_list, 0, len(number_list) - 1)

def count_inversions_recursive(number_list, start_index, end_index):
    inversion_count = 0

    if start_index < end_index:
        middle_index = (start_index + end_index) // 2

        # Recursively count inversions in the left and right subarrays.
        inversion_count += count_inversions_recursive(number_list, start_index, middle_index)

        inversion_count += count_inversions_recursive(number_list, middle_index + 1, end_index)

        # Merge the two sorted subarrays and count inversions during the merge.
        inversion_count += merge_and_count(number_list, start_index, middle_index, end_index)

    return inversion_count

def merge_and_count(number_list, start_index, middle_index, end_index):
    left_subarray = number_list[start_index:middle_index + 1]
    right_subarray = number_list[middle_index + 1:end_index + 1]

    left_index = 0
    right_index = 0
    merged_index = start_index
    inversion_count = 0

    # Iterate until one of the subarrays is exhausted.
    while left_index < len(left_subarray) and right_index < len(right_subarray):
        if left_subarray[left_index] <= right_subarray[right_index]:
            number_list[merged_index] = left_subarray[left_index]
            left_index += 1
        else:
            number_list[merged_index] = right_subarray[right_index]
            right_index += 1

            # Count inversions.
            # Remaining elements in left are greater than current right.
            inversion_count += (len(left_subarray) - left_index)

        merged_index += 1

    # Copy any remaining elements from the left subarray.
    while left_index < len(left_subarray):
        number_list[merged_index] = left_subarray[left_index]
        left_index += 1
        merged_index += 1

    # Copy any remaining elements from the right subarray.
    while right_index < len(right_subarray):
        number_list[merged_index] = right_subarray[right_index]
        right_index += 1
        merged_index += 1

    return inversion_count

Big(O) Analysis

Time Complexity

O(n log n) – The algorithm employs a divide-and-conquer approach, recursively splitting the input array of size n into two halves until each sub-array contains only one element. This division process takes O(log n) steps. The merging process, which also counts the inversions, iterates through each element of the array in each merge step, resulting in O(n) operations per merge. Since merging happens at each level of the recursion (log n levels), the total time complexity is O(n log n).

Space Complexity

O(N) – The dominant factor in auxiliary space is the temporary lists created during the merging steps. In the merging process, temporary storage is required to hold the merged sorted sub-arrays. At each level of recursion, at most N elements will need to be copied to temporary arrays. Since the input array may be overwritten during the sorting and merging process, this represents extra memory usage. Therefore, the auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 since an empty array has no inversions.
Array with one element	Return 0 since a single element cannot form an inversion.
Array with two elements, sorted	Return 0 as there is no inversion.
Array with two elements, unsorted	Return 1, representing the single inversion.
Array with all elements identical	Return 0 since there are no inversions.
Array with already reverse sorted elements	Expect a high number of inversions equal to n*(n-1)/2.
Large input array exceeding memory limitations during merge sort	Consider using an in-place merge sort (though less efficient) or reporting an error if memory limits are hit.
Integer overflow if the number of inversions is very large	Use a 64-bit integer type (long in Java, long long in C++) to store the inversion count to prevent overflow.