Distribute Elements Into Two Arrays II - Practice Coding Problems

Distribute Elements Into Two Arrays II - Problem

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.

Return the integer array result.

Input & Output

Example 1 — Basic Distribution

$ Input: nums = [2,1,3,3]

› Output: [2,3,1,3]

💡 Note: Start: arr1=[2], arr2=[1]. For nums[2]=3: count1=1 (2>3? no), count2=0 (1>3? no), so 0<1, add to arr2. For nums[3]=3: count1=1, count2=1, tie goes to smaller array (arr1). Result: arr1=[2,3], arr2=[1,3] → [2,3,1,3]

Example 2 — Equal Counts

$ Input: nums = [5,4,3,8]

› Output: [5,3,4,8]

💡 Note: Start: arr1=[5], arr2=[4]. For nums[2]=3: count1=1 (5>3), count2=1 (4>3), equal counts and equal sizes, tie goes to arr1. For nums[3]=8: count1=0, count2=0, equal counts, arr1 smaller, add to arr1.

Example 3 — Minimum Size

$ Input: nums = [1,2]

› Output: [1,2]

💡 Note: Only two elements, first goes to arr1, second to arr2. Result is concatenation: [1,2]

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Initialize

arr1 gets nums[0], arr2 gets nums[1]

Compare Counts

For each remaining element, count greater elements in both arrays

Distribute

Add to array with more greater elements, break ties by size

Key Takeaway

🎯 Key Insight: Use efficient data structures like Binary Indexed Trees to count greater elements in O(log n) time

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is efficiently counting elements greater than a given value in two dynamic arrays. The brute force approach uses linear scanning (O(n²)), while the optimal solution uses Binary Indexed Trees with coordinate compression for O(n log n) time complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Binary Indexed Tree (Fenwick Tree)	O(n log n)	O(n)	Use Binary Indexed Tree for efficient counting of greater elements
Brute Force Simulation	O(n²)	O(n)	Simulate the process by linearly counting greater elements in each array

Binary Indexed Tree (Fenwick Tree) — Algorithm Steps

Coordinate compress all values to handle large ranges
Maintain two BITs for arr1 and arr2 counts
For each element, query BIT for greater count and update accordingly

Visualization

Tap to expand

Step-by-Step Walkthrough

Coordinate Compression

Map values to smaller range [1, m]

BIT Query

Query range [val+1, m] for count > val

Update

Add element to chosen array and update BIT

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int n;
    int* tree;
} BIT;

BIT* createBIT(int n) {
    BIT* bit = (BIT*)malloc(sizeof(BIT));
    bit->n = n;
    bit->tree = (int*)calloc(n + 1, sizeof(int));
    return bit;
}

void updateBIT(BIT* bit, int i, int delta) {
    while (i <= bit->n) {
        bit->tree[i] += delta;
        i += i & (-i);
    }
}

int queryBIT(BIT* bit, int i) {
    int res = 0;
    while (i > 0) {
        res += bit->tree[i];
        i -= i & (-i);
    }
    return res;
}

int rangeQueryBIT(BIT* bit, int l, int r) {
    if (l > r) return 0;
    return queryBIT(bit, r) - queryBIT(bit, l - 1);
}

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int* solution(int* nums, int n, int* returnSize) {
    *returnSize = n;
    if (n == 0) return NULL;
    if (n <= 2) {
        int* result = (int*)malloc(n * sizeof(int));
        for (int i = 0; i < n; i++) result[i] = nums[i];
        return result;
    }
    
    // Simple coordinate compression
    int* sortedVals = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) sortedVals[i] = nums[i];
    qsort(sortedVals, n, sizeof(int), compare);
    
    int m = 1;
    for (int i = 1; i < n; i++) {
        if (sortedVals[i] != sortedVals[m-1]) {
            sortedVals[m++] = sortedVals[i];
        }
    }
    
    BIT* bit1 = createBIT(m);
    BIT* bit2 = createBIT(m);
    
    int* result = (int*)malloc(n * sizeof(int));
    int* arr1 = (int*)malloc(n * sizeof(int));
    int* arr2 = (int*)malloc(n * sizeof(int));
    int size1 = 0, size2 = 0;
    
    arr1[size1++] = nums[0];
    arr2[size2++] = nums[1];
    
    // Find coordinates and update BITs
    int coord1 = 0, coord2 = 0;
    for (int i = 0; i < m; i++) {
        if (sortedVals[i] == nums[0]) coord1 = i + 1;
        if (sortedVals[i] == nums[1]) coord2 = i + 1;
    }
    updateBIT(bit1, coord1, 1);
    updateBIT(bit2, coord2, 1);
    
    for (int i = 2; i < n; i++) {
        int val = nums[i];
        int valCoord = 0;
        for (int j = 0; j < m; j++) {
            if (sortedVals[j] == val) {
                valCoord = j + 1;
                break;
            }
        }
        
        int count1 = rangeQueryBIT(bit1, valCoord + 1, m);
        int count2 = rangeQueryBIT(bit2, valCoord + 1, m);
        
        if (count1 > count2) {
            arr1[size1++] = val;
            updateBIT(bit1, valCoord, 1);
        } else if (count2 > count1) {
            arr2[size2++] = val;
            updateBIT(bit2, valCoord, 1);
        } else if (size1 <= size2) {
            arr1[size1++] = val;
            updateBIT(bit1, valCoord, 1);
        } else {
            arr2[size2++] = val;
            updateBIT(bit2, valCoord, 1);
        }
    }
    
    for (int i = 0; i < size1; i++) result[i] = arr1[i];
    for (int i = 0; i < size2; i++) result[size1 + i] = arr2[i];
    
    free(sortedVals);
    free(bit1->tree);
    free(bit1);
    free(bit2->tree);
    free(bit2);
    free(arr1);
    free(arr2);
    
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000], n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n') {
            nums[n++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int returnSize;
    int* result = solution(nums, n, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Coordinate compression takes O(n log n), then n operations each taking O(log n) for BIT queries and updates

⚡ Linearithmic

Space Complexity

O(n)

Space for coordinate mapping and two Binary Indexed Trees

⚡ Linearithmic Space

5.8K Views

Medium Frequency

~35 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Indexed Tree (Fenwick Tree) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler