# Minimum Operations to Collect Elements
**Difficulty:** EASY
[External](https://leetcode.com/problems/minimum-operations-to-collect-elements)
Canonical: https://scaleengineer.com/dsa/problems/minimum-operations-to-collect-elements
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array, Hash Table
**Companies:** [Deutsche Bank](https://scaleengineer.com/companies/deutsche-bank)
---
## 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`.

**Example 1:**

**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:**

**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:**

**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`.

# Approaches
## Brute-Force Simulation
This approach simulates the process by trying every possible number of operations, from 1 up to the length of the array. For each number of operations `i`, it checks if collecting the last `i` elements from the array is sufficient to gather all numbers from 1 to `k`. The first value of `i` for which this condition is met is the minimum number of operations.
**Time:** O(N * (N + K)), where N is the length of `nums`. The outer loop runs up to N times. Inside, creating the set takes O(ops) (at most O(N)), and checking for k elements takes O(K). This results in a quadratic time complexity. · **Space:** O(N), where N is the number of elements in `nums`. In the worst case, the `HashSet` might store all N elements if `ops` goes up to N.
**Pros:** Conceptually simple and easy to understand as it directly models the question.; Guaranteed to find the correct answer because it checks possibilities in increasing order of operations.
**Cons:** Highly inefficient due to redundant computations. The collection of removed elements is rebuilt from scratch in every iteration of the outer loop.; The time complexity of O(N * (N + K)) is significantly worse than optimal approaches, making it unsuitable for larger constraints.
### Explanation
The brute-force method directly translates the problem's requirement into a straightforward, albeit inefficient, algorithm. We iterate through all possible answers for the number of operations, starting from 1. For each potential answer, `ops`, we simulate the process: we take the last `ops` elements from the `nums` array and put them into a set to easily check for existence. Then, we verify if this set contains all the numbers we need, i.e., every integer from 1 to `k`. The first value of `ops` that satisfies this condition is, by definition, the minimum number of operations, and we can return it immediately.

```java
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public int minOperations(List<Integer> nums, int k) {
        int n = nums.size();
        for (int ops = 1; ops <= n; ops++) {
            Set<Integer> collected = new HashSet<>();
            // Collect the last 'ops' elements
            for (int i = 0; i < ops; i++) {
                collected.add(nums.get(n - 1 - i));
            }

            // Check if all numbers from 1 to k are collected
            boolean allFound = true;
            for (int target = 1; target <= k; target++) {
                if (!collected.contains(target)) {
                    allFound = false;
                    break;
                }
            }

            if (allFound) {
                return ops;
            }
        }
        return n; // Should not be reached given the problem constraints
    }
}
```
### Algorithm
- For each possible number of operations, `ops`, from 1 to the length of the array `N`:
  - Create a temporary collection (e.g., a `HashSet`) of the last `ops` elements from the `nums` array.
  - Check if this collection contains all integers from `1` to `k`.
    - To do this, iterate from `j = 1` to `k` and verify that `j` is in the collection.
  - If all `k` integers are present, `ops` is the minimum number of operations required. Return `ops`.
- If the loop finishes, it means a solution was found at `ops = N` (guaranteed by the problem statement).

## Single Pass from Right with a HashSet
A more efficient approach is to realize that we are always taking elements from the end of the array. Instead of re-checking for each possible number of operations, we can iterate backward from the end of the array, simulating the process one operation at a time. We use a `HashSet` to keep track of the unique numbers from `1` to `k` that we have collected so far.
**Time:** O(N), where N is the length of `nums`. We iterate through the array at most once. HashSet operations (add, size) take O(1) on average. · **Space:** O(k), as the `HashSet` will store at most `k` distinct elements.
**Pros:** Efficient O(N) time complexity as it only requires a single pass through the array.; Good space complexity of O(k), which is optimal as we need to track k elements.; The logic is clean and directly follows the operational process.
**Cons:** Uses a `HashSet`, which has some memory and performance overhead due to hashing compared to a simple boolean array.
### Explanation
This approach correctly identifies that the order of operations is fixed: we always process elements from right to left. Therefore, we can simulate this process in a single pass. We iterate backward through the `nums` array, counting each step as one operation. We use a `HashSet` to efficiently keep track of which of the target numbers (`1` through `k`) we have encountered. When we see a number that is within this target range, we add it to our set. Since a set only stores unique elements, we don't need to worry about duplicates. We continue this process until the size of our set equals `k`, which signifies that we have collected one of each required number. At that point, the total number of elements we have processed from the end is our answer.

```java
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public int minOperations(List<Integer> nums, int k) {
        Set<Integer> seen = new HashSet<>();
        int operations = 0;
        for (int i = nums.size() - 1; i >= 0; i--) {
            operations++;
            int num = nums.get(i);
            if (num >= 1 && num <= k) {
                seen.add(num);
            }
            if (seen.size() == k) {
                return operations;
            }
        }
        return operations; // Should not be reached given problem constraints
    }
}
```
### Algorithm
- Initialize an empty `HashSet` called `seen` to store the required numbers found so far.
- Initialize an `operations` counter to 0.
- Iterate through the `nums` array in reverse, from the last element (`i = nums.length - 1`) to the first (`i = 0`).
- In each step:
  - Increment the `operations` counter.
  - Get the current element, `num`.
  - If `num` is in the range `[1, k]`, add it to the `seen` set.
  - Check if the size of the `seen` set has become equal to `k`.
  - If it has, we have collected all necessary elements. Return the current `operations` count.

## Optimized Single Pass with a Boolean Array
This approach is a slight optimization of the HashSet method. Since the target elements are a contiguous range of integers from `1` to `k`, we can use a boolean array instead of a `HashSet` to track which elements have been collected. This can be slightly more performant due to direct array indexing and better memory locality.
**Time:** O(N), where N is the length of `nums`. We perform a single pass over the array, and all operations inside the loop are O(1). · **Space:** O(k) to store the boolean array.
**Pros:** Optimal time complexity of O(N) and space complexity of O(k).; Most performant solution in practice due to using a simple array, which avoids hashing overhead and benefits from better cache performance.; Low memory footprint.
**Cons:** This optimization is specific to problems where the target elements are a dense range of small positive integers, making it slightly less general than a HashSet.
### Explanation
This is the most optimized approach for the given constraints. It builds upon the single-pass idea but replaces the `HashSet` with a more efficient data structure for this specific problem: a boolean array. We create a boolean array `found` of size `k+1` to serve as a checklist for the numbers 1 to `k`. We also maintain a counter `foundCount` for the number of unique required items we've collected. As we iterate backward through `nums`, we increment our `operations` count. If we encounter a number `num` that is between 1 and `k` and we haven't seen it before (`found[num]` is false), we mark it as found (`found[num] = true`) and increment `foundCount`. The moment `foundCount` reaches `k`, we have found our last required number, and we can immediately return the current `operations` count.

```java
import java.util.List;

class Solution {
    public int minOperations(List<Integer> nums, int k) {
        boolean[] found = new boolean[k + 1];
        int foundCount = 0;
        int operations = 0;
        for (int i = nums.size() - 1; i >= 0; i--) {
            operations++;
            int num = nums.get(i);
            if (num >= 1 && num <= k && !found[num]) {
                found[num] = true;
                foundCount++;
            }
            if (foundCount == k) {
                return operations;
            }
        }
        return operations; // Should not be reached given problem constraints
    }
}
```
### Algorithm
- Initialize a boolean array `found` of size `k + 1` to all `false`.
- Initialize `foundCount = 0` to track the number of unique required elements found.
- Initialize `operations = 0`.
- Iterate `i` from `nums.length - 1` down to `0`:
  - Increment `operations`.
  - Let `num = nums.get(i)`.
  - If `1 <= num <= k` and `found[num]` is `false`:
    - Set `found[num]` to `true`.
    - Increment `foundCount`.
  - If `foundCount` equals `k`, return `operations`.

# Solutions
### Java

```java
class Solution {
public
  int minOperations(List<Integer> nums, int k) {
    boolean[] isAdded = new boolean[k];
    int n = nums.size();
    int count = 0;
    for (int i = n - 1;; i--) {
      if (nums.get(i) > k || isAdded[nums.get(i) - 1]) {
        continue;
      }
      isAdded[nums.get(i) - 1] = true;
      count++;
      if (count == k) {
        return n - i;
      }
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minOperations(vector<int> &nums, int k) {
    int n = nums.size();
    vector<bool> isAdded(n);
    int count = 0;
    for (int i = n - 1;; --i) {
      if (nums[i] > k || isAdded[nums[i] - 1]) {
        continue;
      }
      isAdded[nums[i] - 1] = true;
      if (++count == k) {
        return n - i;
      }
    }
  }
};

```

### Python

```python
class Solution:
    def minOperations(self, nums: List[int], k: int) -> int: is_added = [False] * k count = 0 n = len(nums) for i in range(n - 1, - 1, - 1): if nums[i] > k or is_added[nums[i] - 1]: continue is_added[nums[i] - 1] = True count += 1 if count == k: return n - i

```