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.
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; } } }}Video 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.