Create Sorted Array through Instructions

hard array bit segment tree

Problem

You insert numbers from instructions[] one by one into a sorted array. Each insertion costs min(count of strictly smaller, count of strictly greater) already inserted. Return the total cost modulo 10⁹+7.

Inputinstructions = [1,5,6,2]

Output1

Costs: 0 (insert 1), 0 (5), 0 (6), 1 (2 has one smaller and two greater).

instructions

MOD = 10**9 + 7

def create_sorted_array(instructions):
    n = max(instructions) + 2
    bit = [0] * n
    def upd(i):
        while i < n:
            bit[i] += 1; i += i & -i
    def qry(i):
        s = 0
        while i > 0:
            s += bit[i]; i -= i & -i
        return s
    cost = 0
    for k, x in enumerate(instructions):
        less = qry(x - 1)
        greater = k - qry(x)
        cost = (cost + min(less, greater)) % MOD
        upd(x)
    return cost

function createSortedArray(instr) {
  const MOD = 1e9 + 7;
  const n = Math.max(...instr) + 2;
  const bit = new Array(n).fill(0);
  const upd = i => { for (; i < n; i += i & -i) bit[i]++; };
  const qry = i => { let s = 0; for (; i > 0; i -= i & -i) s += bit[i]; return s; };
  let cost = 0;
  for (let k = 0; k < instr.length; k++) {
    const x = instr[k];
    const less = qry(x - 1);
    const greater = k - qry(x);
    cost = (cost + Math.min(less, greater)) % MOD;
    upd(x);
  }
  return cost;
}

class Solution {
    int[] bit; int n;
    void upd(int i) { for (; i < n; i += i & -i) bit[i]++; }
    int qry(int i) { int s = 0; for (; i > 0; i -= i & -i) s += bit[i]; return s; }
    public int createSortedArray(int[] instr) {
        int MOD = 1_000_000_007;
        n = 0;
        for (int x : instr) n = Math.max(n, x);
        n += 2;
        bit = new int[n];
        long cost = 0;
        for (int k = 0; k < instr.length; k++) {
            int x = instr[k];
            int less = qry(x - 1), greater = k - qry(x);
            cost = (cost + Math.min(less, greater)) % MOD;
            upd(x);
        }
        return (int) cost;
    }
}

int createSortedArray(vector<int>& instr) {
    const int MOD = 1e9 + 7;
    int n = *max_element(instr.begin(), instr.end()) + 2;
    vector<int> bit(n, 0);
    auto upd = [&](int i) { for (; i < n; i += i & -i) bit[i]++; };
    auto qry = [&](int i) { int s = 0; for (; i > 0; i -= i & -i) s += bit[i]; return s; };
    long long cost = 0;
    for (int k = 0; k < (int)instr.size(); k++) {
        int x = instr[k];
        int less = qry(x - 1), greater = k - qry(x);
        cost = (cost + min(less, greater)) % MOD;
        upd(x);
    }
    return (int) cost;
}

Explanation

Each insert costs min(count of smaller, count of greater) already inserted. To get both counts fast, we use a Fenwick tree (Binary Indexed Tree) indexed by value, which tracks how many of each number we have inserted so far and supports quick prefix counts.

upd(x) records one occurrence of value x, and qry(i) returns how many inserted values are <= i. Both run in O(log V), where V is the value range — the BIT's signature jumping by i & -i.

For each instruction x, before inserting we compute less = qry(x - 1) (how many already inserted are strictly smaller) and greater = k - qry(x) (the rest of the k already-inserted values that are strictly larger). We add min(less, greater) to the running cost (mod 10⁹+7), then call upd(x).

Using the BIT means we never re-scan the inserted numbers; each query and update is logarithmic, giving O(n log V) overall.

Example: instructions = [1, 5, 6, 2]. Inserting 1, 5, 6 each costs 0 (nothing smaller or nothing larger yet). Inserting 2 sees one smaller (1) and two larger (5, 6), so it adds min(1, 2) = 1. Total cost = 1.

Time: O(n log V) Space: O(V)