Create Sorted Array Through Instructions

Hard
1089.

Create Sorted Array Through Instructions

Create Sorted Array Through Instructions is a hard coding problem on arrays, binary search and divide and conquer, asked in Amazon, Google and Microsoft interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} instructions
 * @return {number}
 */
var createSortedArray = function(instructions) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Create Sorted Array Through Instructions — Solution

Create Sorted Array Through Instructions solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Create Sorted Array Through Instructions is a hard coding problem on arrays, binary search and divide and conquer, asked in Amazon, Google and Microsoft interviews.

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

Hints for Create Sorted Array Through Instructions

  1. Hint 1

    Both counts are order-statistics over the values inserted so far.

  2. Hint 2

    A Fenwick (binary indexed) tree over the value range answers "how many are at most v" in O(log V).

  3. Hint 3

    Elements equal to the new value count as neither smaller nor larger.

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

  1. Size the tree to the maximum value in instructions.
  2. For each value in order: compute less = query(v - 1) and greater = i - query(v).
  3. Add min(less, greater) to the running total modulo 10⁹ + 7.
  4. 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

Java

public static int createSortedArray(int[] instructions) {
    final int MOD = 1000000007;
    int maxv = 0;
    for (int v : instructions) maxv = Math.max(maxv, v);
    int[] tree = new int[maxv + 1];
    int total = 0;
    for (int i = 0; i < instructions.length; i++) {
        int v = instructions[i];
        int less = csaQuery(tree, v - 1);
        int greater = i - csaQuery(tree, v);
        total = (total + Math.min(less, greater)) % MOD;
        for (int x = v; x <= maxv; x += x & (-x)) tree[x]++;
    }
    return total;
}

private static int csaQuery(int[] tree, int idx) {
    int s = 0;
    for (int x = idx; x > 0; x -= x & (-x)) s += tree[x];
    return s;
}

C++

static int csaQuery(vector<int>& tree, int idx) {
    int s = 0;
    for (int x = idx; x > 0; x -= x & (-x)) s += tree[x];
    return s;
}

int createSortedArray(vector<int>& instructions) {
    const int MOD = 1000000007;
    int maxv = 0;
    for (int v : instructions) maxv = max(maxv, v);
    vector<int> tree(maxv + 1, 0);
    int total = 0;
    for (int i = 0; i < (int) instructions.size(); i++) {
        int v = instructions[i];
        int less = csaQuery(tree, v - 1);
        int greater = i - csaQuery(tree, v);
        total = (total + min(less, greater)) % MOD;
        for (int x = v; x <= maxv; x += x & (-x)) tree[x]++;
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Search