Minimum Operations to Collect Elements - Practice Coding Problems

Minimum Operations to Collect Elements - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [3,1,5,4,2], k = 2

› Output: 4

💡 Note: Working backwards: remove 2 (have {2}), remove 4 (have {2}), remove 5 (have {2}), remove 1 (have {1,2}). We need 4 operations to collect both 1 and 2.

Example 2 — Numbers at End

$ Input: nums = [3,1,3,2,2], k = 1

› Output: 1

💡 Note: Only need to collect number 1. Working backwards, we don't find 1 in the last element (2), but we only need k=1 distinct numbers from 1 to k, so we need more operations until we find 1.

Example 3 — All Numbers Present

$ Input: nums = [2,1,3], k = 2

› Output: 3

💡 Note: Working backwards: remove 3 (not needed), remove 1 (have {1}), remove 2 (have {1,2}). Need 3 operations total.

Constraints

1 ≤ nums.length ≤ 1000
1 ≤ k ≤ nums.length
1 ≤ nums[i] ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Array [3,1,5,4,2] and k=2 (need to collect 1,2)

Process

Remove from end: 2→4→5→1, stop when we have {1,2}

Output

Return 4 (minimum operations needed)

Key Takeaway

🎯 Key Insight: Work backwards from the end and stop as soon as you've collected all required numbers

Asked in

M Meta 15 A Amazon 12 G Google 8

The key insight is to work backwards from the end of the array, collecting elements until we have all numbers from 1 to k. Best approach uses a single pass with early termination. Time: O(n), Space: O(k)

Common Approaches

Approach	Time	Space	Notes
✓ Single Pass from End	O(n)	O(k)	Work backwards from end, stop when we've collected all numbers 1 to k
Brute Force - Try All Combinations	O(n²)	O(k)	Generate all possible subsequences and find minimum length containing 1 to k

Single Pass from End — Algorithm Steps

Step 1: Start from the last element and work backwards
Step 2: Track collected numbers from 1 to k using a set
Step 3: Return operation count when we have all numbers 1 to k

Visualization

Tap to expand

Step-by-Step Walkthrough

Start from End

Begin at last element, track what we collect

Move Backwards

Process each element, add valid ones to set

Stop Early

Return as soon as we have all k numbers

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int solution(int* nums, int numsSize, int k) {
    bool collected[100001] = {false};
    int count = 0;
    int operations = 0;
    
    for (int i = numsSize - 1; i >= 0; i--) {
        operations++;
        if (nums[i] <= k && !collected[nums[i]]) {
            collected[nums[i]] = true;
            count++;
        }
        if (count == k) {
            return operations;
        }
    }
    
    return operations;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int k;
    scanf("%d", &k);
    
    printf("%d\n", solution(nums, numsSize, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass from end of array, each element processed once

✓ Linear Growth

Space Complexity

O(k)

Set to track collected numbers, maximum size k

✓ Linear Space

15.0K Views

Medium Frequency

~15 min Avg. Time

450 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Single Pass from End — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler