LeetCode Problem 2869

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Bit Manipulation

Solution

LeetCode 2869 - Minimum Operations to Collect Elements

Problem Understanding

This problem gives us an array nums and an integer k. We repeatedly perform an operation where we remove the last element of the array and add it to our collection.

The goal is to determine the minimum number of such operations required so that our collection contains every integer from 1 through k.

In other words, we are collecting elements from the end of the array toward the beginning. As we collect numbers, we want to know when we have seen all required values:

• 1
• 2
• 3
• ...
• k

The moment our collection contains all these values, we stop and return the number of elements we had to remove.

For example, if k = 3, then we need to collect the values {1, 2, 3}. Any numbers larger than 3 do not directly help us satisfy the requirement, although we may still need to collect them because they appear after the numbers we need.

The constraints are very small:

• 1 <= nums.length <= 50
• 1 <= nums[i] <= nums.length
• 1 <= k <= nums.length

The most important guarantee is that the input is generated such that the values 1 through k can always be collected. Therefore, there is always a valid answer.

Several edge cases are worth noting:

• The required values may all appear near the end of the array, producing a very small answer.
• Some required values may appear multiple times.
• Many irrelevant values larger than k may appear near the end.
• When k = 1, we only need to find the first occurrence of 1 when scanning from the end.
• The last required value might appear near the beginning of the array, forcing us to collect almost the entire array.

Approaches

Brute Force Approach

A straightforward approach is to simulate the collection process exactly as described.

We repeatedly remove elements from the end of the array. After each removal, we update a collection set and check whether all values from 1 through k are present.

To perform the check, we could iterate through every value from 1 to k and verify that it exists in the collection.

This approach is correct because it follows the problem statement directly. The first time all required values are present, we return the number of operations performed.

However, after each operation we may perform another scan of all k required values. With up to n operations, this leads to a time complexity of O(nk).

Key Observation

We only care about values in the range 1 through k.

Instead of repeatedly checking whether every required value has been collected, we can scan the array from right to left and keep track of which required values have already been seen.

Whenever we encounter a number between 1 and k, we add it to a set.

Once the set contains exactly k distinct values, we know we have seen every required number. The current position determines how many elements must be removed from the end.

This works because collecting elements from the end is equivalent to scanning the array backward. The first moment we have encountered all required values corresponds exactly to the minimum number of operations needed.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(nk)	O(k)	Simulate removals and repeatedly verify all required values
Optimal	O(n)	O(k)	Scan from right to left and stop once all required values are found

Algorithm Walkthrough

1. Create an empty set called collected.
2. Traverse the array from the last index toward the first index.
3. For each value:

• If the value is between 1 and k, insert it into collected.
• Values greater than k can be ignored because they are not required.

4. After inserting a value, check the size of collected.
5. If the size becomes exactly k, then every required number from 1 through k has been encountered.
6. At this moment, compute how many elements have been collected from the end. If the current index is i, then the number of collected elements is:

len(nums) - i 7. Return this value immediately because this is the first point where all required numbers have been seen, making it the minimum number of operations.

Why it works

Scanning from right to left exactly matches the order in which elements are collected from the end of the array. The set always contains the distinct required values that have already been collected. The first time the set reaches size k, we know we have collected every value from 1 through k. Since we stop at the earliest such moment, the returned operation count is minimal.

Python Solution

from typing import List

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        collected = set()

        for i in range(len(nums) - 1, -1, -1):
            if nums[i] <= k:
                collected.add(nums[i])

            if len(collected) == k:
                return len(nums) - i

        return 0

The implementation uses a set to store distinct required values that have been encountered while scanning from right to left.

The loop starts at the last index and moves toward the beginning. Whenever a value belongs to the required range 1 through k, it is inserted into the set. Duplicate values are automatically ignored by the set.

After each insertion, we check whether the set contains k distinct values. Since the required values are exactly 1 through k, having k distinct values in the set means all required numbers have been found.

The answer is computed as len(nums) - i, which represents the number of elements removed from the end to reach the current position.

Go Solution

func minOperations(nums []int, k int) int {
    collected := make(map[int]bool)

    for i := len(nums) - 1; i >= 0; i-- {
        if nums[i] <= k {
            collected[nums[i]] = true
        }

        if len(collected) == k {
            return len(nums) - i
        }
    }

    return 0
}

The Go implementation uses a map[int]bool in place of Python's set. The map stores all distinct required values encountered during the reverse traversal.

The logic is otherwise identical. Since the constraints are small and all values are positive integers, there are no integer overflow concerns. The problem guarantees a valid answer exists, although the implementation still includes a final return 0 for completeness.

Worked Examples

Example 1

Input

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

Required values: {1, 2}

Step	Index	Value	Collected Set	Size	Done?
1	4	2	{2}	1	No
2	3	4	{2}	1	No
3	2	5	{2}	1	No
4	1	1	{1,2}	2	Yes

At index 1, all required values have been found.

Answer:

5 - 1 = 4

Output:

4

Example 2

Input

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

Required values: {1,2,3,4,5}

Step	Index	Value	Collected Set
1	4	2	{2}
2	3	4	{2,4}
3	2	5	{2,4,5}
4	1	1	{1,2,4,5}
5	0	3	{1,2,3,4,5}

All five required values are found only after reaching index 0.

Answer:

5 - 0 = 5

Output:

5

Example 3

Input

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

Required values: {1,2,3}

Step	Index	Value	Collected Set
1	4	1	{1}
2	3	3	{1,3}
3	2	5	{1,3}
4	1	2	{1,2,3}

All required values have now been collected.

Answer:

5 - 1 = 4

Output:

4

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each array element is visited at most once
Space	O(k)	The set stores at most the values 1 through k

The algorithm performs a single reverse traversal of the array. Every insertion into the set is an average O(1) operation, so the total running time is linear in the length of the array. The set can contain at most k distinct required values, giving O(k) auxiliary space usage.

Test Cases

from typing import List

s = Solution()

assert s.minOperations([3,1,5,4,2], 2) == 4  # Example 1
assert s.minOperations([3,1,5,4,2], 5) == 5  # Example 2
assert s.minOperations([3,2,5,3,1], 3) == 4  # Example 3

assert s.minOperations([1], 1) == 1  # Single element array
assert s.minOperations([2,1], 1) == 1  # k = 1, target at end
assert s.minOperations([1,2], 1) == 2  # k = 1, target at start

assert s.minOperations([1,2,3,4], 4) == 4  # Need entire array
assert s.minOperations([4,3,2,1], 4) == 4  # Reverse order

assert s.minOperations([1,1,1,1], 1) == 1  # Many duplicates
assert s.minOperations([2,2,2,1], 2) == 2  # Duplicate required values

assert s.minOperations([5,6,1,2,3], 3) == 3  # Ignore large values
assert s.minOperations([1,4,5,2,3], 3) == 5  # Last needed value at beginning

assert s.minOperations([3,3,3,2,2,1], 3) == 3  # Multiple duplicates
assert s.minOperations([6,5,4,3,2,1], 3) == 3  # Required values already at end

Test Summary

Test	Why
[3,1,5,4,2], k=2	Official example 1
[3,1,5,4,2], k=5	Official example 2
[3,2,5,3,1], k=3	Official example 3
[1], k=1	Smallest valid input
[2,1], k=1	Required value at end
[1,2], k=1	Required value at beginning
[1,2,3,4], k=4	Entire array must be collected
[4,3,2,1], k=4	Reverse ordering
[1,1,1,1], k=1	Heavy duplication
[2,2,2,1], k=2	Duplicate required values
[5,6,1,2,3], k=3	Ignore values larger than k
[1,4,5,2,3], k=3	Final required value appears first
[3,3,3,2,2,1], k=3	Multiple repeated targets
[6,5,4,3,2,1], k=3	Required values concentrated at end

Edge Cases

Edge Case 1: k = 1

When k equals 1, the only value we need is 1. A common mistake is to overcomplicate the logic by expecting multiple values. The algorithm naturally handles this case because the set reaches size 1 as soon as the first 1 is encountered while scanning from the end.

Edge Case 2: Many Duplicate Required Values

Arrays may contain repeated occurrences of required numbers. For example, [3,3,3,2,2,1] with k = 3 contains several duplicates. A counting approach could accidentally treat duplicates as new discoveries. Using a set ensures each required value is counted only once.

Edge Case 3: Irrelevant Large Values

Values larger than k do not contribute toward satisfying the requirement. For example, in [5,6,1,2,3] with k = 3, the values 5 and 6 are irrelevant. The implementation ignores them by only inserting values <= k into the set.

Edge Case 4: Entire Array Must Be Collected

Sometimes the final missing required value appears at the first position of the array. In [1,4,5,2,3] with k = 3, the value 1 is only found after scanning all the way to the beginning. The algorithm correctly continues until every required value has been discovered and returns the full array length when necessary.

Edge Case 5: Required Values Already Near the End

If all required values appear in the suffix of the array, the answer can be very small. For example, [6,5,4,3,2,1] with k = 3 requires only three operations. Because the algorithm scans from the end and stops immediately when all required values are found, it naturally returns the minimum possible number of operations.