Minimum Operations to Collect Elements

Difficulty: Easy | Acceptance: 62.30% | Paid: No

Topics: Array, Hash Table, Bit Manipulation

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. An element x is added to the collection if it is in the range [1, k] and it is not already in the collection.

• Examples
• Constraints
• Hash Set
• Boolean Frequency Array
• Bit Manipulation

Examples

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.

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, 2, 3, 4, and 5. Hence, the answer is 5.

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, 2, and 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.

Hash Set

Intuition

To collect all numbers from 1 to k, we should iterate from the end of the array (simulating the removal of the last element) and keep track of the unique numbers we’ve encountered that are less than or equal to k.

Steps

• Initialize an empty set to store the unique elements found that are in the range [1, k].
• Initialize a counter for the number of operations.
• Iterate through the array starting from the last element (index n-1) down to the first element.
• For each element, increment the operation count.
• If the current element is less than or equal to k, add it to the set.
• Check if the size of the set has reached k. If it has, it means we have collected all numbers from 1 to k.
• Return the current operation count as soon as the set size equals k.

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        seen = set()
        ops = 0
        for i in range(len(nums) - 1, -1, -1):
            ops += 1
            if nums[i] <= k:
                seen.add(nums[i])
            if len(seen) == k:
                return ops
        return ops

Complexity

• Time: O(n) where n is the length of the array. In the worst case, we might iterate through the entire array.
• Space: O(k) to store the unique elements in the set.
• Notes: The set operations (add, size) are O(1) on average.

Boolean Frequency Array

Intuition

Since the range of numbers we care about is small (1 to k), we can use a boolean array instead of a hash set to track which numbers have been collected.

Steps

• Create a boolean array ‘seen’ of size k + 1, initialized to false.
• Initialize a variable ‘count’ to 0 to track how many unique elements from [1, k] we have found.
• Iterate from the end of the ‘nums’ array.
• For each element ‘nums[i]’, if ‘nums[i] <= k’ and ‘seen[nums[i]]’ is false:
• Mark ‘seen[nums[i]]’ as true and increment ‘count’.
• If ‘count’ reaches k, return the number of elements processed so far (n - i).

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        seen = [False] * (k + 1)
        count = 0
        n = len(nums)
        for i in range(n - 1, -1, -1):
            val = nums[i]
            if val <= k and not seen[val]:
                seen[val] = True
                count += 1
            if count == k:
                return n - i
        return n

Complexity

• Time: O(n) where n is the length of the array.
• Space: O(k) to store the boolean array.
• Notes: This approach is slightly more memory-efficient than a Hash Set because it avoids the overhead of hash table management.

Bit Manipulation

Intuition

Since k is small (up to 50), we can represent the set of collected numbers using a single 64-bit integer (bitmask). Each bit i represents whether the number i has been collected.

Steps

• Initialize a bitmask ‘mask’ to 0.
• Define a ‘target’ mask where bits 1 through k are set to 1. This can be calculated as (2^(k+1) - 2).
• Iterate from the end of the array.
• If the current element ‘nums[i]’ is less than or equal to k, set the corresponding bit in the mask: mask |= (1 << nums[i]).
• After each update, check if ‘mask’ equals ‘target’. If it does, return the number of operations performed.
• Note: In JavaScript, bitwise operations are 32-bit, so BigInt must be used for k up to 50.

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        mask = 0
        target = (1 << (k + 1)) - 2
        n = len(nums)
        for i in range(n - 1, -1, -1):
            if nums[i] <= k:
                mask |= (1 << nums[i])
            if mask == target:
                return n - i
        return n

Complexity

• Time: O(n) where n is the length of the array.
• Space: O(1) as we only use a few variables and a single bitmask integer.
• Notes: This is the most space-efficient approach. It works because k is constrained to 50, fitting within a 64-bit integer.