Create Sorted Array through Instructions: Fenwick Tree for Insertion Costs

LeetCode Create Sorted Array through Instructions (Problem 1649) asks you to build a sorted array one element at a time and accumulate the total insertion cost. For each new element, the cost is the minimum of two counts: how many already-inserted elements are strictly less than it, and how many are strictly greater. You return the total cost modulo 10^9 + 7.

The problem

You are given an integer array instructions. Starting from an empty array nums, for each instructions[i] you insert it into nums while keeping nums sorted. Before each insertion, you compute two values:

• strictly_less: the number of elements already in nums that are strictly less than instructions[i]
• strictly_greater: the number of elements already in nums that are strictly greater than instructions[i]

The cost of that insertion is min(strictly_less, strictly_greater). You sum all costs and return the result modulo 10^9 + 7.

For instructions = [1, 5, 6, 2], the first three insertions all have cost 0 because they go at the end of the sorted array. Only inserting 2 into [1, 5, 6] costs anything: 1 element is smaller (the 1) and 2 elements are larger (5 and 6), so the cost is min(1, 2) = 1. The total is 1.

The brute force approach

The simplest solution maintains a sorted list. For each new element, you binary-search for its position to count how many elements fall on each side. That gives you strictly_less and strictly_greater in O(log n) time, but the actual insertion into the sorted list takes O(n) because you need to shift elements. Over n insertions, the total time is O(n^2). When instructions can have up to 100,000 elements, that is too slow.

You could also skip the binary search and just scan the list each time, but that is also O(n) per insertion and does not improve the situation.

The key insight

You do not actually need to maintain the sorted array itself. All you need for each insertion is two counts: how many values less than x and how many values greater than x exist so far. If you maintain a frequency array where freq[v] records how many times value v has been inserted, then strictly_less is the sum freq[1] + freq[2] + ... + freq[x-1] and strictly_greater is the sum freq[x+1] + ... + freq[max_val].

A Binary Indexed Tree (BIT), also called a Fenwick tree, lets you update a single frequency and query any prefix sum in O(log m) time, where m is the maximum value in the array. That turns the entire problem into O(n log m).

Step-by-step walkthrough

Here is how the algorithm processes instructions = [1, 5, 6, 2] using a BIT of size 7 (indices 0 through 6, since the max value is 6).

Each step queries the BIT twice (once for strictly_less, once to derive strictly_greater), then updates the BIT at the inserted value. Every query and update is O(log m), so the full pass over n instructions takes O(n log m).

The code

def createSortedArray(instructions):
    MOD = 10**9 + 7
    m = max(instructions)
    bit = [0] * (m + 2)

    def update(i):
        while i <= m:
            bit[i] += 1
            i += i & (-i)

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

    cost = 0
    for i, x in enumerate(instructions):
        less = query(x - 1)
        greater = i - query(x)
        cost = (cost + min(less, greater)) % MOD
        update(x)

    return cost

The BIT array is sized m + 2 to avoid boundary issues when querying or updating at index m. The update function increments every BIT node responsible for index i by walking up the tree. The query function sums all values from index 1 to i by walking down.

For strictly_greater, notice the trick: after inserting i elements (0-indexed), the total count of elements already in the array is i. The count of elements with value x or less is query(x). So strictly_greater = i - query(x). This avoids a second range query.

Complexity analysis

Here, n is the length of instructions and m is the maximum value in the array. Each of the n insertions performs a constant number of BIT operations, each taking O(log m). The BIT itself uses O(m) space. For this problem, m can be up to 100,000, so the space is manageable.

The building blocks

Binary Indexed Tree (Fenwick tree)

A BIT supports two operations in O(log n): point update and prefix sum query. It works by decomposing indices into powers of two. The key formula i & (-i) extracts the lowest set bit of i, which determines the range each BIT node is responsible for. If you have never seen a BIT before, practice it on a simpler problem first (like counting inversions or range sum queries) before tackling this one.

Frequency counting with prefix sums

Instead of maintaining a sorted array, you maintain frequencies. The number of elements strictly less than x is just the prefix sum up to x - 1. The number strictly greater is the total count minus the prefix sum up to x. This reframing is what makes the BIT applicable. Many "counting in a sorted structure" problems can be transformed into prefix sum queries on a frequency array.

Edge cases

All identical values. If every instruction is the same value, then strictly_less and strictly_greater are both 0 for every insertion. The total cost is 0.

Already sorted input. If the instructions arrive in increasing order, strictly_greater is always 0, so every insertion has cost 0. The same applies to strictly decreasing order, where strictly_less is always 0.

Large values with small n. The BIT size depends on the max value m, not on n. If m is 100,000 but n is 10, the BIT is still 100,000 entries. This is fine for this problem's constraints, but for extremely large value ranges you would need coordinate compression.

Modular arithmetic. The problem asks for the result mod 10^9 + 7. Apply the modulo after each addition to avoid overflow in languages with fixed-width integers. In Python, this is mostly a formality since integers have arbitrary precision, but it keeps the output correct.

From understanding to recall

The core pattern here has three pieces you need to internalize. First, reframe insertion cost as a frequency counting problem. Second, use a BIT to answer prefix sum queries in O(log m). Third, compute strictly_greater as total_inserted - query(x) instead of doing a separate range query.

The part that usually trips people up is the BIT mechanics. Practice writing update and query from scratch until the i & (-i) bit manipulation feels automatic. Once the BIT is second nature, the rest of the solution is just a loop that queries twice and updates once.

Space your practice sessions out over a few days. Each time, start from a blank editor and write the full solution without looking at notes. Pay special attention to the off-by-one details: querying x - 1 for strictly_less, using 1-based indexing, and sizing the BIT array to m + 2.

Related posts

• Reverse Pairs - Another hard counting problem that tracks relationships between elements during insertion, solved with a different divide-and-conquer approach.
• Count of Smaller Numbers After Self - Counts elements smaller than each value to its right, using a BIT or merge sort, the same frequency-based counting pattern.
• Kth Largest Element - Uses partitioning to find order statistics efficiently, a related skill for understanding element rankings in unsorted arrays.