Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Create Sorted Array through Instructions

Problem (restated)

Start with an empty list. For each instruction x, insert x into the sorted list, paying min(count of current values < x, count of current values > x). Return the total cost modulo 10^9+7.

Intuition

You never need the list itself — only how many inserted numbers are strictly less / strictly greater than x. A Fenwick tree of frequencies on compressed ranks: less = prefix(rank-1), greater = total - prefix(rank) (everything ≤ x subtracted from the count). Then insert.

Approaches

Fenwick, min(less, greater)

Unverified

Time O(n log n)Space O(n)

Idea. Compress unique instruction values. For each x: add min(less, greater) into the answer, update(rank[x], 1), increment total. Equals of x sit in prefix(rank) so they count as neither less nor greater.

Walkthrough. [1,5,6,2]. Insert 1 (0). Insert 5 (0). Insert 6 (0). Insert 2: less=1, greater=2 → cost 1. Total 1.

Trade-offs. The pattern page lists lazy range-add for this id; a point-update frequency BIT is enough because each insert is a single value. Mod on every add.

Solution

class BIT {
  private n: number;
  private tree: number[];
  constructor(n: number) {
    this.n = n;
    this.tree = new Array<number>(n + 1).fill(0);
  }
  update(i: number, delta: number): void {
    for (i++; i <= this.n; i += i & -i) this.tree[i]! += delta;
  }
  prefixSum(i: number): number {
    if (i < 0) return 0;
    let s = 0;
    for (i++; i > 0; i -= i & -i) s += this.tree[i]!;
    return s;
  }
}

export function createSortedArray(instructions: number[]): number {
  const MOD = 1_000_000_007;
  const vals = [...new Set(instructions)].sort((a, b) => a - b);
  const rank = new Map<number, number>();
  vals.forEach((v, i) => rank.set(v, i));
  const bit = new BIT(vals.length);
  let ans = 0, total = 0;
  for (const x of instructions) {
    const r = rank.get(x)!;
    const less = bit.prefixSum(r - 1);
    const greater = total - bit.prefixSum(r);
    ans = (ans + Math.min(less, greater)) % MOD;
    bit.update(r, 1);
    total++;
  }
  return ans;
}

class BIT {
  private n: number;
  private tree: number[];
  constructor(n: number) {
    this.n = n;
    this.tree = new Array<number>(n + 1).fill(0);
  }
  update(i: number, delta: number): void {
    for (i++; i <= this.n; i += i & -i) this.tree[i]! += delta;
  }
  prefixSum(i: number): number {
    if (i < 0) return 0;
    let s = 0;
    for (i++; i > 0; i -= i & -i) s += this.tree[i]!;
    return s;
  }
}

export function createSortedArray(instructions: number[]): number {
  const MOD = 1_000_000_007;
  const vals = [...new Set(instructions)].sort((a, b) => a - b);
  const rank = new Map<number, number>();
  vals.forEach((v, i) => rank.set(v, i));
  const bit = new BIT(vals.length);
  let ans = 0, total = 0;
  for (const x of instructions) {
    const r = rank.get(x)!;
    const less = bit.prefixSum(r - 1);
    const greater = total - bit.prefixSum(r);
    ans = (ans + Math.min(less, greater)) % MOD;
    bit.update(r, 1);
    total++;
  }
  return ans;
}

Template connection

BIT as a dynamic ordered multiset: prefix counts give less/equal, total - equal gives greater. LC 315 is less-only, walking right to left.

Reflection

On compressed ranks, count how many values already stored are smaller and how many are greater, then add 1. The cost is min(smaller, greater).
An equal value is neither smaller nor greater. The running sum is modulo 10**9 + 7.
The first instruction costs 0. Repeating the same number is free. The tree is 1-indexed.