Watch 10 video solutions for Create Sorted Array through Instructions, a hard level problem involving Array, Binary Search, Divide and Conquer. This walkthrough by Fraz has 8,001 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an integer array instructions, you are asked to create a sorted array from the elements in instructions. You start with an empty container nums. For each element from left to right in instructions, insert it into nums. The cost of each insertion is the minimum of the following:
nums that are strictly less than instructions[i].nums that are strictly greater than instructions[i].For example, if inserting element 3 into nums = [1,2,3,5], the cost of insertion is min(2, 1) (elements 1 and 2 are less than 3, element 5 is greater than 3) and nums will become [1,2,3,3,5].
Return the total cost to insert all elements from instructions into nums. Since the answer may be large, return it modulo 109 + 7
Example 1:
Input: instructions = [1,5,6,2] Output: 1 Explanation: Begin with nums = []. Insert 1 with cost min(0, 0) = 0, now nums = [1]. Insert 5 with cost min(1, 0) = 0, now nums = [1,5]. Insert 6 with cost min(2, 0) = 0, now nums = [1,5,6]. Insert 2 with cost min(1, 2) = 1, now nums = [1,2,5,6]. The total cost is 0 + 0 + 0 + 1 = 1.
Example 2:
Input: instructions = [1,2,3,6,5,4] Output: 3 Explanation: Begin with nums = []. Insert 1 with cost min(0, 0) = 0, now nums = [1]. Insert 2 with cost min(1, 0) = 0, now nums = [1,2]. Insert 3 with cost min(2, 0) = 0, now nums = [1,2,3]. Insert 6 with cost min(3, 0) = 0, now nums = [1,2,3,6]. Insert 5 with cost min(3, 1) = 1, now nums = [1,2,3,5,6]. Insert 4 with cost min(3, 2) = 2, now nums = [1,2,3,4,5,6]. The total cost is 0 + 0 + 0 + 0 + 1 + 2 = 3.
Example 3:
Input: instructions = [1,3,3,3,2,4,2,1,2] Output: 4 Explanation: Begin with nums = []. Insert 1 with cost min(0, 0) = 0, now nums = [1]. Insert 3 with cost min(1, 0) = 0, now nums = [1,3]. Insert 3 with cost min(1, 0) = 0, now nums = [1,3,3]. Insert 3 with cost min(1, 0) = 0, now nums = [1,3,3,3]. Insert 2 with cost min(1, 3) = 1, now nums = [1,2,3,3,3]. Insert 4 with cost min(5, 0) = 0, now nums = [1,2,3,3,3,4]. Insert 2 with cost min(1, 4) = 1, now nums = [1,2,2,3,3,3,4]. Insert 1 with cost min(0, 6) = 0, now nums = [1,1,2,2,3,3,3,4]. Insert 2 with cost min(2, 4) = 2, now nums = [1,1,2,2,2,3,3,3,4]. The total cost is 0 + 0 + 0 + 0 + 1 + 0 + 1 + 0 + 2 = 4.
Constraints:
1 <= instructions.length <= 1051 <= instructions[i] <= 105Problem Overview: You process an array of instructions and insert each number into a growing sorted array. The cost of inserting a value is the minimum between the number of existing elements strictly smaller than it and strictly greater than it. The goal is to compute the total cost after processing all instructions, modulo 1e9+7.
Approach 1: Binary Indexed Tree (Fenwick Tree) (Time: O(n log m), Space: O(m))
The core task is counting how many numbers smaller and larger than the current value already exist in the array. A Binary Indexed Tree efficiently maintains prefix frequencies of values seen so far. After coordinate compression (or using the value range directly if small), you query the Fenwick Tree to get countLess = query(x - 1) and countGreater = insertedSoFar - query(x). The insertion cost is min(countLess, countGreater). Then update the tree with the current value. Each query and update runs in O(log m), making the overall complexity O(n log m), where m is the maximum value range. This approach is compact, fast, and the most common solution used in competitive programming.
Approach 2: Segment Tree (Time: O(n log m), Space: O(m))
A Segment Tree solves the same frequency counting problem with explicit range queries. Each node stores how many times values in that segment have appeared. For every instruction x, query the range [1, x-1] to count smaller elements and [x+1, max] for larger elements. The insertion cost is again the minimum of those two counts. After computing the cost, update the tree at position x. Segment trees provide the same O(log m) update and query complexity but use more memory and code compared to Fenwick Trees. They become useful if the problem later requires additional range operations beyond prefix sums.
Both approaches rely on the same idea: maintain a dynamic frequency structure that supports fast prefix or range queries. This avoids repeatedly scanning the sorted array, which would otherwise lead to O(n^2) behavior. These data structures are commonly used in problems involving order statistics, inversion counting, and dynamic ranking.
Recommended for interviews: The Fenwick Tree solution is the expected optimal approach. It demonstrates strong understanding of prefix frequency queries and appears frequently in problems related to binary search style counting and inversion-like metrics. Explaining the naive insertion idea first shows reasoning, but implementing the Fenwick Tree proves mastery of advanced data structures.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Binary Indexed Tree (Fenwick Tree) | O(n log m) | O(m) | Best general solution for dynamic prefix counts and competitive programming problems |
| Segment Tree | O(n log m) | O(m) | Useful when more complex range queries or updates are required |