Minimum Operations to Collect Elements

Easy
608.

Minimum Operations to Collect Elements

Minimum Operations to Collect Elements is an easy coding problem on arrays, hash table and simulation, asked in Infosys and Zoho interviews.

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 <= 50
  • 1 <= nums[i] <= nums.length
  • 1 <= k <= nums.length
  • The input guarantees 1 through k all appear.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minOperations = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 50
  • 1 <= nums[i] <= nums.length
  • 1 <= k <= nums.length
  • The input guarantees 1 through k all appear.

Hints for Minimum Operations to Collect Elements

  1. Hint 1

    Operations always come off the back, so walk the array from right to left.

  2. Hint 2

    Only values in 1..k matter; anything larger is collected but never helps.

  3. Hint 3

    Stop the moment you have seen k distinct 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

  1. Walk i from n - 1 down to 0, counting operations as n - i.
  2. If nums[i] <= k and it has not been seen, mark it and increment got.
  3. As soon as got == k, return n - 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 k towards the goal — they never satisfy the requirement.
  • Counting duplicates twice; the goal is k distinct 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