Distribute elements into two arrays ii

Array Binary Indexed Tree Segment Tree Simulation

30.4% acceptance

Feb 25, 2026

157

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. 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 less, append to arr2. If equal, append to arr1 if arr1 has fewer elements, else to arr1 if still tie. Return the array result formed by concatenating arr1 and arr2.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn result_array(nums: Vec<i32>) -> Vec<i32> {
    // Use coordinate compression + BIT for greaterCount
    let n = nums.len();
    let mut sorted = nums.clone();
    sorted.sort_unstable();
    sorted.dedup();
    let m = sorted.len();
    let compress = |x: i32| -> usize { sorted.partition_point(|&v| v < x) + 1 };

    let mut bit1 = vec![0i32; m + 2];
    let mut bit2 = vec![0i32; m + 2];
    let mut size1: i32;
    let mut size2: i32;

    let bit_update = |bit: &mut Vec<i32>, i: usize, m: usize| {
      let mut i = i as i32;
      while i <= m as i32 { bit[i as usize] += 1; i += i & -i; }
    };
    let bit_query = |bit: &Vec<i32>, i: usize| -> i32 {
      let mut s = 0; let mut i = i as i32;
      while i > 0 { s += bit[i as usize]; i -= i & -i; }
      s
    };
    let greater_count = |bit: &Vec<i32>, val: i32, size: i32, _m: usize| -> i32 {
      let ci = compress(val);
      size - bit_query(bit, ci)
    };

    let mut arr1 = vec![nums[0]]; bit_update(&mut bit1, compress(nums[0]), m); size1=1;
    let mut arr2 = vec![nums[1]]; bit_update(&mut bit2, compress(nums[1]), m); size2=1;

    for i in 2..n {
      let v = nums[i];
      let g1 = greater_count(&bit1, v, size1, m);
      let g2 = greater_count(&bit2, v, size2, m);
      if g1 > g2 || (g1 == g2 && size1 <= size2) {
        arr1.push(v); bit_update(&mut bit1, compress(v), m); size1+=1;
      } else {
        arr2.push(v); bit_update(&mut bit2, compress(v), m); size2+=1;
      }
    }
    arr1.extend(arr2);
    arr1
  }
}