Create sorted array through instructions

Array Binary Search Divide and Conquer Binary Indexed Tree Segment Tree Merge Sort Ordered Set

41.4% acceptance

Feb 25, 2026

690

Given an integer array instructions, create a sorted array from the elements. Start with an empty container nums. For each element from left to right in instructions, insert it into nums. The cost of each insertion is the minimum of the following: The number of elements currently in nums that are strictly less than instructions[i]. The number of elements currently in nums that are strictly greater than instructions[i]. Return the total cost to insert all elements modulo 10^9 + 7.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn create_sorted_array(instructions: Vec<i32>) -> i32 {
    const MOD: i64 = 1_000_000_007;
    const MAX_VAL: usize = 100_001;
    let mut bit = vec![0i32; MAX_VAL + 2];

    fn bit_update(bit: &mut Vec<i32>, mut i: usize, max_val: usize) {
      while i <= max_val {
        bit[i] += 1;
        i += i & i.wrapping_neg();
      }
    }

    fn bit_query(bit: &[i32], mut i: usize) -> i32 {
      let mut s = 0;
      while i > 0 {
        s += bit[i];
        i -= i & i.wrapping_neg();
      }
      s
    }

    let mut total_cost: i64 = 0;
    for (idx, &x) in instructions.iter().enumerate() {
      let x = x as usize;
      let less = bit_query(&bit, x - 1) as i64;
      let greater = idx as i64 - bit_query(&bit, x) as i64;
      total_cost = (total_cost + less.min(greater)) % MOD;
      bit_update(&mut bit, x, MAX_VAL);
    }
    total_cost as i32
  }
}