Create Sorted Array through Instructions

Hard

#1514Time: O(N^2), where N is the length of `instructions`. For each of the N elements, we perform an insertion into a list of size up to N-1. In Java's `ArrayList`, insertion takes O(i) time for the i-th element, leading to a total of Σ(i) from i=0 to N-1, which is O(N^2). While finding the counts can be optimized to O(log i) with binary search, the insertion operation dominates the complexity.Space: O(N), where N is the length of `instructions`, to store the `nums` list.1 company

Algorithms

Binary Search Divide and Conquer Merge Sort

Data structures

Array Binary Indexed Tree Segment Tree Ordered Set

Companies

Akuna Capital

Prompt

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 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 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 10⁹ + 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 <= 10⁵
1 <= instructions[i] <= 10⁵

Approaches

2 approaches with complexity analysis and trade-offs.

This approach simulates the process directly. We maintain a sorted list of numbers that have been inserted so far. For each new number from instructions, we can find the number of smaller and larger elements and then insert the new number into the list while maintaining its sorted order.

Algorithm

Initialize totalCost = 0 and an empty list nums.
Iterate through each number x in the instructions array.
To find the number of elements strictly less than x, use binary search on nums to find the index of the first element that is greater than or equal to x. This index, let's call it lessCount, is the count of elements smaller than x.
To find the number of elements strictly greater than x, use binary search again to find the index of the first element strictly greater than x (i.e., search for x+1). The number of greater elements is nums.size() minus this index.
Calculate the cost for the current insertion: min(lessCount, greaterCount).
Add the cost to totalCost, taking modulo 10^9 + 7.
Insert x into nums at the lessCount index to maintain the sorted order. This operation is slow for list-like data structures.
After the loop, return totalCost.

Walkthrough

The core of this approach is to maintain a sorted list, nums, of the numbers processed so far. For each new number x from the instructions array, we need to determine the cost of inserting it. The cost is min(count of elements < x, count of elements > x).

We can find these counts by performing binary searches on the sorted list nums. A binary search can find the insertion point for x, which directly gives us the count of elements smaller than x. A second binary search can find the count of elements smaller than or equal to x, which allows us to calculate the count of elements greater than x.

The main performance issue with this method is the insertion step. Inserting an element into the middle of a dynamic array (like Java's ArrayList) requires shifting all subsequent elements, which takes time proportional to the size of the list. Since the list can grow up to size N, this insertion operation takes O(N) time in the worst case.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public int createSortedArray(int[] instructions) {6        List<Integer> nums = new ArrayList<>();7        long cost = 0;8        int MOD = 1_000_000_007;9 10        for (int x : instructions) {11            int lessCount = findFirstIndex(nums, x);12            int greaterCount = nums.size() - findFirstIndex(nums, x + 1);13            14            cost = (cost + Math.min(lessCount, greaterCount)) % MOD;15            16            // This insertion is the O(N) bottleneck17            nums.add(lessCount, x);18        }19        return (int) cost;20    }21 22    // Finds the index of the first element >= target (lower_bound)23    // This is equivalent to counting elements < target24    private int findFirstIndex(List<Integer> list, int target) {25        int left = 0, right = list.size();26        while (left < right) {27            int mid = left + (right - left) / 2;28            if (list.get(mid) < target) {29                left = mid + 1;30            } else {31                right = mid;32            }33        }34        return left;35    }36}

Complexity

Time

O(N^2), where N is the length of `instructions`. For each of the N elements, we perform an insertion into a list of size up to N-1. In Java's `ArrayList`, insertion takes O(i) time for the i-th element, leading to a total of Σ(i) from i=0 to N-1, which is O(N^2). While finding the counts can be optimized to O(log i) with binary search, the insertion operation dominates the complexity.

Space

O(N), where N is the length of `instructions`, to store the `nums` list.

Trade-offs

Pros

Simple to understand and implement.
Uses standard library data structures.

Cons

Inefficient for large inputs due to the O(N^2) time complexity.
Will likely result in a 'Time Limit Exceeded' error on competitive programming platforms for the given constraints.

A much more efficient approach uses a Fenwick Tree (also known as a Binary Indexed Tree or BIT). This data structure is ideal for problems that require frequent prefix sum queries and point updates. We can use a BIT to maintain the frequency counts of all numbers seen so far. Since the numbers are constrained to a range up to 10^5, the BIT will be of a manageable size, allowing for very fast operations.

Algorithm

Define a constant MOD = 10^9 + 7 and MAX_VAL = 10^5.
Create a Fenwick Tree (BIT) array bit of size MAX_VAL + 2 and initialize it to zeros.
Initialize totalCost = 0.
Iterate through the instructions array from left to right. Let the current element be num and its 0-based index in the input array be i.
Query the BIT to find the number of elements strictly less than num: less = query(num - 1).
The total number of elements inserted so far is i. The number of elements less than or equal to num is query(num). Therefore, the number of elements strictly greater than num is greater = i - query(num).
The cost for this insertion is min(less, greater).
Add this cost to totalCost: totalCost = (totalCost + min(less, greater)) % MOD.
Update the BIT to reflect the insertion of num: update(num, 1).
After iterating through all instructions, return totalCost.

Walkthrough

The key insight is that for each instruction x, we need two pieces of information: the count of numbers already processed that are less than x, and the count of numbers already processed that are greater than x. A Fenwick Tree can provide this information efficiently.

We use a BIT of size M+1, where M is the maximum possible value in instructions (10^5). The BIT will store the frequencies of the numbers. update(val, 1) will increment the frequency of val, and query(idx) will give the cumulative frequency of all numbers up to idx.

For each number x at index i in instructions:

The number of elements strictly less than x is query(x - 1).
The total number of elements processed so far is i. The number of elements less than or equal to x is query(x). Thus, the number of elements strictly greater than x is i - query(x).
We calculate the cost min(less, greater) and add it to our total.
Finally, we call update(x, 1) to include the current number in our frequency counts for subsequent calculations.

Each query and update operation on the BIT takes O(log M) time. Since we do this for each of the N instructions, the total time complexity is O(N log M).

A similar approach can be implemented using a Segment Tree, which would also yield an O(N log M) time complexity but is generally more complex to implement and uses more memory.

1class Solution {2    int[] bit;3    final int MAX_VAL = 100001;4    final int MOD = 1_000_000_007;5 6    public int createSortedArray(int[] instructions) {7        // BIT array size is MAX_VAL + 1 to handle 1-based indexing for values up to MAX_VAL8        bit = new int[MAX_VAL + 1];9        long totalCost = 0;10 11        for (int i = 0; i < instructions.length; i++) {12            int x = instructions[i];13            14            // Count elements strictly less than x15            int lessCount = query(x - 1);16            17            // Count elements strictly greater than x18            // Total elements inserted so far is i19            // Elements <= x is query(x)20            // So, elements > x is i - query(x)21            int greaterCount = i - query(x);22            23            totalCost = (totalCost + Math.min(lessCount, greaterCount)) % MOD;24            25            // Update the BIT with the new element26            update(x, 1);27        }28        29        return (int) totalCost;30    }31 32    private void update(int index, int val) {33        while (index < bit.length) {34            bit[index] += val;35            index += index & -index; // Move to the next relevant index36        }37    }38 39    private int query(int index) {40        int sum = 0;41        while (index > 0) {42            sum += bit[index];43            index -= index & -index; // Move to the parent44        }45        return sum;46    }47}

Complexity

Time

O(N * log M), where N is the length of `instructions` and M is the maximum possible value in `instructions`. For each of the N instructions, we perform two queries and one update on the Fenwick Tree, each taking O(log M) time.

Space

O(M), where M is the maximum possible value in `instructions` (10^5). This space is required for the Fenwick Tree array.

Trade-offs

Pros

Highly efficient, easily passing the time limits for the given constraints.
A standard and powerful technique for problems involving range queries and point updates.

Cons

Requires knowledge of Fenwick Trees or similar data structures.
Space complexity depends on the range of values (M), not just the number of elements (N). This could be a drawback if M is much larger than N.

Solutions

Solution

1class BinaryIndexedTree { private int n ; private int [] c ; public BinaryIndexedTree ( int n ) { this . n = n ; this . c = new int [ n + 1 ]; } public void update ( int x , int v ) { while ( x <= n ) { c [ x ] += v ; x += x & - x ; } } public int query ( int x ) { int s = 0 ; while ( x > 0 ) { s += c [ x ]; x -= x & - x ; } return s ; } } class Solution { public int createSortedArray ( int [] instructions ) { int m = 0 ; for ( int x : instructions ) { m = Math . max ( m , x ); } BinaryIndexedTree tree = new BinaryIndexedTree ( m ); int ans = 0 ; final int mod = ( int ) 1 e9 + 7 ; for ( int i = 0 ; i < instructions . length ; ++ i ) { int x = instructions [ i ]; int cost = Math . min ( tree . query ( x - 1 ), i - tree . query ( x )); ans = ( ans + cost ) % mod ; tree . update ( x , 1 ); } return ans ; } }

1class BinaryIndexedTree { public: BinaryIndexedTree ( int _n ) : n ( _n ) , c ( _n + 1 ) {} void update ( int x , int delta ) { while ( x <= n ) { c [ x ] += delta ; x += x & - x ; } } int query ( int x ) { int s = 0 ; while ( x ) { s += c [ x ]; x -= x & - x ; } return s ; } private: int n ; vector < int > c ; }; class Solution { public: int createSortedArray ( vector < int >& instructions ) { int m = * max_element ( instructions . begin (), instructions . end ()); BinaryIndexedTree tree ( m ); const int mod = 1e9 + 7 ; int ans = 0 ; for ( int i = 0 ; i < instructions . size (); ++ i ) { int x = instructions [ i ]; int cost = min ( tree . query ( x - 1 ), i - tree . query ( x )); ans = ( ans + cost ) % mod ; tree . update ( x , 1 ); } return ans ; } };

1class BinaryIndexedTree : def __init__ ( self , n ): self . n = n self . c = [ 0 ] * ( n + 1 ) def update ( self , x : int , v : int ): while x <= self . n : self . c [ x ] += v x += x & - x def query ( self , x : int ) -> int : s = 0 while x : s += self . c [ x ] x -= x & - x return s class Solution : def createSortedArray ( self , instructions : List [ int ]) -> int : m = max ( instructions ) tree = BinaryIndexedTree ( m ) ans = 0 mod = 10 ** 9 + 7 for i , x in enumerate ( instructions ): cost = min ( tree . query ( x - 1 ), i - tree . query ( x )) ans += cost tree . update ( x , 1 ) return ans % mod

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem