What is the key idea for Minimum Operations to Collect Elements?

Treat the answer as the smallest suffix that contains every value from 1 to k. Scan from the end, record required values as they appear, and stop at the first index where all required values have been seen.

Why does scanning backward work for this problem?

Each operation removes the last element, so the collection order is exactly the reverse traversal of nums. A backward scan simulates the allowed operations without physically modifying the array.

Should I use a hash set or an occurrence array for this pattern?

Both work. A hash set is simple, but an occurrence array is especially natural here because the only useful values are the fixed range 1 through k.

How does bit manipulation fit Minimum Operations to Collect Elements?

Instead of a set, you can store whether each required value has appeared in a bit mask. This is the same backward scan with a more compact representation of collected values.

What is the most common mistake on this problem?

The biggest mistake is solving the wrong direction. If you scan from the front or think about arbitrary selection, you miss that only suffix elements can be collected because every move removes from the back.

#2869

Easy

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

收集元素的最少操作次数

给你一个正整数数组 nums 和一个整数 k 。一次操作中，你可以将数组的最后一个元素删除，将该元素添加到一个集合中。请你返回收集元素 1, 2, ..., k 需要的最少操作次数。示例 1：输入： nums = [3,1,5,4,2], k = 2 输出： 4 解释： 4 次操作后，集…

数组哈希表位运算

题目描述

给你一个正整数数组 nums 和一个整数 k 。

一次操作中，你可以将数组的最后一个元素删除，将该元素添加到一个集合中。

请你返回收集元素 1, 2, ..., k 需要的 最少操作次数 。

示例 1：

输入：nums = [3,1,5,4,2], k = 2
输出：4
解释：4 次操作后，集合中的元素依次添加了 2 ，4 ，5 和 1 。此时集合中包含元素 1 和 2 ，所以答案为 4 。

示例 2：

输入：nums = [3,1,5,4,2], k = 5
输出：5
解释：5 次操作后，集合中的元素依次添加了 2 ，4 ，5 ，1 和 3 。此时集合中包含元素 1 到 5 ，所以答案为 5 。

示例 3：

输入：nums = [3,2,5,3,1], k = 3
输出：4
解释：4 次操作后，集合中的元素依次添加了 1 ，3 ，5 和 2 。此时集合中包含元素 1 到 3  ，所以答案为 4 。

提示：

1 <= nums.length <= 50
1 <= nums[i] <= nums.length
1 <= k <= nums.length
输入保证你可以收集到元素 1, 2, ..., k 。

lightbulb

解题思路

方法一：逆序遍历

我们可以逆序遍历数组，每次遍历到的元素如果小于等于 $k$ ，且没有被添加过，就将其添加到集合中，直到集合中包含了元素 $1$ 到 $k$ 为止。

时间复杂度 $O(n)$ ，其中 $n$ 是数组 $nums$ 的长度。空间复杂度 $O(k)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        is_added = [False] * k
        count = 0
        n = len(nums)
        for i in range(n - 1, -1, -1):
            if nums[i] > k or is_added[nums[i] - 1]:
                continue
            is_added[nums[i] - 1] = True
            count += 1
            if count == k:
                return n - i

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
They mention removing only from the end, which points to scanning nums backward instead of simulating deletions.
question_mark
They ask for the minimum operations, which is really the shortest suffix containing every value from 1 to k.
question_mark
They hint at an occurrence array, which means values outside 1 to k should be ignored instead of tracked.

warning

常见陷阱

外企场景

error
Scanning from the front breaks the problem because collection order is forced by tail removals, not arbitrary picks.
error
Counting duplicates toward completion gives the wrong answer; only the first seen copy of each value from 1 to k matters.
error
Tracking every number in nums wastes work, because values greater than k do not help satisfy the requirement.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return the actual suffix or collected order instead of just the operation count after finding the stopping index.
arrow_right_alt
Change the target from 1 through k to an arbitrary set of required values, which keeps the same backward scan but changes membership checks.
arrow_right_alt
Ask for the minimum operations when removals can happen from either end, which turns this suffix-only scan into a different window problem.

help

常见问题

外企场景

继续练习

#2857 统计距离为 k 的点对 #2897 对数组执行操作使平方和最大 #2932 找出强数对的最大异或值 I