Create Sorted Array through Instructions

Intuitionturning insertion costs into frequency queries

When value x arrives, the sorted position it would occupy is determined by the values already inserted. The elements strictly less than x are exactly the previous values in the range 1 to x - 1. The elements strictly greater than x are all previous elements except those less than or equal to x. Therefore, the cost needs two counts, not an actual insertion into a sorted container.

The values arrive online: each answer depends only on earlier instructions, and the current value must be added after its cost is calculated. A frequency table alone cannot find a range count quickly, but a Fenwick tree stores cumulative frequencies. Its prefix sum gives the number of inserted values up to any value, while its point update records the new instruction.

Approachquery first, charge the cheaper side, then insert

1. 1Find the largest instruction value and create a Fenwick tree indexed by values from 1 through that maximum, because every input value must have a frequency position and unused larger positions are unnecessary.
2. 2Process instructions from left to right, using the loop index as the number of values already inserted, because only earlier values may contribute to the current insertion cost.
3. 3Query the prefix through value - 1 and call it less, because that prefix excludes equal values and therefore counts exactly the elements strictly smaller than the current value.
4. 4Query the prefix through value and call it lessOrEqual, because subtracting it from the number already inserted removes every value that is not strictly greater.
5. 5Compute greater as inserted - lessOrEqual, because the current value has not been added yet and the previous elements split into less than or equal to, and greater than, the current value.
6. 6Add min(less, greater) to the running answer modulo 1,000,000,007, because the statement charges the cheaper side and the total can exceed the integer range used for one count.
7. 7Update the Fenwick tree at value by one only after charging the cost, because including the current instruction would incorrectly make it compete with itself.
8. 8Return the accumulated answer after all instructions have been processed, since every insertion has contributed its own independent minimum cost.

Complexityeach insertion performs two logarithmic queries and one logarithmic update

Annotated solutionC++ · Fenwick tree · query before update

#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
    int createSortedArray(vector<int>& instructions) {
        const int MOD = 1000000007;
        int maxValue = 0;
        for (int value : instructions) {
            maxValue = max(maxValue, value);
        }

        vector<int> bit(maxValue + 2, 0);

        auto add = [&](int index, int delta) {
            for (int i = index; i < static_cast<int>(bit.size()); i += i & -i) {
                bit[i] += delta;
            }
        };

        auto sum = [&](int index) {
            int total = 0;
            for (int i = index; i > 0; i -= i & -i) {
                total += bit[i];
            }
            return total;
        };

        long long cost = 0;
        for (int i = 0; i < static_cast<int>(instructions.size()); ++i) {
            int value = instructions[i];
            int less = sum(value - 1);
            int lessOrEqual = sum(value);
            int greater = i - lessOrEqual;

            cost = (cost + min(less, greater)) % MOD;
            add(value, 1);
        }

        return static_cast<int>(cost);
    }
};

The two queries deliberately use different endpoints. sum(value - 1) excludes duplicates, while sum(value) includes them so that the greater count also excludes every equal value. The loop index i is the number of previous instructions, which makes i - lessOrEqual exact without maintaining a second counter.

Common mistakesthree boundary errors that change strict comparisons