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:
greaterCount(arr1, nums[i]) > greaterCount(arr2, nums[i]), append nums[i] to arr1.greaterCount(arr1, nums[i]) < greaterCount(arr2, nums[i]), append nums[i] to arr2.greaterCount(arr1, nums[i]) == greaterCount(arr2, nums[i]), append nums[i] to the array with a lesser number of elements.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 <= 1051 <= nums[i] <= 109When 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:
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:
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_arrayValues 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:
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| Case | How to Handle |
|---|---|
| The input has only two values | The direct scan returns those values unchanged, and the fast version places one in each group and joins the groups. |
| Every value is equal | 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 | The new value is appended to that group. |
| The greater counts match but one group is shorter | The value is appended to the shorter group. |
| The greater counts match and the lengths match | The value is appended to the first group. |