1649. Create Sorted Array through Instructions Solution

Q: Is Create Sorted Array through Instructions easy or hard?

Create Sorted Array through Instructions is classified as a Hard problem on LeetCode. The difficulty comes from recognizing that naive insertion or sorting approaches are too slow and that a Fenwick Tree or Segment Tree is required to maintain dynamic order statistics efficiently.

Q: Create Sorted Array through Instructions Python/Java solution

Python and Java implementations typically use a Fenwick Tree array to store frequencies. For each instruction, perform prefix sum queries to count smaller and greater elements, update the tree, and accumulate the cost modulo 1e9+7. The logic is identical across C++, Java, Python, C#, and JavaScript.

Q: How to solve Create Sorted Array through Instructions in O(n log n)?

Maintain a frequency structure such as a Binary Indexed Tree. For each number x, query the count of elements less than x using a prefix query and compute greater elements as insertedCount minus prefix(x). Add min(less, greater) to the total cost and update the tree at position x. This keeps every operation logarithmic.

Q: What is the best approach for Create Sorted Array through Instructions?

The most efficient approach uses a Fenwick Tree (Binary Indexed Tree) to track frequencies of inserted values. For each instruction x, query how many elements are smaller than x and how many are greater than x. The insertion cost is the minimum of these two counts. Each update and query takes O(log n), giving an overall complexity of O(n log n).

Q: Is Create Sorted Array through Instructions asked at Google/Amazon/Meta?

Problems involving Fenwick Trees, inversion counting, and order statistics frequently appear in interviews at companies like Google, Amazon, and Meta. This specific LeetCode problem is commonly used for advanced data structure practice and competitive programming preparation.

Q: What data structure is used in Create Sorted Array through Instructions?

The key data structures are Binary Indexed Trees (Fenwick Trees) and Segment Trees. Both support fast prefix or range frequency queries and updates in O(log n). They allow efficient counting of smaller and larger elements during incremental insertions.

Q: What is the time complexity of Create Sorted Array through Instructions?

The optimal solutions using a Fenwick Tree or Segment Tree run in O(n log n) time, where n is the number of instructions. Each step performs two range queries and one update in logarithmic time. Space complexity is O(n) or proportional to the value range after compression.

The 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 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⁵

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.

Python

class CreateSortedArray:
    def __init__(self):
        self.BIT = [0] * 100001
        self.MOD = 10**9 + 7

    def update(self, index, value):
        while index < len(self.BIT):
            self.BIT[index] += value
            index += index & -index

    def query(self, index):
        result = 0
        while index > 0:
            result += self.BIT[index]
            index -= index & -index
        return result

    def createSortedArray(self, instructions):
        cost = 0
        for i, instr in enumerate(instructions):
            left = self.query(instr - 1)
            right = i - self.query(instr)
            cost += min(left, right)
            self.update(instr, 1)
            cost %= self.MOD
        return cost

# Example usage
instructions = [1, 5, 6, 2]
solution = CreateSortedArray()
print(solution.createSortedArray(instructions))

Java

import java.util.*;

public class CreateSortedArray {
    private static final int MAX = 100001;
    private static final int MOD = 1000000007;
    private static int[] BIT = new int[MAX];

    private static void update(int idx, int val) {
        while (idx < MAX) {
            BIT[idx] += val;
            idx += idx & (-idx);
        }
    }

    private static int query(int idx) {
        int sum = 0;
        while (idx > 0) {
            sum += BIT[idx];
            idx -= idx & (-idx);
        }
        return sum;
    }

    public static int createSortedArray(int[] instructions) {
        long cost = 0;
        for (int i = 0; i < instructions.length; i++) {
            int left = query(instructions[i] - 1);
            int right = i - query(instructions[i]);
            cost += Math.min(left, right);
            cost %= MOD;
            update(instructions[i], 1);
        }
        return (int) cost;
    }

    public static void main(String[] args) {
        int[] instructions = {1, 5, 6, 2};
        System.out.println(createSortedArray(instructions));
    }
}

C++

#include <iostream>
#include <vector>
#define MAX 100001
#define MOD 1000000007

using namespace std;

vector<int> BIT(MAX);

void update(int idx, int val) {
    while (idx < MAX) {
        BIT[idx] += val;
        idx += idx & (-idx);
    }
}

int query(int idx) {
    int sum = 0;
    while (idx > 0) {
        sum += BIT[idx];
        idx -= idx & (-idx);
    }
    return sum;
}

int createSortedArray(vector<int>& instructions) {
    long cost = 0;
    for (size_t i = 0; i < instructions.size(); i++) {
        int left = query(instructions[i] - 1);
        int right = i - query(instructions[i]);
        cost += min(left, right);
        cost %= MOD;
        update(instructions[i], 1);
    }
    return static_cast<int>(cost);
}

int main() {
    vector<int> instructions = {1, 5, 6, 2};
    cout << createSortedArray(instructions) << endl;
    return 0;
}

JavaScript

class CreateSortedArray {
    constructor() {
        this.BIT = new Array(100001).fill(0);
        this.MOD = 1000000007;
    }

    update(index, value) {
        while (index < this.BIT.length) {
            this.BIT[index] += value;
            index += index & -index;
        }
    }

    query(index) {
        let result = 0;
        while (index > 0) {
            result += this.BIT[index];
            index -= index & -index;
        }
        return result;
    }

    createSortedArray(instructions) {
        let cost = 0;
        for (let i = 0; i < instructions.length; i++) {
            let left = this.query(instructions[i] - 1);
            let right = i - this.query(instructions[i]);
            cost = (cost + Math.min(left, right)) % this.MOD;
            this.update(instructions[i], 1);
        }
        return cost;
    }
}

// Example usage
const instructions = [1, 5, 6, 2];
const solution = new CreateSortedArray();
console.log(solution.createSortedArray(instructions));

#include <stdio.h>
#define MAX 100001
#define MOD 1000000007

int BIT[MAX] = {0};

void update(int idx, int val) {
    while (idx < MAX) {
        BIT[idx] += val;
        idx += idx & (-idx);
    }
}

int query(int idx) {
    int sum = 0;
    while (idx > 0) {
        sum += BIT[idx];
        idx -= idx & (-idx);
    }
    return sum;
}

int createSortedArray(int* instructions, int instructionsSize) {
    long cost = 0;
    for (int i = 0; i < instructionsSize; i++) {
        int left = query(instructions[i] - 1);
        int right = i - query(instructions[i]);
        cost += (left < right ? left : right);
        cost %= MOD;
        update(instructions[i], 1);
    }
    return (int)cost;
}

int main() {
    int instructions[] = {1, 5, 6, 2};
    int size = sizeof(instructions) / sizeof(instructions[0]);
    printf("%d\n", createSortedArray(instructions, size));
    return 0;
}

using System;

class CreateSortedArray {
    const int MAX = 100001;
    const int MOD = 1000000007;
    int[] BIT = new int[MAX];

    void Update(int idx, int val) {
        while (idx < MAX) {
            BIT[idx] += val;
            idx += idx & (-idx);
        }
    }

    int Query(int idx) {
        int sum = 0;
        while (idx > 0) {
            sum += BIT[idx];
            idx -= idx & (-idx);
        }
        return sum;
    }

    public int CreateSortedArray(int[] instructions) {
        long cost = 0;
        for (int i = 0; i < instructions.Length; i++) {
            int left = Query(instructions[i] - 1);
            int right = i - Query(instructions[i]);
            cost += Math.Min(left, right);
            cost %= MOD;
            Update(instructions[i], 1);
        }
        return (int)cost;
    }

    static void Main(string[] args) {
        int[] instructions = {1, 5, 6, 2};
        CreateSortedArray solution = new CreateSortedArray();
        Console.WriteLine(solution.CreateSortedArray(instructions));
    }
}

The Python class CreateSortedArray uses a method-based approach to define the BIT functionality. The class maintains an array for BIT and uses methods to update and query counts. This helps to compute the desired cost efficiently.

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.

Try this approach in the editor

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.

Python

class CreateSortedArray:
    def __init__(self):
        self.M = 100001
        self.MOD = 10**9 + 7
        self.segTree = [0] * (4 * self.M)

    def update(self, node, start, end, idx, val):
        if start == end:
            self.segTree[node] += val
        else:
            mid = (start + end) // 2
            leftChild = 2 * node + 1
            rightChild = 2 * node + 2
            if idx <= mid:
                self.update(leftChild, start, mid, idx, val)
            else:
                self.update(rightChild, mid + 1, end, idx, val)
            self.segTree[node] = self.segTree[leftChild] + self.segTree[rightChild]

    def query(self, node, start, end, L, R):
        if start > R or end < L:
            return 0
        if start >= L and end <= R:
            return self.segTree[node]
        mid = (start + end) // 2
        leftChild = 2 * node + 1
        rightChild = 2 * node + 2
        p1 = self.query(leftChild, start, mid, L, R)
        p2 = self.query(rightChild, mid + 1, end, L, R)
        return p1 + p2

    def createSortedArray(self, instructions):
        cost = 0
        for i, instr in enumerate(instructions):
            left = self.query(0, 0, self.M - 1, 0, instr - 1)
            right = i - self.query(0, 0, self.M - 1, 0, instr)
            cost = (cost + min(left, right)) % self.MOD
            self.update(0, 0, self.M - 1, instr, 1)
        return cost

# Example usage
instructions = [1, 5, 6, 2]
solution = CreateSortedArray()
print(solution.createSortedArray(instructions))

Java

import java.util.*;

public class CreateSortedArraySegmentTree {
    private static final int MAX = 100001;
    private static final int MOD = 1000000007;
    private int[] segTree = new int[4 * MAX];

    private void update(int node, int start, int end, int idx, int val) {
        if (start == end) {
            segTree[node] += val;
        } else {
            int mid = (start + end) / 2;
            int leftChild = 2 * node + 1;
            int rightChild = 2 * node + 2;
            if (idx <= mid) {
                update(leftChild, start, mid, idx, val);
            } else {
                update(rightChild, mid + 1, end, idx, val);
            }
            segTree[node] = segTree[leftChild] + segTree[rightChild];
        }
    }

    private int query(int node, int start, int end, int L, int R) {
        if (start > R || end < L) {
            return 0;
        }
        if (start >= L && end <= R) {
            return segTree[node];
        }
        int mid = (start + end) / 2;
        int leftChild = 2 * node + 1;
        int rightChild = 2 * node + 2;
        int p1 = query(leftChild, start, mid, L, R);
        int p2 = query(rightChild, mid + 1, end, L, R);
        return p1 + p2;
    }

    public int createSortedArray(int[] instructions) {
        Arrays.fill(segTree, 0);
        long cost = 0;
        for (int i = 0; i < instructions.length; i++) {
            int left = query(0, 0, MAX - 1, 0, instructions[i] - 1);
            int right = i - query(0, 0, MAX - 1, 0, instructions[i]);
            cost = (cost + Math.min(left, right)) % MOD;
            update(0, 0, MAX - 1, instructions[i], 1);
        }
        return (int) cost;
    }

    public static void main(String[] args) {
        int[] instructions = {1, 5, 6, 2};
        CreateSortedArraySegmentTree solution = new CreateSortedArraySegmentTree();
        System.out.println(solution.createSortedArray(instructions));
    }
}

C++

#include <iostream>
#include <vector>
#include <cstring>
#define MAX 100001
#define MOD 1000000007

using namespace std;

int segTree[4 * MAX];

void update(int node, int start, int end, int idx, int val) {
    if (start == end) {
        segTree[node] += val;
    } else {
        int mid = (start + end) / 2;
        int leftChild = 2 * node + 1;
        int rightChild = 2 * node + 2;
        if (idx <= mid) {
            update(leftChild, start, mid, idx, val);
        } else {
            update(rightChild, mid + 1, end, idx, val);
        }
        segTree[node] = segTree[leftChild] + segTree[rightChild];
    }
}

int query(int node, int start, int end, int L, int R) {
    if (start > R || end < L) {
        return 0;
    }
    if (start >= L && end <= R) {
        return segTree[node];
    }
    int mid = (start + end) / 2;
    int leftChild = 2 * node + 1;
    int rightChild = 2 * node + 2;
    int p1 = query(leftChild, start, mid, L, R);
    int p2 = query(rightChild, mid + 1, end, L, R);
    return p1 + p2;
}

int createSortedArray(vector<int>& instructions) {
    memset(segTree, 0, sizeof(segTree));
    long cost = 0;
    for (size_t i = 0; i < instructions.size(); i++) {
        int left = query(0, 0, MAX - 1, 0, instructions[i] - 1);
        int right = i - query(0, 0, MAX - 1, 0, instructions[i]);
        cost = (cost + min(left, right)) % MOD;
        update(0, 0, MAX - 1, instructions[i], 1);
    }
    return static_cast<int>(cost);
}

int main() {
    vector<int> instructions = {1, 5, 6, 2};
    cout << createSortedArray(instructions) << endl;
    return 0;
}

JavaScript

class CreateSortedArraySegmentTree {
    constructor() {
        this.M = 100001;
        this.MOD = 1000000007;
        this.segTree = new Array(4 * this.M).fill(0);
    }

    update(node, start, end, idx, val) {
        if (start === end) {
            this.segTree[node] += val;
        } else {
            const mid = Math.floor((start + end) / 2);
            const leftChild = 2 * node + 1;
            const rightChild = 2 * node + 2;
            if (idx <= mid) {
                this.update(leftChild, start, mid, idx, val);
            } else {
                this.update(rightChild, mid + 1, end, idx, val);
            }
            this.segTree[node] = this.segTree[leftChild] + this.segTree[rightChild];
        }
    }

    query(node, start, end, L, R) {
        if (start > R || end < L) {
            return 0;
        }
        if (start >= L && end <= R) {
            return this.segTree[node];
        }
        const mid = Math.floor((start + end) / 2);
        const leftChild = 2 * node + 1;
        const rightChild = 2 * node + 2;
        const p1 = this.query(leftChild, start, mid, L, R);
        const p2 = this.query(rightChild, mid + 1, end, L, R);
        return p1 + p2;
    }

    createSortedArray(instructions) {
        let cost = 0;
        for (let i = 0; i < instructions.length; i++) {
            const left = this.query(0, 0, this.M - 1, 0, instructions[i] - 1);
            const right = i - this.query(0, 0, this.M - 1, 0, instructions[i]);
            cost = (cost + Math.min(left, right)) % this.MOD;
            this.update(0, 0, this.M - 1, instructions[i], 1);
        }
        return cost;
    }
}

// Example usage
const instructions = [1, 5, 6, 2];
const solution = new CreateSortedArraySegmentTree();
console.log(solution.createSortedArray(instructions));

#include <stdio.h>
#include <string.h>
#define MAX 100001
#define MOD 1000000007

int segTree[4 * MAX];

void update(int node, int start, int end, int idx, int val) {
    if (start == end) {
        segTree[node] += val;
    } else {
        int mid = (start + end) / 2;
        int leftChild = 2 * node + 1;
        int rightChild = 2 * node + 2;
        if (idx <= mid) {
            update(leftChild, start, mid, idx, val);
        } else {
            update(rightChild, mid + 1, end, idx, val);
        }
        segTree[node] = segTree[leftChild] + segTree[rightChild];
    }
}

int query(int node, int start, int end, int L, int R) {
    if (start > R || end < L) {
        return 0;
    }
    if (start >= L && end <= R) {
        return segTree[node];
    }
    int mid = (start + end) / 2;
    int leftChild = 2 * node + 1;
    int rightChild = 2 * node + 2;
    int p1 = query(leftChild, start, mid, L, R);
    int p2 = query(rightChild, mid + 1, end, L, R);
    return p1 + p2;
}

int createSortedArray(int* instructions, int instructionsSize) {
    memset(segTree, 0, sizeof(segTree));
    long cost = 0;
    for (int i = 0; i < instructionsSize; i++) {
        int left = query(0, 0, MAX - 1, 0, instructions[i] - 1);
        int right = i - query(0, 0, MAX - 1, 0, instructions[i]);
        cost = (cost + (left < right ? left : right)) % MOD;
        update(0, 0, MAX - 1, instructions[i], 1);
    }
    return (int)cost;
}

int main() {
    int instructions[] = {1, 5, 6, 2};
    int size = sizeof(instructions) / sizeof(instructions[0]);
    printf("%d\n", createSortedArray(instructions, size));
    return 0;
}

using System;

class CreateSortedArraySegmentTree {
    private const int MAX = 100001;
    private const int MOD = 1000000007;
    private int[] segTree = new int[4 * MAX];

    private void Update(int node, int start, int end, int idx, int val) {
        if (start == end) {
            segTree[node] += val;
        } else {
            int mid = (start + end) / 2;
            int leftChild = 2 * node + 1;
            int rightChild = 2 * node + 2;
            if (idx <= mid) {
                Update(leftChild, start, mid, idx, val);
            } else {
                Update(rightChild, mid + 1, end, idx, val);
            }
            segTree[node] = segTree[leftChild] + segTree[rightChild];
        }
    }

    private int Query(int node, int start, int end, int L, int R) {
        if (start > R || end < L) {
            return 0;
        }
        if (start >= L && end <= R) {
            return segTree[node];
        }
        int mid = (start + end) / 2;
        int leftChild = 2 * node + 1;
        int rightChild = 2 * node + 2;
        int p1 = Query(leftChild, start, mid, L, R);
        int p2 = Query(rightChild, mid + 1, end, L, R);
        return p1 + p2;
    }

    public int CreateSortedArray(int[] instructions) {
        Array.Clear(segTree, 0, segTree.Length);
        long cost = 0;
        for (int i = 0; i < instructions.Length; i++) {
            int left = Query(0, 0, MAX - 1, 0, instructions[i] - 1);
            int right = i - Query(0, 0, MAX - 1, 0, instructions[i]);
            cost = (cost + Math.Min(left, right)) % MOD;
            Update(0, 0, MAX - 1, instructions[i], 1);
        }
        return (int) cost;
    }

    static void Main(string[] args) {
        int[] instructions = {1, 5, 6, 2};
        CreateSortedArraySegmentTree solution = new CreateSortedArraySegmentTree();
        Console.WriteLine(solution.CreateSortedArray(instructions));
    }
}

In Python, the Segment Tree is managed similarly to other languages with defined methods for updating the tree and querying ranges. It supports efficient calculation of insertion costs.

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.

Try this approach in the editor

Approach 3: Default Approach

TypeScript

class BinaryIndexedTree {
    private n: number;
    private c: number[];

    constructor(n: number) {
        this.n = n;
        this.c = new Array(n + 1).fill(0);
    }

    public update(x: number, v: number): void {
        while (x <= this.n) {
            this.c[x] += v;
            x += x & -x;
        }
    }

    public query(x: number): number {
        let s = 0;
        while (x > 0) {
            s += this.c[x];
            x -= x & -x;
        }
        return s;
    }
}

function createSortedArray(instructions: number[]): number {
    const m = Math.max(...instructions);
    const tree = new BinaryIndexedTree(m);
    let ans = 0;
    const mod = 10 ** 9 + 7;
    for (let i = 0; i < instructions.length; ++i) {
        const x = instructions[i];
        const cost = Math.min(tree.query(x - 1), i - tree.query(x));
        ans = (ans + cost) % mod;
        tree.update(x, 1);
    }
    return ans;
}

type BinaryIndexedTree struct {
	n int
	c []int
}

func newBinaryIndexedTree(n int) *BinaryIndexedTree {
	c := make([]int, n+1)
	return &BinaryIndexedTree{n, c}
}

func (this *BinaryIndexedTree) update(x, delta int) {
	for x <= this.n {
		this.c[x] += delta
		x += x & -x
	}
}

func (this *BinaryIndexedTree) query(x int) int {
	s := 0
	for x > 0 {
		s += this.c[x]
		x -= x & -x
	}
	return s
}

func createSortedArray(instructions []int) (ans int) {
	m := slices.Max(instructions)
	tree := newBinaryIndexedTree(m)
	const mod = 1e9 + 7
	for i, x := range instructions {
		cost := min(tree.query(x-1), i-tree.query(x))
		ans = (ans + cost) % mod
		tree.update(x, 1)
	}
	return
}

Try this approach in the editor

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	–

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

–

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

Frequently asked questions

Is Create Sorted Array through Instructions easy or hard?

Create Sorted Array through Instructions is classified as a Hard problem on LeetCode. The difficulty comes from recognizing that naive insertion or sorting approaches are too slow and that a Fenwick Tree or Segment Tree is required to maintain dynamic order statistics efficiently.

Create Sorted Array through Instructions Python/Java solution

Python and Java implementations typically use a Fenwick Tree array to store frequencies. For each instruction, perform prefix sum queries to count smaller and greater elements, update the tree, and accumulate the cost modulo 1e9+7. The logic is identical across C++, Java, Python, C#, and JavaScript.

How to solve Create Sorted Array through Instructions in O(n log n)?

Maintain a frequency structure such as a Binary Indexed Tree. For each number x, query the count of elements less than x using a prefix query and compute greater elements as insertedCount minus prefix(x). Add min(less, greater) to the total cost and update the tree at position x. This keeps every operation logarithmic.

What is the best approach for Create Sorted Array through Instructions?

The most efficient approach uses a Fenwick Tree (Binary Indexed Tree) to track frequencies of inserted values. For each instruction x, query how many elements are smaller than x and how many are greater than x. The insertion cost is the minimum of these two counts. Each update and query takes O(log n), giving an overall complexity of O(n log n).

Is Create Sorted Array through Instructions asked at Google/Amazon/Meta?

Problems involving Fenwick Trees, inversion counting, and order statistics frequently appear in interviews at companies like Google, Amazon, and Meta. This specific LeetCode problem is commonly used for advanced data structure practice and competitive programming preparation.

What data structure is used in Create Sorted Array through Instructions?

The key data structures are Binary Indexed Trees (Fenwick Trees) and Segment Trees. Both support fast prefix or range frequency queries and updates in O(log n). They allow efficient counting of smaller and larger elements during incremental insertions.

What is the time complexity of Create Sorted Array through Instructions?

The optimal solutions using a Fenwick Tree or Segment Tree run in O(n log n) time, where n is the number of instructions. Each step performs two range queries and one update in logarithmic time. Space complexity is O(n) or proportional to the value range after compression.

Create Sorted Array through Instructions solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Binary Indexed Tree (Fenwick Tree) Solution

Approach 2: Approach 2: Segment Tree Solution

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Create Sorted Array through Instructions solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Binary Indexed Tree (Fenwick Tree) Solution

Approach 2: Approach 2: Segment Tree Solution

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems