You are given an array nums of positive integers and an integer k.
In one operation, you can remove the last element of the array and add it to your collection.
Return the minimum number of operations needed to collect elements 1, 2, ..., k.
Example 1:
Input: nums = [3,1,5,4,2], k = 2 Output: 4 Explanation: 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 Explanation: 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 Explanation: 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 <= 501 <= nums[i] <= nums.length1 <= k <= nums.length1, 2, ..., k.Problem Overview: You are given an integer array nums and an integer k. Starting from the end of the array, you remove elements one by one. The goal is to collect every value from 1 to k at least once. The task is to return the minimum number of operations required to achieve this.
Approach 1: Reverse Collection (O(n) time, O(k) space)
The most direct strategy is to scan the array from right to left while collecting values between 1 and k. Maintain a set (or hash structure) that stores which required elements have been seen so far. Each step represents one operation since you are effectively removing an element from the end. When you encounter a value <= k, add it to the set. As soon as the set size becomes k, you have collected all required elements and can return the number of processed elements.
This approach works because removing elements from the end is equivalent to iterating the array in reverse. Hash lookups and insertions are constant time, so the overall complexity remains linear. The method relies on basic array traversal combined with fast membership checks using a hash table.
Approach 2: Decremental Loop Through the Array (O(n) time, O(k) space)
Another implementation tracks how many required elements are still missing instead of storing them all explicitly. Start with a counter remaining = k and a boolean array (or bitmask) to mark which values from 1..k have been collected. Traverse the array from the end and check each value. If the number is within the required range and hasn't been seen before, mark it and decrement remaining.
Once remaining reaches zero, you have collected all elements and can return the number of operations performed. This version replaces a dynamic set with a fixed-size tracking structure, which can also be implemented using bit manipulation for very compact state tracking.
The logic remains the same as the previous approach: iterate backward, track required values, and stop once every number from 1 to k appears. Both solutions run in linear time and scan the array only once.
Recommended for interviews: The reverse traversal with a hash set is the clearest explanation and easiest to implement under time pressure. It demonstrates understanding of array traversal and constant‑time lookups. The decremental tracking version is slightly more optimized and shows stronger control over state management, but interviewers usually accept either once the reverse‑scan insight is explained.
This approach processes the array from the end to the start and uses a set to track the unique elements collected. We iterate from the last element backward, updating the set, until we've collected all elements from 1 through k.
The code uses a boolean array to keep track of collected elements and loops backward over nums to find when all elements 1 through k are collected. The loop stops once all necessary elements are in the collection.
Time Complexity: O(n), where n is the length of the nums array, as we traverse the array once.
Space Complexity: O(k), for storing elements up to k in the boolean array.
Instead of starting at the end and using a set, consider decrementing k directly and track how many of these elements ('1' to current 'k') have been collected as you iterate from the end.
The C solution iterates backward through nums. Each time it finds a number ≤ k, it decrements k. The loop stops when k reaches zero, indicating all numbers have been collected.
Time Complexity: O(n), where n is the length of nums.
Space Complexity: O(1), as no additional collections are used.
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.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(k).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Reverse Collection | Time Complexity: O(n), where n is the length of the nums array, as we traverse the array once. |
| Decremental Loop Through the Array | Time Complexity: O(n), where n is the length of nums. |
| Traverse in Reverse Order | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Reverse Collection with Hash Set | O(n) | O(k) | General case; easiest to implement and explain in interviews |
| Decremental Loop with Boolean/Bit Tracking | O(n) | O(k) | When you want tighter control over memory or prefer array/bit tracking instead of a hash set |
LeetCode#2869 Minimum Operations to Collect Elements - Python • CodeJulian • 987 views views
Watch 9 more video solutions →Practice Minimum Operations to Collect Elements with our built-in code editor and test cases.
Practice on FleetCode