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 theminimum number of operations needed to collect elements 1, 2, ..., k.

Examples

Example 1

1
2
3

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

1
2
3

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

1
2
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 <= 50
  • 1 <= nums[i] <= nums.length
  • 1 <= k <= nums.length
  • The input is generated such that you can collect elements 1, 2, ..., k.

Solution

Method 1 – Hash Set & Reverse Scan

Intuition

We need to collect all elements from 1 to k by removing elements from the end. The minimum number of operations is the number of steps needed to see all k elements when scanning from the end.

Approach

  1. Initialize a set to track collected elements.
  2. Scan nums from the end, adding each element to the set if it is in [1, k].
  3. Stop when the set contains all k elements.
  4. The answer is the number of steps taken.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#include <vector>
#include <unordered_set>
using namespace std;
class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        unordered_set<int> s;
        int ans = 0;
        for (int i = nums.size() - 1; i >= 0; --i) {
            if (1 <= nums[i] && nums[i] <= k) s.insert(nums[i]);
            ++ans;
            if (s.size() == k) break;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func minOperations(nums []int, k int) int {
    s := make(map[int]struct{})
    ans := 0
    for i := len(nums) - 1; i >= 0; i-- {
        if 1 <= nums[i] && nums[i] <= k {
            s[nums[i]] = struct{}{}
        }
        ans++
        if len(s) == k {
            break
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

import java.util.*;
class Solution {
    public int minOperations(int[] nums, int k) {
        Set<Integer> s = new HashSet<>();
        int ans = 0;
        for (int i = nums.length - 1; i >= 0; --i) {
            if (1 <= nums[i] && nums[i] <= k) s.add(nums[i]);
            ++ans;
            if (s.size() == k) break;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun minOperations(nums: IntArray, k: Int): Int {
        val s = mutableSetOf<Int>()
        var ans = 0
        for (i in nums.indices.reversed()) {
            if (nums[i] in 1..k) s.add(nums[i])
            ans++
            if (s.size == k) break
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def minOperations(self, nums: list[int], k: int) -> int:
        s = set()
        ans: int = 0
        for v in reversed(nums):
            if 1 <= v <= k:
                s.add(v)
            ans += 1
            if len(s) == k:
                break
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

use std::collections::HashSet;
impl Solution {
    pub fn min_operations(nums: Vec<i32>, k: i32) -> i32 {
        let mut s = HashSet::new();
        let mut ans = 0;
        for &v in nums.iter().rev() {
            if 1 <= v && v <= k {
                s.insert(v);
            }
            ans += 1;
            if s.len() == k as usize {
                break;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    minOperations(nums: number[], k: number): number {
        const s = new Set<number>();
        let ans = 0;
        for (let i = nums.length - 1; i >= 0; --i) {
            if (1 <= nums[i] && nums[i] <= k) s.add(nums[i]);
            ++ans;
            if (s.size === k) break;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — We scan the array once from the end.
  • 🧺 Space complexity: O(k) — For the set of collected elements.