LeetCode 3072 - Distribute Elements Into Two Arrays II

Difficulty: 🔴 Hard
Topics: Array, Binary Indexed Tree, Segment Tree, Simulation

Solution

Problem Understanding

This problem requires simulating the distribution of elements from a 1-indexed array nums into two separate arrays arr1 and arr2 under specific rules. Each element in nums is assigned sequentially to one of the arrays according to a comparison of how many elements in each array are strictly greater than the current element. If the counts are equal, the element is appended to the array with fewer elements, and if there is still a tie, arr1 is chosen by default.

The input is a 1-indexed array nums of length n where each value is an integer between 1 and 10^9. The output is the concatenation of arr1 and arr2 after processing all elements. The key challenge is that directly counting the elements greater than the current number in both arrays on each step is computationally expensive, especially because n can be up to 100,000. This necessitates an optimized solution using a data structure that supports efficient "count greater than" queries.

Edge cases to consider include all elements being equal, strictly increasing or decreasing sequences, and alternating large and small numbers which could stress the "greaterCount" logic.

Approaches

Brute Force

The brute-force approach iterates over nums and for each element, counts the number of elements greater than it in arr1 and arr2. Then it applies the rules to append the element to the appropriate array. This approach is correct because it directly implements the problem's rules. However, counting greater elements in arrays repeatedly results in O(n^2) time complexity, which is too slow for n = 10^5.

Optimized Approach

The key observation is that we only need to perform greater-than counts efficiently. Using a Binary Indexed Tree (Fenwick Tree) or a Segment Tree over a compressed value space allows us to answer these queries in O(log n) time. First, we normalize the array values to a 1-based index for the tree. Each array maintains a separate tree for counting occurrences of values. For each number, we compute the number of elements greater than it as total_elements - prefix_sum(value). This reduces the time complexity to O(n log n).

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(n)	Direct simulation with repeated greater count checks
Optimal	O(n log n)	O(n)	Uses Binary Indexed Tree for efficient greater-count queries

Algorithm Walkthrough

Normalize values: Compress the values in nums to a 1-based ranking to keep the tree size manageable.
Initialize: Create two Binary Indexed Trees (BITs) bit1 and bit2 to track occurrences in arr1 and arr2.
Process first two elements: Append nums[1] to arr1 and nums[2] to arr2, and update the trees accordingly.
Iterate over remaining elements: For each element nums[i] from 3 to n:
Query greaterCount for both arrays using the BITs: count1 = total1 - bit1.prefix_sum(rank) and count2 = total2 - bit2.prefix_sum(rank).
Apply rules:

If count1 > count2, append to arr1.
If count1 < count2, append to arr2.
If equal, append to the smaller array, and if still equal, append to arr1.

Update the corresponding BIT with the new value.
Concatenate: Return the concatenation of arr1 and arr2.

Why it works: Using BITs ensures that the number of elements greater than any given value can be queried efficiently in O(log n) per operation. This preserves the problem's simulation semantics while remaining performant.

Python Solution

from typing import List
from bisect import bisect_left

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

    def update(self, index: int, value: int):
        while index <= self.size:
            self.tree[index] += value
            index += index & -index

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

class Solution:
    def resultArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        sorted_unique = sorted(set(nums))
        rank_map = {num: i+1 for i, num in enumerate(sorted_unique)}
        max_rank = len(sorted_unique)
        
        bit1 = BIT(max_rank)
        bit2 = BIT(max_rank)
        arr1, arr2 = [], []

        for i, num in enumerate(nums):
            r = rank_map[num]
            if i == 0:
                arr1.append(num)
                bit1.update(r, 1)
            elif i == 1:
                arr2.append(num)
                bit2.update(r, 1)
            else:
                total1 = len(arr1)
                total2 = len(arr2)
                greater1 = total1 - bit1.query(r)
                greater2 = total2 - bit2.query(r)
                
                if greater1 > greater2:
                    arr1.append(num)
                    bit1.update(r, 1)
                elif greater1 < greater2:
                    arr2.append(num)
                    bit2.update(r, 1)
                else:
                    if total1 <= total2:
                        arr1.append(num)
                        bit1.update(r, 1)
                    else:
                        arr2.append(num)
                        bit2.update(r, 1)

        return arr1 + arr2

This Python implementation first compresses nums for efficient BIT usage. The BIT class supports update and query operations. For each element, we compute the number of elements strictly greater in both arrays using total - prefix_sum logic, then apply the distribution rules.

Go Solution

package main

func resultArray(nums []int) []int {
    n := len(nums)
    sorted := make([]int, n)
    copy(sorted, nums)
    sort.Ints(sorted)
    
    rankMap := make(map[int]int)
    rank := 1
    for _, num := range sorted {
        if _, exists := rankMap[num]; !exists {
            rankMap[num] = rank
            rank++
        }
    }

    bit1 := make([]int, rank+1)
    bit2 := make([]int, rank+1)

    update := func(bit []int, idx int, val int) {
        for idx < len(bit) {
            bit[idx] += val
            idx += idx & -idx
        }
    }

    query := func(bit []int, idx int) int {
        sum := 0
        for idx > 0 {
            sum += bit[idx]
            idx -= idx & -idx
        }
        return sum
    }

    arr1, arr2 := []int{}, []int{}

    for i, num := range nums {
        r := rankMap[num]
        if i == 0 {
            arr1 = append(arr1, num)
            update(bit1, r, 1)
        } else if i == 1 {
            arr2 = append(arr2, num)
            update(bit2, r, 1)
        } else {
            total1 := len(arr1)
            total2 := len(arr2)
            greater1 := total1 - query(bit1, r)
            greater2 := total2 - query(bit2, r)
            if greater1 > greater2 {
                arr1 = append(arr1, num)
                update(bit1, r, 1)
            } else if greater1 < greater2 {
                arr2 = append(arr2, num)
                update(bit2, r, 1)
            } else {
                if total1 <= total2 {
                    arr1 = append(arr1, num)
                    update(bit1, r, 1)
                } else {
                    arr2 = append(arr2, num)
                    update(bit2, r, 1)
                }
            }
        }
    }

    return append(arr1, arr2...)
}

The Go implementation mirrors the Python approach, using slices for BIT storage. Sorting and ranking compress the values, and the update and query functions provide O(log n) operations for greater-count queries.

Worked Examples

Example 1: nums = [2,1,3,3]

i	num	arr1	arr2	greater1	greater2	Chosen Array
1	2	[2]	[]	-	-	arr1
2	1	[2]	[1]	-	-	arr2
3	3	[2]	[1]	0	0	arr1
4	3	[2,3]	[1]	0	0	arr2

Result: [2,3,1,3]