#1649
Create Sorted Array through Instructions
Hard Fenwick tree counting
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Insert numbers one by one into a sorted container. Each insertion costs min(count of existing numbers strictly less, count strictly greater). Return the total cost modulo 1e9+7.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: inserting each number costs min(smaller already in, bigger already in); total cost?
Why this works: a Fenwick tree indexed by value counts how many inserted numbers are below or above x in O(log M).
Example: [1, 5, 6, 2]
1: 0, 5: 0, 6: 0, 2: min(1 smaller, 2 bigger) = 1 → total 1✦Hints open one at a time
You need "how many inserted so far are < x" and "> x" quickly.
Values are at most 10^5, so a Fenwick tree indexed by value counts them.
↗Approach
less = prefix(x − 1); greater = inserted − prefix(x). Add min to the cost, then add 1 at x.
</>Solution (Java)
class Solution {
public int createSortedArray(int[] instructions) {
final int MOD = 1_000_000_007;
int max = 0;
for (int x : instructions) max = Math.max(max, x);
int[] tree = new int[max + 1];
long cost = 0;
for (int i = 0; i < instructions.length; i++) {
int x = instructions[i];
int less = prefix(tree, x - 1);
int greater = i - prefix(tree, x); // i numbers inserted so far
cost += Math.min(less, greater);
for (int j = x; j <= max; j += j & -j) tree[j]++;
}
return (int) (cost % MOD);
}
private int prefix(int[] tree, int i) {
int s = 0;
for (; i > 0; i -= i & -i) s += tree[i];
return s;
}
}!Common mistake
Counting "greater" as inserted − prefix(x − 1), which wrongly includes equal values.
Complexity
- Time: O(n log M), M = max value.
- Space: O(M).
Topic: Segment Tree, Fenwick & Sparse Table
🎬 Episodes 98–100: video coming soon