# Create Sorted Array through Instructions
**Difficulty:** HARD
[External](https://leetcode.com/problems/create-sorted-array-through-instructions)
Canonical: https://scaleengineer.com/dsa/problems/create-sorted-array-through-instructions
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Divide and Conquer](https://scaleengineer.com/algorithms/divide-and-conquer), [Merge Sort](https://scaleengineer.com/algorithms/merge-sort)
**Data structures:** Array, Binary Indexed Tree, Segment Tree, Ordered Set
**Companies:** [Akuna Capital](https://scaleengineer.com/companies/akuna-capital)
---
## Problem
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** `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 <= 105`
* `1 <= instructions[i] <= 105`

# Approaches
## Brute Force with Sorted List
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.
**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.
**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.
### Explanation
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.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int createSortedArray(int[] instructions) {
        List<Integer> nums = new ArrayList<>();
        long cost = 0;
        int MOD = 1_000_000_007;

        for (int x : instructions) {
            int lessCount = findFirstIndex(nums, x);
            int greaterCount = nums.size() - findFirstIndex(nums, x + 1);
            
            cost = (cost + Math.min(lessCount, greaterCount)) % MOD;
            
            // This insertion is the O(N) bottleneck
            nums.add(lessCount, x);
        }
        return (int) cost;
    }

    // Finds the index of the first element >= target (lower_bound)
    // This is equivalent to counting elements < target
    private int findFirstIndex(List<Integer> list, int target) {
        int left = 0, right = list.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (list.get(mid) < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}
```
### 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`.

## Fenwick Tree (Binary Indexed Tree)
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.
**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.
**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.
### Explanation
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`:
1.  The number of elements strictly less than `x` is `query(x - 1)`.
2.  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)`.
3.  We calculate the cost `min(less, greater)` and add it to our total.
4.  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.

```java
class Solution {
    int[] bit;
    final int MAX_VAL = 100001;
    final int MOD = 1_000_000_007;

    public int createSortedArray(int[] instructions) {
        // BIT array size is MAX_VAL + 1 to handle 1-based indexing for values up to MAX_VAL
        bit = new int[MAX_VAL + 1];
        long totalCost = 0;

        for (int i = 0; i < instructions.length; i++) {
            int x = instructions[i];
            
            // Count elements strictly less than x
            int lessCount = query(x - 1);
            
            // Count elements strictly greater than x
            // Total elements inserted so far is i
            // Elements <= x is query(x)
            // So, elements > x is i - query(x)
            int greaterCount = i - query(x);
            
            totalCost = (totalCost + Math.min(lessCount, greaterCount)) % MOD;
            
            // Update the BIT with the new element
            update(x, 1);
        }
        
        return (int) totalCost;
    }

    private void update(int index, int val) {
        while (index < bit.length) {
            bit[index] += val;
            index += index & -index; // Move to the next relevant index
        }
    }

    private int query(int index) {
        int sum = 0;
        while (index > 0) {
            sum += bit[index];
            index -= index & -index; // Move to the parent
        }
        return sum;
    }
}
```
### 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`.

# Solutions
### Java

```java
class 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 ; } }
```

### CPP

```cpp
class 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 ; } };
```

### Python

```python
class 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
```