Create Sorted Array through Instructions - Solution & Explanation
Problem Statement
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:
- The number of elements currently in
numsthat are strictly less thaninstructions[i]. - The number of elements currently in
numsthat are strictly greater thaninstructions[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] <= 105
Approach Overview
Problem 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 1: Approach 1: Binary Indexed Tree (Fenwick Tree) Solution
This approach uses a Binary Indexed Tree (BIT) data structure to efficiently count the number of elements less than and greater than the current element during the insertion process.
We maintain a BIT to store the frequency of each element from the instructions array. For each element, we calculate the cost as the minimum of the count of elements that are less than it and the count of elements that are greater than it that have been inserted so far. We use BIT to efficiently calculate prefix sums, which helps in calculating these counts.
The C implementation uses a Binary Indexed Tree (BIT) to keep track of element counts. The update function updates the tree, and the query function retrieves prefix sums. These are used to count how many elements are less than or greater than the current element, allowing for efficient insertion cost calculation.
Complexity
Time Complexity: O(n log n), where n is the number of instructions. The operations of update and query on the BIT are O(log n).
Space Complexity: O(n), to store the BIT.
Approach 2: Approach 2: Segment Tree Solution
This approach employs a Segment Tree to perform range query operations to efficiently count the number of elements less than and greater than the current element during insertion. The Segment Tree helps maintain the frequency of elements within a range and can provide range sum in logarithmic time, allowing for quick calculations of the insertion cost.
The C implementation uses a Segment Tree to efficiently count elements in a range for insertion cost calculation. The update function alters the Segment Tree to reflect changes in element frequency, while query retrieves summations of elements over a range.
Complexity
Time Complexity: O(n log n), where n is the number of instructions. The Segment Tree operations take O(log n).
Space Complexity: O(n), to store the Segment Tree.
Approach 3: Default Approach
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Binary Indexed Tree (Fenwick Tree) Solution | Time Complexity: O(n log n), where n is the number of instructions. The operations of update and query on the BIT are O(log n). Space Complexity: O(n), to store the BIT. |
| Approach 2: Segment Tree Solution | Time Complexity: O(n log n), where n is the number of instructions. The Segment Tree operations take O(log n). Space Complexity: O(n), to store the Segment Tree. |
| Default Approach | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Leetcode 1649. Create Sorted Array through Instructions • Fraz • 8,096 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Create Sorted Array through Instructions easy or hard?
Create Sorted Array through Instructions Python/Java solution
How to solve Create Sorted Array through Instructions in O(n log n)?
What is the best approach for Create Sorted Array through Instructions?
Is Create Sorted Array through Instructions asked at Google/Amazon/Meta?
What data structure is used in Create Sorted Array through Instructions?
What is the time complexity of Create Sorted Array through Instructions?
Ready to solve this problem?
Practice Create Sorted Array through Instructions with our built-in code editor and test cases.
Practice on FleetCode