1649. Create Sorted Array through Instructions - Leetcode Solution

Code Implementation

from bisect import bisect_left, bisect_right, insort

class FenwickTree:
    def __init__(self, size):
        self.n = size + 2
        self.tree = [0] * (self.n)

    def update(self, index, delta):
        while index < self.n:
            self.tree[index] += delta
            index += index & -index

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

class Solution:
    def createSortedArray(self, instructions):
        MOD = 10**9 + 7
        max_val = max(instructions)
        ft = FenwickTree(max_val)
        cost = 0
        for i, num in enumerate(instructions):
            left = ft.query(num - 1)
            right = i - ft.query(num)
            cost = (cost + min(left, right)) % MOD
            ft.update(num, 1)
        return cost

class FenwickTree {
    vector<int> tree;
    int n;
public:
    FenwickTree(int size) : n(size + 2), tree(n, 0) {}
    void update(int index, int delta) {
        while (index < n) {
            tree[index] += delta;
            index += index & -index;
        }
    }
    int query(int index) {
        int result = 0;
        while (index > 0) {
            result += tree[index];
            index -= index & -index;
        }
        return result;
    }
};

class Solution {
public:
    int createSortedArray(vector<int>& instructions) {
        const int MOD = 1e9 + 7;
        int maxVal = *max_element(instructions.begin(), instructions.end());
        FenwickTree ft(maxVal);
        int cost = 0;
        for (int i = 0; i < instructions.size(); ++i) {
            int num = instructions[i];
            int left = ft.query(num - 1);
            int right = i - ft.query(num);
            cost = (cost + min(left, right)) % MOD;
            ft.update(num, 1);
        }
        return cost;
    }
};

class FenwickTree {
    int[] tree;
    int n;
    FenwickTree(int size) {
        n = size + 2;
        tree = new int[n];
    }
    void update(int index, int delta) {
        while (index < n) {
            tree[index] += delta;
            index += index & -index;
        }
    }
    int query(int index) {
        int result = 0;
        while (index > 0) {
            result += tree[index];
            index -= index & -index;
        }
        return result;
    }
}

class Solution {
    public int createSortedArray(int[] instructions) {
        int MOD = 1000000007;
        int maxVal = 0;
        for (int num : instructions) maxVal = Math.max(maxVal, num);
        FenwickTree ft = new FenwickTree(maxVal);
        int cost = 0;
        for (int i = 0; i < instructions.length; ++i) {
            int num = instructions[i];
            int left = ft.query(num - 1);
            int right = i - ft.query(num);
            cost = (cost + Math.min(left, right)) % MOD;
            ft.update(num, 1);
        }
        return cost;
    }
}

class FenwickTree {
    constructor(size) {
        this.n = size + 2;
        this.tree = new Array(this.n).fill(0);
    }
    update(index, delta) {
        while (index < this.n) {
            this.tree[index] += delta;
            index += index & -index;
        }
    }
    query(index) {
        let result = 0;
        while (index > 0) {
            result += this.tree[index];
            index -= index & -index;
        }
        return result;
    }
}

var createSortedArray = function(instructions) {
    const MOD = 1e9 + 7;
    let maxVal = Math.max(...instructions);
    let ft = new FenwickTree(maxVal);
    let cost = 0;
    for (let i = 0; i < instructions.length; ++i) {
        let num = instructions[i];
        let left = ft.query(num - 1);
        let right = i - ft.query(num);
        cost = (cost + Math.min(left, right)) % MOD;
        ft.update(num, 1);
    }
    return cost;
};

Problem Description

You are given an array of integers called instructions. You need to create a sorted array by inserting the elements from instructions one by one, from left to right.
When inserting instructions[i] into the array, the cost is defined as the minimum of:

The number of elements strictly less than instructions[i] already present in the array
The number of elements strictly greater than instructions[i] already present in the array

The total cost is the sum of the costs for each insertion. Return the total cost modulo 10^9 + 7.
Constraints: All insertions are processed in order, and the elements are not reused. The array can contain up to 10⁵ elements, and each element can be up to 10⁵ in value.

Thought Process

At first glance, the problem seems to require counting, for each number, how many elements are less than and greater than it in a dynamically growing array. A brute-force way would be to scan the array each time, but that would be too slow for large inputs.
We realize that we need a way to efficiently count the number of elements less than or greater than a given value, as the array grows. This is a classic use-case for data structures that support fast prefix sums or order statistics, such as Binary Indexed Trees (Fenwick Trees) or Segment Trees.
The key insight is that we do not need to maintain the array in sorted order; we only need to know, for each number, how many smaller and greater numbers have already been inserted, and do so quickly.

Solution Approach

To solve this efficiently, we use a Fenwick Tree (also known as a Binary Indexed Tree). This data structure allows us to:

Update the count of each number in O(log N) time
Query the prefix sum (number of elements less than or equal to a value) in O(log N) time

Step-by-step algorithm:

Initialize a Fenwick Tree large enough to cover all possible values in instructions.
Iterate through each number in instructions:
- Query the Fenwick Tree for the count of numbers less than the current number (prefix sum up to num - 1).
- Query the Fenwick Tree for the count of numbers less than or equal to the current number (prefix sum up to num).
- The number of elements greater than the current number is the total inserted so far minus the prefix sum up to num.
- The cost for this insertion is the minimum of the two counts above.
- Add this cost to the running total.
- Update the Fenwick Tree to record the new insertion of the current number.
After all insertions, return the total cost modulo 10^9 + 7.

We use the Fenwick Tree because it provides fast updates and prefix sum queries, which are precisely what we need for this problem.

Example Walkthrough

Consider instructions = [1,5,6,2]:

Insert 1: Array is [1]. No elements less or greater. Cost = 0.
Insert 5: Array is [1,5]. 1 element less (1), 0 greater. Cost = 0.
Insert 6: Array is [1,5,6]. 2 less (1,5), 0 greater. Cost = 0.
Insert 2: Array is [1,2,5,6]. 1 less (1), 2 greater (5,6). Cost = min(1,2) = 1.

Total cost = 0 + 0 + 0 + 1 = 1
At each step, the Fenwick Tree is updated so that queries for counts less than or greater than a number are efficient.

Time and Space Complexity

Brute-force approach:

For each insertion, scan the entire array so far to count less/greater elements.
Time complexity: O(N^2), where N is the length of instructions.
This is not feasible for N up to 10⁵.

Optimized approach (Fenwick Tree):

Each update and query is O(log M), where M is the maximum value in instructions.
Total time complexity: O(N log M).
Space complexity: O(M), for the Fenwick Tree array.
This is efficient enough for the given constraints.

Summary

The key insight is to use a Fenwick Tree to efficiently count how many numbers less than or greater than a given value have been inserted so far. This allows us to calculate the cost of each insertion in logarithmic time, making the solution feasible for large inputs. The elegance of the solution lies in recognizing that we do not need to actually sort or maintain the array, only to count efficiently, which is what the Fenwick Tree excels at.

AlgoMap.io

Want Help Cracking FAANG?