Taro Logo

Distribute Elements Into Two Arrays II

#6 Most AskedHard
4 views
Topics:
ArraysTrees

You are given a 1-indexed array of integers nums of length n.

We define a function greaterCount such that greaterCount(arr, val) returns the number of elements in arr that are strictly greater than val.

You need to distribute all the elements of nums between two arrays arr1 and arr2 using n operations. In the first operation, append nums[1] to arr1. In the second operation, append nums[2] to arr2. Afterwards, in the ith operation:

  • If greaterCount(arr1, nums[i]) > greaterCount(arr2, nums[i]), append nums[i] to arr1.
  • If greaterCount(arr1, nums[i]) < greaterCount(arr2, nums[i]), append nums[i] to arr2.
  • If greaterCount(arr1, nums[i]) == greaterCount(arr2, nums[i]), append nums[i] to the array with a lesser number of elements.
  • If there is still a tie, append nums[i] to arr1.

The array result is formed by concatenating the arrays arr1 and arr2. For example, if arr1 == [1,2,3] and arr2 == [4,5,6], then result = [1,2,3,4,5,6].

Return the integer array result.

Example 1:

Input: nums = [2,1,3,3]
Output: [2,3,1,3]
Explanation: After the first 2 operations, arr1 = [2] and arr2 = [1].
In the 3rd operation, the number of elements greater than 3 is zero in both arrays. Also, the lengths are equal, hence, append nums[3] to arr1.
In the 4th operation, the number of elements greater than 3 is zero in both arrays. As the length of arr2 is lesser, hence, append nums[4] to arr2.
After 4 operations, arr1 = [2,3] and arr2 = [1,3].
Hence, the array result formed by concatenation is [2,3,1,3].

Example 2:

Input: nums = [5,14,3,1,2]
Output: [5,3,1,2,14]
Explanation: After the first 2 operations, arr1 = [5] and arr2 = [14].
In the 3rd operation, the number of elements greater than 3 is one in both arrays. Also, the lengths are equal, hence, append nums[3] to arr1.
In the 4th operation, the number of elements greater than 1 is greater in arr1 than arr2 (2 > 1). Hence, append nums[4] to arr1.
In the 5th operation, the number of elements greater than 2 is greater in arr1 than arr2 (2 > 1). Hence, append nums[5] to arr1.
After 5 operations, arr1 = [5,3,1,2] and arr2 = [14].
Hence, the array result formed by concatenation is [5,3,1,2,14].

Example 3:

Input: nums = [3,3,3,3]
Output: [3,3,3,3]
Explanation: At the end of 4 operations, arr1 = [3,3] and arr2 = [3,3].
Hence, the array result formed by concatenation is [3,3,3,3].

Constraints:

  • 3 <= n <= 105
  • 1 <= nums[i] <= 109

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:

  1. Are the first value placed in the first group and the second value placed in the second group before any comparison?
  2. Does strictly greater mean that equal values do not count for either group?
  3. When the greater counts match and the groups have the same length, does the value always go to the first group?
  4. Should the returned sequence be the first group followed by the second, with each group's own order preserved?
  5. Can duplicate values appear, and should they still be placed by the same greater-count rules?

Brute Force Solution

Approach

The first value starts the first group and the second value starts the second group. Each later value is appended to the group that already contains more strictly larger values, using length and then the first group to break ties. The answer is the first group followed by the second.

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

  1. If the input has two or fewer values, return it unchanged.
  2. Place the first value in the first group and the second value in the second group.
  3. For each remaining value, count how many entries already in the first group are strictly larger.
  4. Count the strictly larger entries in the second group the same way.
  5. Append the value to the group with the larger count.
  6. If the counts are equal, append it to the shorter group, and if the lengths are also equal, append it to the first group.
  7. Join the first group and the second group and return that sequence.

Code Implementation

class Solution:
    def resultArray(self, nums: list[int]) -> list[int]:
        if len(nums) <= 2:
            return nums

        first_array = [nums[0]]
        second_array = [nums[1]]

        for index in range(2, len(nums)):
            current_number = nums[index]

            count_greater_in_first = 0
            for element_in_first in first_array:
                if element_in_first > current_number:
                    count_greater_in_first += 1
            
            count_greater_in_second = 0
            for element_in_second in second_array:
                if element_in_second > current_number:
                    count_greater_in_second += 1

            # This decision logic determines which array receives the current number based on the counts.
            if count_greater_in_first > count_greater_in_second:
                first_array.append(current_number)
            elif count_greater_in_second > count_greater_in_first:
                second_array.append(current_number)
            else:
                # A tie in counts requires a secondary check based on array sizes.
                if len(first_array) <= len(second_array):
                    # This tie-breaking rule ensures predictability when counts and sizes are equal.
                    first_array.append(current_number)
                else:
                    second_array.append(current_number)
        
        # The final result is formed by concatenating the two arrays as per the problem statement.
        return first_array + second_array

Big(O) Analysis

Time Complexity
O(n^2) – Let n be the number of values. Each new value scans every value already placed, and the two groups together hold every earlier value. The scan lengths are one, then two, and so on up to n. Those lengths form a triangular series, which is O(n^2). Joining the groups copies each value once and does not change the bound, so the total time is O(n^2).
Space Complexity
O(n) – The two groups together store every input value. The joined answer is another sequence of the same length. No search structure is built beyond those groups. The extra memory therefore grows in proportion to the input. The space is O(n).

Optimal Solution

Approach

Values are replaced by their order among the distinct values so each group can answer a greater-count with a prefix tree. The placement rule is unchanged: the larger greater-count wins, then the shorter group, then the first group. After every value is placed, the first group is followed by the second.

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

  1. Give each distinct value a rank equal to its place among the sorted distinct values, starting at one.
  2. Place the first value in the first group and the second value in the second group, and record both ranks in their prefix trees.
  3. For each later value, ask each tree how many stored ranks are less than or equal to this value's rank.
  4. Subtract those counts from the group lengths to get how many stored values are strictly greater.
  5. Append the value to the group with the larger greater-count and record its rank in that group's tree.
  6. If the greater counts match, choose the shorter group, and if the lengths also match, choose the first group.
  7. Return the first group followed by the second group.

Code Implementation

class FenwickTree:
    def __init__(self, size):
        self.tree = [0] * (size + 1)

    def update(self, index, delta):
        while index < len(self.tree):
            self.tree[index] += delta
            index += index & -index

    def query(self, index):
        current_sum = 0
        while index > 0:
            current_sum += self.tree[index]
            index -= index & -index
        return current_sum

class Solution:
    def resultArray(self, nums: list[int]) -> list[int]:
        unique_sorted_nums = sorted(list(set(nums)))
        value_to_rank_mapping = {value: index + 1 for index, value in enumerate(unique_sorted_nums)}

        group_one = [nums[0]]
        group_two = [nums[1]]
        tree_size = len(unique_sorted_nums)
        fenwick_tree_one = FenwickTree(tree_size)
        fenwick_tree_two = FenwickTree(tree_size)

        fenwick_tree_one.update(value_to_rank_mapping[nums[0]], 1)
        fenwick_tree_two.update(value_to_rank_mapping[nums[1]], 1)

        for index in range(2, len(nums)):
            current_number = nums[index]
            rank = value_to_rank_mapping[current_number]

            # This finds how many elements are smaller or equal by querying the Fenwick tree up to the rank.
            count_smaller_equal_one = fenwick_tree_one.query(rank)
            count_smaller_equal_two = fenwick_tree_two.query(rank)

            # The number of greater elements is the total size minus the count of smaller or equal ones.
            count_greater_one = len(group_one) - count_smaller_equal_one
            count_greater_two = len(group_two) - count_smaller_equal_two

            # The decision logic directs the element based on greater counts, falling back to group size.
            if count_greater_one > count_greater_two:
                group_one.append(current_number)
                fenwick_tree_one.update(rank, 1)
            elif count_greater_two > count_greater_one:
                group_two.append(current_number)
                fenwick_tree_two.update(rank, 1)
            else:
                if len(group_one) <= len(group_two):
                    group_one.append(current_number)
                    fenwick_tree_one.update(rank, 1)
                else:
                    group_two.append(current_number)
                    fenwick_tree_two.update(rank, 1)
        
        # Combine the two groups to form the final resulting array as per the problem statement.
        return group_one + group_two

Big(O) Analysis

Time Complexity
O(n log n) – Let n be the number of values. Sorting the distinct values takes O(n log n). Each remaining value performs a constant number of prefix queries and one update. Each query or update walks a path whose length is logarithmic in the number of distinct values, which is at most n. The placement work is therefore O(n log n) as well, so the total time is O(n log n).
Space Complexity
O(n) – The rank table, both prefix trees, and both groups each store at most one entry per input value. The trees are sized to the number of distinct values, which cannot exceed n. The joined answer has length n. The extra space is O(n).

Edge Cases

The input has only two values
How to Handle:
The direct scan returns those values unchanged, and the fast version places one in each group and joins the groups.
Every value is equal
How to Handle:
Both greater counts stay at zero, so each value goes to the shorter group, and a length tie goes to the first group.
One group contains more strictly larger values
How to Handle:
The new value is appended to that group.
The greater counts match but one group is shorter
How to Handle:
The value is appended to the shorter group.
The greater counts match and the lengths match
How to Handle:
The value is appended to the first group.
0/32 completed