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] <= 105In #1649 Create Sorted Array through Instructions, you insert elements into a growing sorted array and compute the cost of each insertion. The cost is defined as the minimum of two values: the number of existing elements strictly less than the current value and the number strictly greater than it. A naive insertion and counting strategy would lead to O(n^2) time, which is too slow for large inputs.
The key idea is to efficiently maintain frequency counts of inserted numbers and quickly query how many values fall within certain ranges. Data structures such as a Binary Indexed Tree (Fenwick Tree), Segment Tree, or other ordered structures allow prefix sum queries and updates in O(log n) time. By mapping instruction values (often with coordinate compression if needed), you can query counts of smaller and larger elements before inserting the current value.
Each step performs two range queries and one update, resulting in an overall time complexity of about O(n log m), where m is the range of values. The approach efficiently simulates building the sorted array without actually performing costly insertions.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Binary Indexed Tree (Fenwick Tree) | O(n log m) | O(m) |
| Segment Tree | O(n log m) | O(m) |
| Merge Sort / Divide & Conquer Counting | O(n log n) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
This problem is closely related to finding the number of inversions in an array
if i know the position in which i will insert the i-th element in I can find the minimum cost to insert it
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.
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.
1class CreateSortedArray {
2 constructor() {
3 this.BIT = new Array(100001).fill(0)
The JavaScript class CreateSortedArray uses an array for the BIT and provides update and query methods to handle operations on it. This allows efficient computation of costs for the operation.
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.
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.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
A naive method would insert elements into a list and count smaller or greater elements by scanning the array each time. This leads to O(n^2) time in the worst case, which becomes inefficient for large input sizes specified in the problem constraints.
Yes, problems involving Fenwick Trees, Segment Trees, and order statistics frequently appear in advanced coding interviews. This problem tests understanding of range queries, frequency counting, and efficient data structures for dynamic ordering.
A Binary Indexed Tree is commonly considered the best choice because it supports fast prefix sum queries and updates in logarithmic time. It is simpler to implement than a segment tree while providing the same asymptotic performance for this problem.
The optimal approach uses a Binary Indexed Tree (Fenwick Tree) or Segment Tree to maintain counts of inserted numbers. These structures allow efficient prefix queries to determine how many elements are smaller or greater than the current value. This reduces the time complexity to about O(n log m).
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.