Log inSign up
hardLeetCodeNot Started

Create Sorted Array Through Instructions

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Advanced DSA
Solve on LeetCode
Lesson

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 number of elements currently in nums that are strictly less than instructions[i]. - The number of elements currently in nums that are strictly greater than instructions[i].

For example, if inserting element 3 into nums = [1, 2, 3, 5], the number of elements strictly less than 3 is 2 and the number of elements strictly greater than 3 is 1. The cost is min(2, 1) = 1, and nums becomes [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 10^9 + 7.

Example 1 · 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 · Example 2:

Input: instructions = [1, 2, 3, 6, 5, 4]
Output: 3
Explanation: Insert 1 with cost min(0, 0) = 0, nums = [1]. Insert 2 with cost min(1, 0) = 0, nums = [1, 2]. Insert 3 with cost min(2, 0) = 0, nums = [1, 2, 3]. Insert 6 with cost min(3, 0) = 0, nums = [1, 2, 3, 6]. Insert 5 with cost min(3, 1) = 1, nums = [1, 2, 3, 5, 6]. Insert 4 with cost min(3, 2) = 2, nums = [1, 2, 3, 4, 5, 6]. Total cost is 0 + 0 + 0 + 0 + 1 + 2 = 3.

Example 3 · Example 3:

Input: instructions = [1, 3, 3, 3, 2, 4, 2, 1, 2]
Output: 4
Explanation: Total cost is 4 modulo 109 + 7.

Constraints:

  • 1 <= instructions.length <= 105
  • 1 <= instructions[i] <= 105

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the 3 distinct approaches for Create Sorted Array through Instructions.
  • Implement fully runnable solutions in C++, Java, Python, and JavaScript.
  • Analyze algorithmic trade-offs across data structure designs.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Create Sorted Array through Instructions
  • Advanced Data Structures & Algorithmic Paradigm
  • Fast Range Queries or Amortized Dynamic Operations

Algorithmic Decision Tree:

  • BRUTE_FORCE: Constraint sizes where n <= 2000.
  • BETTER: When segment tree implementations are already templated.
  • OPTIMAL: The optimal, industry standard solution for this problem.

Connected Patterns:

Segment TreeFenwick TreeDisjoint Set UnionDesign Data Structures

1. Sorted List Insertion with Binary Search

Intuition

Maintain a sorted dynamic array nums. For each incoming element x in instructions: 1. Use binary search (lower_bound) to find the count of elements strictly smaller than x. 2. Use binary search (upper_bound) to find the count of elements <= x. The count of elements strictly greater than x is \text{nums.size()} - \text{upper\_bound}. 3. Add min(\text{strictly less}, \text{strictly greater}) to total cost. 4. Insert x into nums at the upper_bound position. Even though binary search takes O(log n), inserting into a dynamic array requires shifting elements in O(n) time, leading to O(n2) overall time complexity.

When to apply: Constraint sizes where n <= 2000.

Algorithm

  1. Step 1: Initialize sorted list nums = [] and totalCost = 0.
  2. Step 2: For each x in instructions, compute strictly less count using lower_bound.
  3. Step 3: Compute strictly greater count as nums.size() - upper_bound.
  4. Step 4: Add min(less, greater) to totalCost modulo 109 + 7.
  5. Step 5: Insert x into nums maintaining sorted order.
  6. Step 6: Return totalCost.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5int createSortedArrayBrute(const std::vector<int>& instructions) {
6 const int MOD = 1e9 + 7;
7 std::vector<int> nums;
8 long long totalCost = 0;
9
10 for (int x : instructions) {
11 auto itLow = std::lower_bound(nums.begin(), nums.end(), x);
12 auto itHigh = std::upper_bound(nums.begin(), nums.end(), x);
13
14 int less = itLow - nums.begin();
15 int greater = nums.end() - itHigh;
16
17 totalCost = (totalCost + std::min(less, greater)) % MOD;
18 nums.insert(itHigh, x);
19 }
20
21 return totalCost;
22}
23
24int main() {
25 std::vector<int> inst = {1, 5, 6, 2};
26 std::cout << createSortedArrayBrute(inst) << std::endl;
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(n^2) due to array element shifts on insertion
  • Space complexity: O(n) auxiliary space for nums list

2. Segment Tree on Frequency Counts

Intuition

Let M = max(\text{instructions}). A Segment Tree whose leaves correspond to values 1 <= v <= M can maintain frequencies: - Leaf v stores the number of times value v has been inserted so far. - Query [1, x - 1] returns the count of elements strictly smaller than x. - Query [x + 1, M] returns the count of elements strictly greater than x. - Update leaf x by adding +1. Each query and update takes O(log M) time on a tree of size 4M.

When to apply: When segment tree implementations are already templated.

Algorithm

  1. Step 1: Determine maximum value M in instructions (up to 105).
  2. Step 2: Allocate segment tree array of size 4 * M initialized to 0.
  3. Step 3: For each x in instructions, query range [1, x - 1] for strictly less count.
  4. Step 4: Query range [x + 1, M] for strictly greater count.
  5. Step 5: Add min(less, greater) to total cost.
  6. Step 6: Update point x with +1 in segment tree.
  7. Step 7: Return total cost modulo 109 + 7.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5struct SegTree {
6 int n;
7 std::vector<int> tree;
8 SegTree(int n) : n(n), tree(4 * n + 1, 0) {}
9
10 void update(int node, int start, int end, int idx) {
11 if (start == end) {
12 tree[node]++;
13 return;
14 }
15 int mid = (start + end) / 2;
16 if (idx <= mid) update(2 * node, start, mid, idx);
17 else update(2 * node + 1, mid + 1, end, idx);
18 tree[node] = tree[2 * node] + tree[2 * node + 1];
19 }
20
21 int query(int node, int start, int end, int l, int r) {
22 if (r < start || end < l) return 0;
23 if (l <= start && end <= r) return tree[node];
24 int mid = (start + end) / 2;
25 return query(2 * node, start, mid, l, r) + query(2 * node + 1, mid + 1, end, l, r);
26 }
27};
28
29int createSortedArraySegTree(const std::vector<int>& instructions) {
30 const int MOD = 1e9 + 7;
31 int maxVal = *std::max_element(instructions.begin(), instructions.end());
32 SegTree st(maxVal);
33 long long totalCost = 0;
34
35 for (int x : instructions) {
36 int less = st.query(1, 1, maxVal, 1, x - 1);
37 int greater = st.query(1, 1, maxVal, x + 1, maxVal);
38 totalCost = (totalCost + std::min(less, greater)) % MOD;
39 st.update(1, 1, maxVal, x);
40 }
41
42 return totalCost;
43}
44
45int main() {
46 std::vector<int> inst = {1, 5, 6, 2};
47 std::cout << createSortedArraySegTree(inst) << std::endl;
48 return 0;
49}

Time & Space Complexity

  • Time complexity: O(n log M) time where M = max(instructions)
  • Space complexity: O(M) auxiliary space for the segment tree array

3. Binary Indexed Tree (Fenwick Tree)

Intuition

Because the values in instructions are bounded by 105, a Fenwick tree (Binary Indexed Tree) is optimal: 1. Initialize a BIT of size M = 100,000. 2. For the i-th element x = \text{instructions}[i] (0-indexed, meaning i elements have been inserted so far): - The count of elements strictly smaller than x is: \text{less} = \text{query}(x - 1). - The count of elements <= x is: \text{query}(x). - Therefore, the count of elements strictly greater than x is: \text{greater} = i - \text{query}(x). - Total cost increments by min(\text{less}, \text{greater}) \pmod{109 + 7}. - Add +1 at index x in the BIT using \text{add}(x, 1). 3. Because Fenwick tree uses only bitwise operations (i \mathrel{\&} -i) and a flat array of size M + 1, it executes in O(n log M) with extremely fast runtime and zero overhead.

When to apply: The optimal, industry standard solution for this problem.

Algorithm

  1. Step 1: Set maxVal = max(instructions) and allocate BIT of size maxVal + 1.
  2. Step 2: Loop i from 0 to instructions.length - 1 with current element x = instructions[i].
  3. Step 3: less = query(x - 1).
  4. Step 4: greater = i - query(x).
  5. Step 5: totalCost = (totalCost + min(less, greater)) % 1_000_000_007.
  6. Step 6: add(x, 1) in BIT.
  7. Step 7: Return totalCost.

Interactive trace

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Process instructions[0] = 1: i = 0
Visual state
Values and pointers at this exact step
pointers
S
1
0
↑ i
Check / comparison
min(0, 0) = 0
Decision / next transition
totalCost = 0
Why this step matters

Process instructions[0] = 1: i = 0. less = query(0) = 0. greater = 0 - query(1) = 0. Cost = min(0, 0) = 0. Add 1 at index 1 in BIT.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5struct Fenwick {
6 int n;
7 std::vector<int> tree;
8 Fenwick(int n) : n(n), tree(n + 1, 0) {}
9
10 void add(int i, int delta) {
11 for (; i <= n; i += i & -i) tree[i] += delta;
12 }
13
14 int query(int i) {
15 int sum = 0;
16 for (; i > 0; i -= i & -i) sum += tree[i];
17 return sum;
18 }
19};
20
21int createSortedArray(const std::vector<int>& instructions) {
22 const int MOD = 1e9 + 7;
23 int maxVal = *std::max_element(instructions.begin(), instructions.end());
24 Fenwick bit(maxVal);
25 long long totalCost = 0;
26
27 for (int i = 0; i < (int)instructions.size(); ++i) {
28 int x = instructions[i];
29 int less = bit.query(x - 1);
30 int greater = i - bit.query(x);
31 totalCost = (totalCost + std::min(less, greater)) % MOD;
32 bit.add(x, 1);
33 }
34
35 return totalCost;
36}
37
38int main() {
39 std::vector<int> inst = {1, 5, 6, 2};
40 std::cout << createSortedArray(inst) << std::endl;
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(n log M) time where M <= 10^5
  • Space complexity: O(M) space for BIT array

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Sorted List Insertion with Binary SearchO(n^2) due to array element shifts on insertionO(n) auxiliary space for nums listMaintain a sorted list. Use binary search to compute counts of elements strictly less and strictly greater, then insert.O(n2) due to array element shifts on insertion
2.Segment Tree on Frequency CountsO(n log M) time where M = max(instructions)O(M) auxiliary space for the segment tree arrayBuild a segment tree covering the value domain [1, maxVal]. Query range sums for strictly less and strictly greater frequencies in O(log M).O(n log M) time where M = max(instructions)
3.Binary Indexed Tree (Fenwick Tree)OptimalO(n log M) time where M <= 10^5O(M) space for BIT arrayUse a Fenwick tree of size max(instructions) to query strictly less (query(x-1)) and strictly greater (i - query(x)) in O(log M) time and O(M) space.O(n log M) time where M <= 105

Common Pitfalls & Crucial Edge Cases

Using binary search / array insertion in an actual array

Inserting into an array takes O(N) per instruction, resulting in O(N2) overall runtime and TLE.

Forgetting modulo at each addition step

Can cause 64-bit integer overflow if not taking % MOD.

Off-by-one in Fenwick Tree bound

Max value in instructions is 105, so Fenwick tree must have size at least 100002.

Crucial Edge Cases to Validate:

  • All elements are identical `[1, 1, 1, 1]` — Strictly less = 0, strictly greater = 0; total cost is 0.
  • Strictly ascending instructions — Cost for each element is 0 (strictly greater is 0).
  • Strictly descending instructions — Cost for each element is 0 (strictly less is 0).
  • Values up to 10^5 — Fenwick tree size of 100001 handles all values directly without coordinate compression.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the Fenwick Tree range queries immediately: less = query(x - 1), greater = total - query(x).
  2. Point out that since max value is 105, coordinate compression is not strictly necessary, keeping the code clean.
  3. Mention that this runs in O(N log M) time and O(M) auxiliary space.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.For each inserted number x, what is the cost added to the total?

2.How does a Fenwick Tree calculate both counts in O(log M) time?

3.Why must the total cost be computed modulo 109 + 7?

Back to DSA Sheet