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.

#1649

Hard

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

通过指令创建有序数组

给你一个整数数组 instructions ，你需要根据 instructions 中的元素创建一个有序数组。一开始你有一个空的数组 nums ，你需要从左到右遍历 instructions 中的元素，将它们依次插入 nums 数组中。每一次插入操作的代价是以下两者的较小值： nums …

数组二分查找分治树状数组线段树

题目描述

给你一个整数数组 instructions ，你需要根据 instructions 中的元素创建一个有序数组。一开始你有一个空的数组 nums ，你需要 从左到右 遍历 instructions 中的元素，将它们依次插入 nums 数组中。每一次插入操作的代价是以下两者的 较小值 ：

nums 中 严格小于 instructions[i] 的数字数目。
nums 中 严格大于 instructions[i] 的数字数目。

比方说，如果要将 3 插入到 nums = [1,2,3,5] ，那么插入操作的代价为 min(2, 1) (元素 1 和 2 小于 3 ，元素 5 大于 3 ），插入后 nums 变成 [1,2,3,3,5] 。

请你返回将 instructions 中所有元素依次插入 nums 后的 总最小代价 。由于答案会很大，请将它对 10⁹ + 7 取余后返回。

示例 1：

输入：instructions = [1,5,6,2]
输出：1
解释：一开始 nums = [] 。
插入 1 ，代价为 min(0, 0) = 0 ，现在 nums = [1] 。
插入 5 ，代价为 min(1, 0) = 0 ，现在 nums = [1,5] 。
插入 6 ，代价为 min(2, 0) = 0 ，现在 nums = [1,5,6] 。
插入 2 ，代价为 min(1, 2) = 1 ，现在 nums = [1,2,5,6] 。
总代价为 0 + 0 + 0 + 1 = 1 。

示例 2:

输入：instructions = [1,2,3,6,5,4]
输出：3
解释：一开始 nums = [] 。
插入 1 ，代价为 min(0, 0) = 0 ，现在 nums = [1] 。
插入 2 ，代价为 min(1, 0) = 0 ，现在 nums = [1,2] 。
插入 3 ，代价为 min(2, 0) = 0 ，现在 nums = [1,2,3] 。
插入 6 ，代价为 min(3, 0) = 0 ，现在 nums = [1,2,3,6] 。
插入 5 ，代价为 min(3, 1) = 1 ，现在 nums = [1,2,3,5,6] 。
插入 4 ，代价为 min(3, 2) = 2 ，现在 nums = [1,2,3,4,5,6] 。
总代价为 0 + 0 + 0 + 0 + 1 + 2 = 3 。

示例 3：

输入：instructions = [1,3,3,3,2,4,2,1,2]
输出：4
解释：一开始 nums = [] 。
插入 1 ，代价为 min(0, 0) = 0 ，现在 nums = [1] 。
插入 3 ，代价为 min(1, 0) = 0 ，现在 nums = [1,3] 。
插入 3 ，代价为 min(1, 0) = 0 ，现在 nums = [1,3,3] 。
插入 3 ，代价为 min(1, 0) = 0 ，现在 nums = [1,3,3,3] 。
插入 2 ，代价为 min(1, 3) = 1 ，现在 nums = [1,2,3,3,3] 。
插入 4 ，代价为 min(5, 0) = 0 ，现在 nums = [1,2,3,3,3,4] 。
插入 2 ，代价为 min(1, 4) = 1 ，现在 nums = [1,2,2,3,3,3,4] 。
插入 1 ，代价为 min(0, 6) = 0 ，现在 nums = [1,1,2,2,3,3,3,4] 。
插入 2 ，代价为 min(2, 4) = 2 ，现在 nums = [1,1,2,2,2,3,3,3,4] 。
总代价为 0 + 0 + 0 + 0 + 1 + 0 + 1 + 0 + 2 = 4 。

提示：

1 <= instructions.length <= 10⁵
1 <= instructions[i] <= 10⁵

lightbulb

解题思路

方法一：树状数组

树状数组，也称作“二叉索引树”（Binary Indexed Tree）或 Fenwick 树。它可以高效地实现如下两个操作：

单点更新 update(x, delta)：把序列 x 位置的数加上一个值 delta；
前缀和查询 query(x)：查询序列 [1,...x] 区间的区间和，即位置 x 的前缀和。

这两个操作的时间复杂度均为 $O(\log n)$ 。

树状数组最基本的功能就是求比某点 x 小的点的个数（这里的比较是抽象的概念，可以是数的大小、坐标的大小、质量的大小等等）。

比如给定数组 a[5] = {2, 5, 3, 4, 1}，求 b[i] = 位置 i 左边小于等于 a[i] 的数的个数。对于此例，b[5] = {0, 1, 1, 2, 0}。

解决方案是直接遍历数组，每个位置先求出 query(a[i])，然后再修改树状数组 update(a[i], 1) 即可。当数的范围比较大时，需要进行离散化，即先进行去重并排序，然后对每个数字进行编号。

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

30

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

error
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.
error
Not utilizing efficient data structures like a Binary Indexed Tree or Segment Tree can result in suboptimal performance.
error
The modulo operation (10^9 + 7) should be correctly applied to prevent overflow errors.

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#2179 统计数组中好三元组数目 #2426 满足不等式的数对数目 #493 翻转对