#1649

Hard

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Create Sorted Array through Instructions

The problem asks to compute the cost of inserting elements into a sorted array using a series of instructions.

array binary search divide and conquer binary indexed tree segment tree

Problem Statement

You are given an array of integers, 'instructions'. Starting with an empty array 'nums', you need to insert each element of 'instructions' into 'nums' one by one. For each insertion, the cost is calculated as the minimum of the number of elements less than the current element and the number of elements greater than it in 'nums'. The total cost of all insertions is returned modulo 10^9 + 7.

For example, with the input instructions = [1,5,6,2], the cost for each insertion is computed based on the relative positions in the sorted array 'nums'. After all insertions, the total cost of these operations is calculated.

Examples

Example 1

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

Output: 1

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

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

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

Solution Approach

Binary Search Approach

The problem can be optimized by using binary search. This allows us to find the position of the current element in the sorted array efficiently, reducing the complexity of insertion. By keeping track of the number of elements less than and greater than the current element, we can compute the cost without having to resort to a brute force solution.

Binary Indexed Tree (BIT)

A Binary Indexed Tree (BIT) can be used to maintain the count of elements already inserted, allowing for quick range queries. With BIT, you can efficiently compute the number of elements smaller and larger than the current element, reducing the time complexity of each insertion.

Segment Tree Approach

A Segment Tree is another viable solution for this problem. It provides efficient querying and updating of ranges, which is useful for counting the elements smaller and larger than the current insertion point. The segment tree approach can also work well for large arrays and large value ranges.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this problem depends on the approach chosen. A Binary Indexed Tree or Segment Tree approach generally runs in O(log n) for each insertion, making the overall time complexity O(n log n). Binary search over the sorted array can also give similar performance. The space complexity varies based on the data structure, but it generally remains O(n).

What Interviewers Usually Probe

Does the candidate use a data structure that optimizes range queries and updates, such as a BIT or Segment Tree?
Can the candidate explain the trade-offs between different approaches, such as Binary Search vs Segment Tree?
Is the candidate aware of the need to handle large input sizes efficiently with their solution?

Common Pitfalls or Variants

Common pitfalls

The candidate might attempt to solve the problem with a brute force approach, leading to a time complexity that is too slow for large inputs.
Not utilizing efficient data structures like a Binary Indexed Tree or Segment Tree can result in suboptimal performance.
The modulo operation (10^9 + 7) should be correctly applied to prevent overflow errors.

Follow-up variants

What happens if we use a different sorting algorithm or data structure, like Merge Sort or a custom BST?
How would the solution change if we were to handle dynamic updates to the array instead of a single sequence of insertions?
What if we had constraints where instructions could include negative numbers or larger values?

FAQ

How can binary search help solve the Create Sorted Array through Instructions problem?

Binary search allows you to efficiently find the correct position of each element in the growing sorted array, which helps calculate the cost of insertion faster than using brute-force methods.

What is the time complexity of the best solution for the Create Sorted Array through Instructions problem?

The best solution uses Binary Indexed Trees or Segment Trees, both offering a time complexity of O(n log n), where n is the length of the instructions array.

What is the key challenge in solving the Create Sorted Array through Instructions problem?

The key challenge is optimizing the insertion process to compute the cost efficiently without resorting to an O(n^2) brute force approach.

Can this problem be solved without using binary search or segment trees?

While it's possible to solve this problem with simpler methods, such as sorting and linear scanning, doing so would not be efficient enough for large input sizes and would result in a much slower solution.

What is the significance of the modulo operation in this problem?

The modulo operation ensures that the total cost remains within bounds, preventing overflow and ensuring the answer fits within the constraints of the problem.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

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

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

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

Continue Practicing

#2179 count good triplets in an array #2426 number of pairs satisfying inequality #493 reverse pairs