Minimum Operations to Collect Elements
EasyPrompt
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.length- The input is generated such that you can collect elements
1, 2, ..., k.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach simulates the process by trying every possible number of operations, from 1 up to the length of the array. For each number of operations i, it checks if collecting the last i elements from the array is sufficient to gather all numbers from 1 to k. The first value of i for which this condition is met is the minimum number of operations.
Algorithm
- For each possible number of operations,
ops, from 1 to the length of the arrayN:- Create a temporary collection (e.g., a
HashSet) of the lastopselements from thenumsarray. - Check if this collection contains all integers from
1tok.- To do this, iterate from
j = 1tokand verify thatjis in the collection.
- To do this, iterate from
- If all
kintegers are present,opsis the minimum number of operations required. Returnops.
- Create a temporary collection (e.g., a
- If the loop finishes, it means a solution was found at
ops = N(guaranteed by the problem statement).
Walkthrough
The brute-force method directly translates the problem's requirement into a straightforward, albeit inefficient, algorithm. We iterate through all possible answers for the number of operations, starting from 1. For each potential answer, ops, we simulate the process: we take the last ops elements from the nums array and put them into a set to easily check for existence. Then, we verify if this set contains all the numbers we need, i.e., every integer from 1 to k. The first value of ops that satisfies this condition is, by definition, the minimum number of operations, and we can return it immediately.
import java.util.HashSet;import java.util.List;import java.util.Set; class Solution { public int minOperations(List<Integer> nums, int k) { int n = nums.size(); for (int ops = 1; ops <= n; ops++) { Set<Integer> collected = new HashSet<>(); // Collect the last 'ops' elements for (int i = 0; i < ops; i++) { collected.add(nums.get(n - 1 - i)); } // Check if all numbers from 1 to k are collected boolean allFound = true; for (int target = 1; target <= k; target++) { if (!collected.contains(target)) { allFound = false; break; } } if (allFound) { return ops; } } return n; // Should not be reached given the problem constraints }}Complexity
Time
O(N * (N + K)), where N is the length of `nums`. The outer loop runs up to N times. Inside, creating the set takes O(ops) (at most O(N)), and checking for k elements takes O(K). This results in a quadratic time complexity.
Space
O(N), where N is the number of elements in `nums`. In the worst case, the `HashSet` might store all N elements if `ops` goes up to N.
Trade-offs
Pros
Conceptually simple and easy to understand as it directly models the question.
Guaranteed to find the correct answer because it checks possibilities in increasing order of operations.
Cons
Highly inefficient due to redundant computations. The collection of removed elements is rebuilt from scratch in every iteration of the outer loop.
The time complexity of O(N * (N + K)) is significantly worse than optimal approaches, making it unsuitable for larger constraints.
A more efficient approach is to realize that we are always taking elements from the end of the array. Instead of re-checking for each possible number of operations, we can iterate backward from the end of the array, simulating the process one operation at a time. We use a HashSet to keep track of the unique numbers from 1 to k that we have collected so far.
Algorithm
- Initialize an empty
HashSetcalledseento store the required numbers found so far. - Initialize an
operationscounter to 0. - Iterate through the
numsarray in reverse, from the last element (i = nums.length - 1) to the first (i = 0). - In each step:
- Increment the
operationscounter. - Get the current element,
num. - If
numis in the range[1, k], add it to theseenset. - Check if the size of the
seenset has become equal tok. - If it has, we have collected all necessary elements. Return the current
operationscount.
- Increment the
Walkthrough
This approach correctly identifies that the order of operations is fixed: we always process elements from right to left. Therefore, we can simulate this process in a single pass. We iterate backward through the nums array, counting each step as one operation. We use a HashSet to efficiently keep track of which of the target numbers (1 through k) we have encountered. When we see a number that is within this target range, we add it to our set. Since a set only stores unique elements, we don't need to worry about duplicates. We continue this process until the size of our set equals k, which signifies that we have collected one of each required number. At that point, the total number of elements we have processed from the end is our answer.
import java.util.HashSet;import java.util.List;import java.util.Set; class Solution { public int minOperations(List<Integer> nums, int k) { Set<Integer> seen = new HashSet<>(); int operations = 0; for (int i = nums.size() - 1; i >= 0; i--) { operations++; int num = nums.get(i); if (num >= 1 && num <= k) { seen.add(num); } if (seen.size() == k) { return operations; } } return operations; // Should not be reached given problem constraints }}Complexity
Time
O(N), where N is the length of `nums`. We iterate through the array at most once. HashSet operations (add, size) take O(1) on average.
Space
O(k), as the `HashSet` will store at most `k` distinct elements.
Trade-offs
Pros
Efficient O(N) time complexity as it only requires a single pass through the array.
Good space complexity of O(k), which is optimal as we need to track k elements.
The logic is clean and directly follows the operational process.
Cons
Uses a
HashSet, which has some memory and performance overhead due to hashing compared to a simple boolean array.
This approach is a slight optimization of the HashSet method. Since the target elements are a contiguous range of integers from 1 to k, we can use a boolean array instead of a HashSet to track which elements have been collected. This can be slightly more performant due to direct array indexing and better memory locality.
Algorithm
- Initialize a boolean array
foundof sizek + 1to allfalse. - Initialize
foundCount = 0to track the number of unique required elements found. - Initialize
operations = 0. - Iterate
ifromnums.length - 1down to0:- Increment
operations. - Let
num = nums.get(i). - If
1 <= num <= kandfound[num]isfalse:- Set
found[num]totrue. - Increment
foundCount.
- Set
- If
foundCountequalsk, returnoperations.
- Increment
Walkthrough
This is the most optimized approach for the given constraints. It builds upon the single-pass idea but replaces the HashSet with a more efficient data structure for this specific problem: a boolean array. We create a boolean array found of size k+1 to serve as a checklist for the numbers 1 to k. We also maintain a counter foundCount for the number of unique required items we've collected. As we iterate backward through nums, we increment our operations count. If we encounter a number num that is between 1 and k and we haven't seen it before (found[num] is false), we mark it as found (found[num] = true) and increment foundCount. The moment foundCount reaches k, we have found our last required number, and we can immediately return the current operations count.
import java.util.List; class Solution { public int minOperations(List<Integer> nums, int k) { boolean[] found = new boolean[k + 1]; int foundCount = 0; int operations = 0; for (int i = nums.size() - 1; i >= 0; i--) { operations++; int num = nums.get(i); if (num >= 1 && num <= k && !found[num]) { found[num] = true; foundCount++; } if (foundCount == k) { return operations; } } return operations; // Should not be reached given problem constraints }}Complexity
Time
O(N), where N is the length of `nums`. We perform a single pass over the array, and all operations inside the loop are O(1).
Space
O(k) to store the boolean array.
Trade-offs
Pros
Optimal time complexity of O(N) and space complexity of O(k).
Most performant solution in practice due to using a simple array, which avoids hashing overhead and benefits from better cache performance.
Low memory footprint.
Cons
This optimization is specific to problems where the target elements are a dense range of small positive integers, making it slightly less general than a HashSet.
Solutions
Solution
class Solution {public int minOperations(List<Integer> nums, int k) { boolean[] isAdded = new boolean[k]; int n = nums.size(); int count = 0; for (int i = n - 1;; i--) { if (nums.get(i) > k || isAdded[nums.get(i) - 1]) { continue; } isAdded[nums.get(i) - 1] = true; count++; if (count == k) { return n - i; } } }}class Solution {public: int minOperations(vector<int> &nums, int k) { int n = nums.size(); vector<bool> isAdded(n); int count = 0; for (int i = n - 1;; --i) { if (nums[i] > k || isAdded[nums[i] - 1]) { continue; } isAdded[nums[i] - 1] = true; if (++count == k) { return n - i; } } }};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 - iVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.