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. 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.

Examples

Example 1

1
2
3
4
5
6
7

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

1
2
3
4
5
6
7
8

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

1
2
3
4

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 <= 10^5
  • 1 <= nums[i] <= 10^9

Solution

Method 1 – Binary Indexed Tree (Fenwick Tree) for Efficient Greater Count

Intuition

To efficiently count the number of elements greater than a value in each array, we can use a Binary Indexed Tree (Fenwick Tree) to maintain a frequency table of inserted values. Since values can be up to 1e9, we compress the values to a smaller range using coordinate compression. For each insertion, we can query the number of elements greater than a value in O(log n) time.

Approach

  1. Coordinate compress all values in nums to a range [1, n].
  2. Initialize two BITs (one for arr1, one for arr2) to keep track of inserted values.
  3. For each operation:
    • For the first two elements, append to arr1 and arr2 respectively and update their BITs.
    • For each subsequent element:
      • Use BITs to count the number of elements greater than nums[i] in arr1 and arr2.
      • If arr1’s count is greater, append to arr1 and update its BIT.
      • If arr2’s count is greater, append to arr2 and update its BIT.
      • If counts are equal, append to the array with fewer elements (if still tied, to arr1).
  4. Concatenate arr1 and arr2 for the result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

class BIT {
public:
    vector<int> tree;
    int n;
    BIT(int n): n(n), tree(n + 2) {}
    void add(int i, int v) { for (; i <= n; i += i & -i) tree[i] += v; }
    int sum(int i) { int s = 0; for (; i > 0; i -= i & -i) s += tree[i]; return s; }
    int range(int l, int r) { return sum(r) - sum(l - 1); }
};
class Solution {
public:
    vector<int> resultArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> sorted = nums;
        sort(sorted.begin(), sorted.end());
        sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
        unordered_map<int, int> mp;
        for (int i = 0; i < sorted.size(); ++i) mp[sorted[i]] = i + 1;
        BIT bit1(n), bit2(n);
        vector<int> arr1{nums[0]}, arr2{nums[1]};
        bit1.add(mp[nums[0]], 1);
        bit2.add(mp[nums[1]], 1);
        for (int i = 2; i < n; ++i) {
            int idx = mp[nums[i]];
            int g1 = bit1.range(idx + 1, n);
            int g2 = bit2.range(idx + 1, n);
            if (g1 > g2) {
                arr1.push_back(nums[i]);
                bit1.add(idx, 1);
            } else if (g1 < g2) {
                arr2.push_back(nums[i]);
                bit2.add(idx, 1);
            } else {
                if (arr1.size() <= arr2.size()) {
                    arr1.push_back(nums[i]);
                    bit1.add(idx, 1);
                } else {
                    arr2.push_back(nums[i]);
                    bit2.add(idx, 1);
                }
            }
        }
        arr1.insert(arr1.end(), arr2.begin(), arr2.end());
        return arr1;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

// For large constraints, use sort.SearchInts for coordinate compression and implement BIT.
func resultArray(nums []int) []int {
    n := len(nums)
    sorted := append([]int{}, nums...)
    sort.Ints(sorted)
    uniq := []int{}
    for i, v := range sorted {
        if i == 0 || v != sorted[i-1] {
            uniq = append(uniq, v)
        }
    }
    idx := map[int]int{}
    for i, v := range uniq {
        idx[v] = i + 1
    }
    type BIT struct {
        t []int
        n int
    }
    add := func(b *BIT, i, v int) {
        for ; i <= b.n; i += i & -i {
            b.t[i] += v
        }
    }
    sum := func(b *BIT, i int) int {
        s := 0
        for ; i > 0; i -= i & -i {
            s += b.t[i]
        }
        return s
    }
    rng := func(b *BIT, l, r int) int {
        return sum(b, r) - sum(b, l-1)
    }
    bit1 := &BIT{make([]int, n+2), n}
    bit2 := &BIT{make([]int, n+2), n}
    arr1 := []int{nums[0]}
    arr2 := []int{nums[1]}
    add(bit1, idx[nums[0]], 1)
    add(bit2, idx[nums[1]], 1)
    for i := 2; i < n; i++ {
        id := idx[nums[i]]
        g1 := rng(bit1, id+1, n)
        g2 := rng(bit2, id+1, n)
        if g1 > g2 {
            arr1 = append(arr1, nums[i])
            add(bit1, id, 1)
        } else if g1 < g2 {
            arr2 = append(arr2, nums[i])
            add(bit2, id, 1)
        } else {
            if len(arr1) <= len(arr2) {
                arr1 = append(arr1, nums[i])
                add(bit1, id, 1)
            } else {
                arr2 = append(arr2, nums[i])
                add(bit2, id, 1)
            }
        }
    }
    return append(arr1, arr2...)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

class BIT {
    int[] t;
    int n;
    BIT(int n) { this.n = n; t = new int[n + 2]; }
    void add(int i, int v) { for (; i <= n; i += i & -i) t[i] += v; }
    int sum(int i) { int s = 0; for (; i > 0; i -= i & -i) s += t[i]; return s; }
    int range(int l, int r) { return sum(r) - sum(l - 1); }
}
class Solution {
    public int[] resultArray(int[] nums) {
        int n = nums.length;
        int[] sorted = nums.clone();
        Arrays.sort(sorted);
        int[] uniq = Arrays.stream(sorted).distinct().toArray();
        Map<Integer, Integer> idx = new HashMap<>();
        for (int i = 0; i < uniq.length; ++i) idx.put(uniq[i], i + 1);
        BIT bit1 = new BIT(n), bit2 = new BIT(n);
        List<Integer> arr1 = new ArrayList<>(), arr2 = new ArrayList<>();
        arr1.add(nums[0]); arr2.add(nums[1]);
        bit1.add(idx.get(nums[0]), 1);
        bit2.add(idx.get(nums[1]), 1);
        for (int i = 2; i < n; ++i) {
            int id = idx.get(nums[i]);
            int g1 = bit1.range(id + 1, n);
            int g2 = bit2.range(id + 1, n);
            if (g1 > g2) {
                arr1.add(nums[i]);
                bit1.add(id, 1);
            } else if (g1 < g2) {
                arr2.add(nums[i]);
                bit2.add(id, 1);
            } else {
                if (arr1.size() <= arr2.size()) {
                    arr1.add(nums[i]);
                    bit1.add(id, 1);
                } else {
                    arr2.add(nums[i]);
                    bit2.add(id, 1);
                }
            }
        }
        int[] ans = new int[n];
        int idx1 = 0;
        for (int x : arr1) ans[idx1++] = x;
        for (int x : arr2) ans[idx1++] = x;
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

class BIT(val n: Int) {
    val t = IntArray(n + 2)
    fun add(i0: Int, v: Int) {
        var i = i0
        while (i <= n) {
            t[i] += v
            i += i and -i
        }
    }
    fun sum(i0: Int): Int {
        var i = i0
        var s = 0
        while (i > 0) {
            s += t[i]
            i -= i and -i
        }
        return s
    }
    fun range(l: Int, r: Int) = sum(r) - sum(l - 1)
}
class Solution {
    fun resultArray(nums: IntArray): IntArray {
        val n = nums.size
        val sorted = nums.sorted().distinct()
        val idx = sorted.withIndex().associate { it.value to it.index + 1 }
        val bit1 = BIT(n)
        val bit2 = BIT(n)
        val arr1 = mutableListOf(nums[0])
        val arr2 = mutableListOf(nums[1])
        bit1.add(idx[nums[0]]!!, 1)
        bit2.add(idx[nums[1]]!!, 1)
        for (i in 2 until n) {
            val id = idx[nums[i]]!!
            val g1 = bit1.range(id + 1, n)
            val g2 = bit2.range(id + 1, n)
            if (g1 > g2) {
                arr1.add(nums[i])
                bit1.add(id, 1)
            } else if (g1 < g2) {
                arr2.add(nums[i])
                bit2.add(id, 1)
            } else {
                if (arr1.size <= arr2.size) {
                    arr1.add(nums[i])
                    bit1.add(id, 1)
                } else {
                    arr2.add(nums[i])
                    bit2.add(id, 1)
                }
            }
        }
        return (arr1 + arr2).toIntArray()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

class BIT:
    def __init__(self, n: int):
        self.n = n
        self.t = [0] * (n + 2)
    def add(self, i: int, v: int):
        while i <= self.n:
            self.t[i] += v
            i += i & -i
    def sum(self, i: int) -> int:
        s = 0
        while i > 0:
            s += self.t[i]
            i -= i & -i
        return s
    def range(self, l: int, r: int) -> int:
        return self.sum(r) - self.sum(l - 1)
class Solution:
    def resultArray(self, nums: list[int]) -> list[int]:
        n = len(nums)
        sorted_nums = sorted(set(nums))
        idx = {v: i + 1 for i, v in enumerate(sorted_nums)}
        bit1 = BIT(n)
        bit2 = BIT(n)
        arr1 = [nums[0]]
        arr2 = [nums[1]]
        bit1.add(idx[nums[0]], 1)
        bit2.add(idx[nums[1]], 1)
        for i in range(2, n):
            id = idx[nums[i]]
            g1 = bit1.range(id + 1, n)
            g2 = bit2.range(id + 1, n)
            if g1 > g2:
                arr1.append(nums[i])
                bit1.add(id, 1)
            elif g1 < g2:
                arr2.append(nums[i])
                bit2.add(id, 1)
            else:
                if len(arr1) <= len(arr2):
                    arr1.append(nums[i])
                    bit1.add(id, 1)
                else:
                    arr2.append(nums[i])
                    bit2.add(id, 1)
        return arr1 + arr2
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

struct BIT {
    t: Vec<i32>,
    n: usize,
}
impl BIT {
    fn new(n: usize) -> Self { Self { t: vec![0; n + 2], n } }
    fn add(&mut self, mut i: usize, v: i32) {
        while i <= self.n {
            self.t[i] += v;
            i += i & (!i + 1);
        }
    }
    fn sum(&self, mut i: usize) -> i32 {
        let mut s = 0;
        while i > 0 {
            s += self.t[i];
            i -= i & (!i + 1);
        }
        s
    }
    fn range(&self, l: usize, r: usize) -> i32 {
        self.sum(r) - self.sum(l - 1)
    }
}
impl Solution {
    pub fn result_array(nums: Vec<i32>) -> Vec<i32> {
        let n = nums.len();
        let mut sorted = nums.clone();
        sorted.sort();
        sorted.dedup();
        let idx: std::collections::HashMap<i32, usize> = sorted.iter().enumerate().map(|(i, &v)| (v, i + 1)).collect();
        let mut bit1 = BIT::new(n);
        let mut bit2 = BIT::new(n);
        let mut arr1 = vec![nums[0]];
        let mut arr2 = vec![nums[1]];
        bit1.add(idx[&nums[0]], 1);
        bit2.add(idx[&nums[1]], 1);
        for i in 2..n {
            let id = idx[&nums[i]];
            let g1 = bit1.range(id + 1, n);
            let g2 = bit2.range(id + 1, n);
            if g1 > g2 {
                arr1.push(nums[i]);
                bit1.add(id, 1);
            } else if g1 < g2 {
                arr2.push(nums[i]);
                bit2.add(id, 1);
            } else {
                if arr1.len() <= arr2.len() {
                    arr1.push(nums[i]);
                    bit1.add(id, 1);
                } else {
                    arr2.push(nums[i]);
                    bit2.add(id, 1);
                }
            }
        }
        arr1.extend(arr2);
        arr1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

class BIT {
    t: number[];
    n: number;
    constructor(n: number) { this.n = n; this.t = Array(n + 2).fill(0); }
    add(i: number, v: number) { for (; i <= this.n; i += i & -i) this.t[i] += v; }
    sum(i: number) { let s = 0; for (; i > 0; i -= i & -i) s += this.t[i]; return s; }
    range(l: number, r: number) { return this.sum(r) - this.sum(l - 1); }
}
class Solution {
    resultArray(nums: number[]): number[] {
        const n = nums.length;
        const sorted = Array.from(new Set(nums)).sort((a, b) => a - b);
        const idx = new Map<number, number>();
        sorted.forEach((v, i) => idx.set(v, i + 1));
        const bit1 = new BIT(n), bit2 = new BIT(n);
        const arr1 = [nums[0]], arr2 = [nums[1]];
        bit1.add(idx.get(nums[0])!, 1);
        bit2.add(idx.get(nums[1])!, 1);
        for (let i = 2; i < n; ++i) {
            const id = idx.get(nums[i])!;
            const g1 = bit1.range(id + 1, n);
            const g2 = bit2.range(id + 1, n);
            if (g1 > g2) {
                arr1.push(nums[i]);
                bit1.add(id, 1);
            } else if (g1 < g2) {
                arr2.push(nums[i]);
                bit2.add(id, 1);
            } else {
                if (arr1.length <= arr2.length) {
                    arr1.push(nums[i]);
                    bit1.add(id, 1);
                } else {
                    arr2.push(nums[i]);
                    bit2.add(id, 1);
                }
            }
        }
        return arr1.concat(arr2);
    }
}

Complexity

  • ⏰ Time complexity: O(n log n), for coordinate compression and O(log n) per operation.
  • 🧺 Space complexity: O(n), for the BITs and arrays.