1649. Create Sorted Array through Instructions

1649

HardAdvanced Range Data StructuresBinary Indexed Tree (Fenwick tree) indexed by valueOrder-statistics counting with a Fenwick tree

Create Sorted Array through Instructions

You build a sorted array by inserting the elements of instructions one at a time. The cost of inserting instructions[i] is the minimum of (the count of elements already placed that are strictly less than instructions[i]) and (the count of elements already placed that are strictly greater than instructions[i]). After paying the cost you insert the element in sorted position. Return the total cost of all insertions modulo 10^9 + 7.

Open official problem prompt ↗

In plain English

Sum, over every insertion, the smaller of the count of already-placed smaller elements and already-placed larger elements, modulo 10^9 + 7.

Picture it like this

Imagine seating guests on a bench in numbered seats by their ticket number. As each guest arrives you look at how many are already seated to their left versus their right and walk in from whichever side is shorter; the walking distance is the cost, and a Fenwick tree is your fast tally of who is seated where.

Example

Input: instructions = [1, 5, 6, 2]
Output: 1
Why: Costs are 0 (insert 1), 0 (insert 5, nothing greater), 0 (insert 6), and min(1 less, 2 greater) = 1 for inserting 2; total 1.

Constraints

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

Pattern lesson

See the pattern, then code

Order-statistics counting with a Fenwick tree

↗

Advanced Range Data Structures

Online prefix or range queries with updates, inversions, or coordinate compression.. Keep a frequency count over the value range in a Fenwick tree. Before inserting v, prefix-sum up to v-1 gives how many earlier elements are smaller, and (elements placed so far) minus prefix-sum up to v gives how many are larger; the cost is the smaller of the two. Then bump v's frequency.

New words, made simpleKnow these before the algorithm

Fenwick tree (BIT): An array supporting prefix-sum queries and single-point updates, both in O(log m), using the lowest-set-bit trick i & (-i).
Rank / order statistic: How many stored values are less than a given value; here it drives the insertion cost.
Prefix sum query(i): Total count of stored values in [1, i]; query(v-1) is the number strictly less than v.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Maintain a sorted list and bisect

Rank lookup is O(log n) but the physical insertion is O(n), too slow for n = 10^5.

Keep the placed elements sorted; use binary search for the rank but shift on insert.

Time O(n^2) because each list insertion shifts elementsSpace O(n)

Best choiceFenwick tree over values

Both the query and the update are logarithmic, comfortably handling 10^5 instructions.

Count frequencies by value; prefix sums give smaller/larger counts in O(log m) and updates are O(log m).

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

The rule we keep true

Invariant

After processing the first i instructions, the Fenwick tree holds the exact frequency of every value seen so far, so query(x) always equals the count of placed elements <= x.

Why this is correct

Reasoning

For the element v being inserted, elements already placed split cleanly into strictly-less (query(v-1)), equal (do not affect the two moving fronts), and strictly-greater. The number strictly greater is the total placed so far (idx) minus those <= v (query(v)). Taking the minimum models walking in from the cheaper side. Updating the tree by +1 at v keeps the invariant for the next step, and summing under the modulus yields the required answer.

The algorithm in three movesSay these aloud before coding

1Create a Fenwick tree sized to the maximum value in instructions

after 1,5,6: tree counts {1,5,6}

2For each value v in order, query less = prefix(v-1)

insert 2: less = prefix(1) = 1

3Compute greater = (number inserted so far) - prefix(v)

greater = 3 - prefix(2) = 3 - 1 = 2, cost = min(1,2) = 1

4Add min(less, greater) to the running total, then increment v's count in the tree

5Return the total modulo 10^9 + 7

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readv = 1

2 · AskHow many placed are < 1 and > 1?

3 · Update statetree empty

4 · Resultless = query(0) = 0, greater = 0 - query(1) = 0, cost 0; update(1)

Key takeaway

Inserting the final element 2: one placed value is smaller (1) and two are larger (5, 6), so the cost is 1.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 6-8Size the tree to the value domain
The Fenwick tree is indexed by value 1..m, where m is the largest instruction, so counts live directly at their value's index.
2
Lines 10-13Point update
update(i) adds one to value i by walking up the tree via i += i & (-i), touching O(log m) nodes.
3
Lines 15-20Prefix-sum query
query(i) totals counts in [1, i] by walking down via i -= i & (-i), the standard Fenwick prefix read.
4
Lines 22-28Cost accumulation
less is prefix(v-1); greater is idx (elements so far) minus prefix(v); add the minimum, then record v. The final modulo keeps the total in range.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Duplicate values: equal elements count as neither strictly less nor strictly greater, so they contribute 0 to both sides for the current insert
The first element always costs 0 since nothing is placed yet
A strictly increasing input costs 0 every step (nothing is greater); a strictly decreasing input costs 0 too (nothing is less)
Large totals require the final modulo 10^9 + 7

Common beginner mistakes

Using query(v) instead of query(v-1) for the 'less than' count, which wrongly includes equal elements
Computing greater as idx - query(v-1), which double-counts equal elements as greater
Sizing the tree by instructions length instead of by maximum value
Applying the modulo mid-loop to less/greater (they are small) rather than only to the final sum, or forgetting it entirely

Check your understanding

When inserting v, why is the number of strictly greater placed elements idx - query(v) rather than idx - query(v-1)?

PyPython 3 · solution.py

Optimal

1from typing import List23class Solution:4    def createSortedArray(self, instructions: List[int]) -> int:5        MOD = 10**9 + 76        m = max(instructions)7        tree = [0] * (m + 1)89        def update(i: int) -> None:10            while i <= m:11                tree[i] += 112                i += i & (-i)1314        def query(i: int) -> int:15            s = 016            while i > 0:17                s += tree[i]18                i -= i & (-i)19            return s2021        total = 022        for idx, v in enumerate(instructions):23            less = query(v - 1)24            greater = idx - query(v)25            total += min(less, greater)26            update(v)27        return total % MOD

Time complexityO(n log m), where n is the number of instructions and m is the maximum valueOptimized

Space complexityO(m) for the Fenwick treeExplained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonGoogleBloomberg

Create Sorted Array through Instructions

Create Sorted Array through Instructions

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Advanced Range Data Structures