Minimum Operations to Collect Elements — Problem & Solution
Minimum Operations to Collect Elements solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Minimum Operations to Collect Elements is an easy coding problem on arrays, hash table and simulation, asked in Infosys and Zoho interviews.
- Difficulty: Easy
- Topics: Arrays, Hash Table, Simulation
- Asked at: Infosys, Zoho
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array nums of positive integers and an integer k.
One operation removes the last element of nums and puts it into your collection. Return the minimum number of operations after which your collection contains every number from 1 to k.
The input always makes this possible.
Example 1
Input: nums = [3,1,5,4,2], k = 2
Output: 4
Explanation: Removing 2, 4, 5, 1 collects both 1 and 2 after four operations.
Example 2
Input: nums = [3,1,5,4,2], k = 5
Output: 5
Explanation: All five elements are needed.
Example 3
Input: nums = [3,2,5,3,1], k = 3
Output: 4
Explanation: Removing 1, 3, 5, 2 covers 1, 2 and 3.
Constraints
1 <= nums.length <= 501 <= nums[i] <= nums.length1 <= k <= nums.lengthThe input guarantees 1 through k all appear.
Hints for Minimum Operations to Collect Elements
Hint 1
Operations always come off the back, so walk the array from right to left.
Hint 2
Only values in
1..kmatter; anything larger is collected but never helps.Hint 3
Stop the moment you have seen
kdistinct qualifying values — the count of steps so far is the answer.
How to solve Minimum Operations to Collect Elements
The removal order is fixed — last to first — so there is nothing to choose. Scan right to left and stop at the first prefix (from the right) that covers 1..k.
Approach
- Walk
ifromn - 1down to0, counting operations asn - i. - If
nums[i] <= kand it has not been seen, mark it and incrementgot. - As soon as
got == k, returnn - i.
Why it works
Every strategy performs the same removals in the same order, so the cost of collecting 1..k is exactly the position of the earliest suffix containing all of them. Scanning right to left finds that suffix at its first occurrence, which is minimal by construction.
Complexity
- Time —
O(n) - Space —
O(k)
Pitfalls
- Counting values greater than
ktowards the goal — they never satisfy the requirement. - Counting duplicates twice; the goal is
kdistinct values.
Reference solution
Python
from typing import List
def minOperations(nums: List[int], k: int) -> int:
have = set()
for i in range(len(nums) - 1, -1, -1):
if nums[i] <= k:
have.add(nums[i])
if len(have) == k:
return len(nums) - i
return len(nums)Java
public static int minOperations(int[] nums, int k) {
boolean[] have = new boolean[k + 1];
int got = 0;
for (int i = nums.length - 1; i >= 0; i--) {
int v = nums[i];
if (v <= k && !have[v]) { have[v] = true; got++; }
if (got == k) return nums.length - i;
}
return nums.length;
}C++
int minOperations(vector<int>& nums, int k) {
vector<bool> have(k + 1, false);
int got = 0;
for (int i = (int) nums.size() - 1; i >= 0; i--) {
int v = nums[i];
if (v <= k && !have[v]) { have[v] = true; got++; }
if (got == k) return (int) nums.size() - i;
}
return (int) nums.size();
}JavaScript
var minOperations = function(nums, k) {
var have = {}, got = 0;
for (var i = nums.length - 1; i >= 0; i--) {
var v = nums[i];
if (v <= k && have[String(v)] !== true) { have[String(v)] = true; got++; }
if (got === k) return nums.length - i;
}
return nums.length;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets