#2869

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Minimum Operations to Collect Elements

Scan from the end, track seen values from 1 to k, and stop once every required number is collected.

Problem Statement

You are given a positive integer array nums and an integer k. In one move, you remove the current last element of nums and place it into your collection. Your goal is to collect every value from 1 through k at least once.

Return the fewest moves needed before your collection contains all required values 1, 2, ..., k. Since you can only remove from the back, the answer is the length of the shortest suffix whose elements include every required value. For nums = [3,1,5,4,2] and k = 2, scanning from the end sees 2, 4, 5, 1, so the answer is 4.

Examples

Example 1

Input: nums = [3,1,5,4,2], k = 2

Output: 4

After 4 operations, we collect elements 2, 4, 5, and 1, in this order. Our collection contains elements 1 and 2. Hence, the answer is 4.

Example 2

Input: nums = [3,1,5,4,2], k = 5

Output: 5

After 5 operations, we collect elements 2, 4, 5, 1, and 3, in this order. Our collection contains elements 1 through 5. Hence, the answer is 5.

Example 3

Input: nums = [3,2,5,3,1], k = 3

Output: 4

After 4 operations, we collect elements 1, 3, 5, and 2, in this order. Our collection contains elements 1 through 3. Hence, the answer is 4.

Constraints

1 <= nums.length <= 50
1 <= nums[i] <= nums.length
1 <= k <= nums.length
The input is generated such that you can collect elements 1, 2, ..., k.

Solution Approach

Reverse scan with a seen set

Start from the last index and move left because each operation removes the current tail. When nums[i] is between 1 and k, add it to a hash set. As soon as the set size reaches k, return n - i. This directly models the minimum suffix that contains all required values.

Occurrence array instead of a hash set

Because the target values are exactly 1 through k, a boolean array of size k + 1 is often cleaner than a hash set. Mark seen[x] when x <= k, and keep a counter of how many distinct required values have been found. This matches the interview hint and avoids extra hash overhead.

Bit mask when k is small

You can also store collected values 1 through k in a bit mask, where bit x - 1 means value x has appeared. Update the mask during the backward scan and stop when it matches the full target mask. This keeps the same logic but makes the state compact, which is useful when discussing the Bit Manipulation tag.

Complexity Analysis

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

A single backward pass touches each element at most once, so the time complexity is O(n). The extra space is O(k) with a set or occurrence array, or O(1) auxiliary space if a bit mask fits in a standard integer for the given k.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Traverse in Reverse Order

We can traverse the array in reverse order. For each element encountered during the traversal that is less than or equal to $k$ and has not been added to the set yet, we add it to the set until the set contains elements from $1$ to $k$.

1

2

3

4

5

6

7

8

9

10

11

12

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

Continue Practicing

#2857 count pairs of points with distance k #2897 apply operations on array to maximize sum of squares #2932 maximum strong pair xor i