Create Sorted Array Through Instructions — Hard Problem & Solution

Insert the values of instructions one at a time, left to right, into an initially empty array that is always kept sorted.

Difficulty: Hard
Topics: Arrays, Binary Search, Divide and Conquer, Binary Indexed Tree, Merge Sort, Segment Tree
Asked at: Amazon, Google, Microsoft
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Insert the values of instructions one at a time, left to right, into an initially empty array that is always kept sorted. Inserting a value costs the minimum of:

the number of already-inserted elements strictly less than it, and
the number strictly greater than it.

Return the total cost, modulo 10⁹ + 7.

Example 1

Input: instructions = [1,5,6,2]
Output: 1
Explanation: Only inserting 2 costs anything: one element is smaller, two are larger.

Example 2

Input: instructions = [1,2,3,6,5,4]
Output: 3
Explanation: 0 + 0 + 0 + 0 + 1 + 2.

Example 3

Input: instructions = [1,3,3,3,2,4,2,1,2]
Output: 4
Explanation: Equal values cost nothing against each other.

Constraints

1 <= instructions.length <= 10^5
1 <= instructions[i] <= 10^5

How to solve Create Sorted Array Through Instructions

Keep a Fenwick tree indexed by value, counting how many of each value have been inserted. For a new value v, the smaller count is query(v - 1) and the larger count is i - query(v) where i is how many have been inserted; add the minimum and then record v.

Approach

Size the tree to the maximum value in instructions.
For each value in order: compute less = query(v - 1) and greater = i - query(v).
Add min(less, greater) to the running total modulo 10⁹ + 7.
Insert v into the tree.

Why it works

Using i - query(v) rather than query(maxV) - query(v) is the detail that makes equal values behave: query(v) includes the copies equal to v, so subtracting it from the insertion count leaves exactly the strictly-greater ones. A merge-sort counting pass computes the same thing offline, but the Fenwick tree keeps the cost available at the moment each insertion happens, which is what the running total needs.

Complexity

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

Pitfalls

Both counts are strict, so equal values must be excluded from each.
The total exceeds a 32-bit integer before the modulo — reduce as you accumulate.
The Fenwick tree is indexed by value, not by position.

Reference solution

Python

from typing import List

def createSortedArray(instructions: List[int]) -> int:
    MOD = 10**9 + 7
    maxv = max(instructions)
    tree = [0] * (maxv + 1)

    def add(i: int) -> None:
        while i <= maxv:
            tree[i] += 1
            i += i & -i

    def query(i: int) -> int:
        s = 0
        while i > 0:
            s += tree[i]
            i -= i & -i
        return s

    total = 0
    for i, v in enumerate(instructions):
        total = (total + min(query(v - 1), i - query(v))) % MOD
        add(v)
    return total

JavaScript

var createSortedArray = function(instructions) {
    var MOD = 1000000007, i;
    var maxv = 0;
    for (i = 0; i < instructions.length; i++) if (instructions[i] > maxv) maxv = instructions[i];
    var tree = [];
    for (i = 0; i <= maxv; i++) tree.push(0);
    var add = function(idx) {
        for (var x = idx; x <= maxv; x += x & (-x)) tree[x]++;
    };
    var query = function(idx) {
        var s = 0;
        for (var x = idx; x > 0; x -= x & (-x)) s += tree[x];
        return s;
    };
    var total = 0;
    for (i = 0; i < instructions.length; i++) {
        var v = instructions[i];
        var less = query(v - 1);
        var greater = i - query(v);
        total = (total + (less < greater ? less : greater)) % MOD;
        add(v);
    }
    return total;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue