Get started

Minimum Operations to Collect Elements — Easy Problem & Solution

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.

  • 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.

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)

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue