# Find the Largest Almost Missing Integer
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-the-largest-almost-missing-integer)
Canonical: https://scaleengineer.com/dsa/problems/find-the-largest-almost-missing-integer
**Data structures:** Array, Hash Table
---
## Problem
You are given an integer array `nums` and an integer `k`.

An integer `x` is **almost missing** from `nums` if `x` appears in _exactly_ one subarray of size `k` within `nums`.

Return the **largest** **almost missing** integer from `nums`. If no such integer exists, return `-1`.

A **subarray** is a contiguous sequence of elements within an array. 

**Example 1:**

**Input:** nums = \[3,9,2,1,7\], k = 3

**Output:** 7

**Explanation:**

* 1 appears in 2 subarrays of size 3: `[9, 2, 1]` and `[2, 1, 7]`.
* 2 appears in 3 subarrays of size 3: `[3, 9, 2]`, `[9, 2, 1]`, `[2, 1, 7]`.
* 3 appears in 1 subarray of size 3: `[3, 9, 2]`.
* 7 appears in 1 subarray of size 3: `[2, 1, 7]`.
* 9 appears in 2 subarrays of size 3: `[3, 9, 2]`, and `[9, 2, 1]`.

We return 7 since it is the largest integer that appears in exactly one subarray of size `k`.

**Example 2:**

**Input:** nums = \[3,9,7,2,1,7\], k = 4

**Output:** 3

**Explanation:**

* 1 appears in 2 subarrays of size 4: `[9, 7, 2, 1]`, `[7, 2, 1, 7]`.
* 2 appears in 3 subarrays of size 4: `[3, 9, 7, 2]`, `[9, 7, 2, 1]`, `[7, 2, 1, 7]`.
* 3 appears in 1 subarray of size 4: `[3, 9, 7, 2]`.
* 7 appears in 3 subarrays of size 4: `[3, 9, 7, 2]`, `[9, 7, 2, 1]`, `[7, 2, 1, 7]`.
* 9 appears in 2 subarrays of size 4: `[3, 9, 7, 2]`, `[9, 7, 2, 1]`.

We return 3 since it is the largest and only integer that appears in exactly one subarray of size `k`.

**Example 3:**

**Input:** nums = \[0,0\], k = 1

**Output:** \-1

**Explanation:**

There is no integer that appears in only one subarray of size 1.

**Constraints:**

* `1 <= nums.length <= 50`
* `0 <= nums[i] <= 50`
* `1 <= k <= nums.length`

# Approaches
## Brute-Force Iteration
This approach directly translates the problem definition into code. It checks every possible number from the allowed range (0 to 50) to see if it meets the 'almost missing' criteria. For each number, it iterates through all subarrays of size `k` and counts how many of them contain that number. If the count is one, we've found an almost missing integer. By checking numbers in descending order, the first one we find is guaranteed to be the largest.
**Time:** O(V * n * k), where `V` is the range of values (51 in this case), `n` is the length of `nums`, and `k` is the subarray size. Since `V` is a small constant, the complexity is effectively O(n * k). · **Space:** O(1), as we only use a few variables to keep track of counts and loop indices.
**Pros:** Very simple to understand and implement.; Minimal space complexity.
**Cons:** The time complexity of O(V * n * k) can be slow if the range of values (V) or the array size (n) were large.; It repeatedly scans subarrays, which is inefficient.
### Explanation
The brute-force method involves a straightforward, nested-loop structure. The outermost loop iterates through potential candidates for the almost missing integer, from 50 down to 0. For each candidate `x`, an inner loop iterates through all `n-k+1` subarrays of size `k`. A third, innermost loop then scans the current subarray to check for the presence of `x`. If `x` is found, a counter for the number of windows containing `x` is incremented. If, after checking all windows, this counter is exactly 1, we have found our answer.

```java
class Solution {
    public int findLargestAlmostMissingInteger(int[] nums, int k) {
        int n = nums.length;
        // Iterate from the largest possible value down to 0
        for (int x = 50; x >= 0; x--) {
            int windowCount = 0;
            // Iterate through all subarrays of size k
            for (int i = 0; i <= n - k; i++) {
                boolean found = false;
                // Check if x is in the current subarray
                for (int j = i; j < i + k; j++) {
                    if (nums[j] == x) {
                        found = true;
                        break;
                    }
                }
                if (found) {
                    windowCount++;
                }
            }
            // If x appeared in exactly one window, it's the largest one found so far
            if (windowCount == 1) {
                return x;
            }
        }
        return -1;
    }
}
```
### Algorithm
*   Initialize a variable `max_almost_missing` to -1 to store the result.
*   Iterate through all possible integer values `x` that can appear in the array. Given the constraints, this range is from 50 down to 0. Iterating downwards ensures that the first almost missing integer we find is the largest one.
*   For each value `x`, initialize a counter `window_count` to 0.
*   Iterate through all possible starting positions `i` of a subarray of size `k`, from `0` to `nums.length - k`.
*   For each subarray starting at `i`, check if `x` is present within `nums[i]` to `nums[i+k-1]`.
*   If `x` is found in the current subarray, increment `window_count`.
*   After checking all subarrays, if `window_count` is exactly 1, it means `x` is an almost missing integer. Since we are iterating from the largest possible value downwards, this `x` is the largest one. Return `x` immediately.
*   If the loops complete without finding any such integer, it means no almost missing integer exists. Return the initial value of `max_almost_missing`, which is -1.

## Hash Map for Window Counts
This approach optimizes the counting process by using a hash map. Instead of re-scanning for each potential number, we make a single pass through all the subarrays of size `k`. For each subarray, we identify its unique elements and update their appearance count in a global hash map. After this counting phase, we iterate through the map to find the largest number that appeared in exactly one subarray.
**Time:** O((n-k+1) * k), which simplifies to O(n * k). For each of the `n-k+1` windows, we spend O(k) time to build the set of unique elements. · **Space:** O(U + k), where `U` is the number of unique elements in `nums` and `k` is the window size. This is for the `window_counts` map and the temporary `HashSet` for each window. In the worst case, this is O(n + k).
**Pros:** More structured than the pure brute-force method.; Processes each window once to update counts for all numbers within it.
**Cons:** Has the same asymptotic time complexity as the brute-force approach.; Requires extra space for the hash map and hash set, which can be up to O(n + k).
### Explanation
We use a `HashMap<Integer, Integer>` to store the frequency of each number across all windows. We iterate from the first window to the last. For each window, we first find its unique elements using a `HashSet` to ensure we don't over-count. Then, for each unique element, we increment its corresponding counter in our main `HashMap`. Once all windows are processed, the map contains all the necessary information. A final pass over the map allows us to find the largest number with a count of 1.

```java
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

class Solution {
    public int findLargestAlmostMissingInteger(int[] nums, int k) {
        int n = nums.length;
        Map<Integer, Integer> windowCounts = new HashMap<>();

        for (int i = 0; i <= n - k; i++) {
            Set<Integer> uniqueInWindow = new HashSet<>();
            for (int j = i; j < i + k; j++) {
                uniqueInWindow.add(nums[j]);
            }
            for (int num : uniqueInWindow) {
                windowCounts.put(num, windowCounts.getOrDefault(num, 0) + 1);
            }
        }

        int maxAlmostMissing = -1;
        for (Map.Entry<Integer, Integer> entry : windowCounts.entrySet()) {
            if (entry.getValue() == 1) {
                maxAlmostMissing = Math.max(maxAlmostMissing, entry.getKey());
            }
        }

        return maxAlmostMissing;
    }
}
```
### Algorithm
*   Initialize a `HashMap` called `window_counts` to store each number and the count of size-`k` windows it appears in.
*   Iterate through all possible starting positions `i` of a subarray of size `k`, from `0` to `nums.length - k`.
*   For each subarray, create a `HashSet` to find the unique numbers within that subarray. This avoids multiple counting of the same number within a single window.
*   For each unique number `u` in the current window's `HashSet`, increment its count in the `window_counts` map.
*   After populating the map, initialize a variable `max_almost_missing` to -1.
*   Iterate through the entries of the `window_counts` map.
*   If an entry `(number, count)` has a `count` of 1, update `max_almost_missing = max(max_almost_missing, number)`.
*   Finally, return `max_almost_missing`.

## Optimal Approach with Index Pre-computation and Interval Merging
This optimal approach avoids redundant work by changing the perspective. Instead of checking windows for numbers, we check numbers for windows. We first pre-compute all locations of each number. For any given number, its occurrences define a set of intervals of windows that contain it. The problem then reduces to finding the total size of the union of these intervals. By merging these intervals efficiently, we can find the count of windows for each number in linear time relative to its number of occurrences.
**Time:** O(N + V), where `N` is `nums.length` and `V` is the range of values (51). The initial pass to build the map is O(N). The second part iterates `V` times, and the inner work for all numbers combined is proportional to the total number of occurrences, which is `N`. Thus, the total time is O(N + V). · **Space:** O(N), where `N` is the length of `nums`. This space is used to store the `positions` map, which in the worst case (all unique elements) stores `N` indices in total.
**Pros:** Most efficient approach with linear time complexity.; Scales well even with larger constraints for `n`.
**Cons:** More complex to understand and implement correctly, especially the interval merging logic.
### Explanation
The core idea is to map each number to a list of its indices in the array. This takes one pass, O(n). Then, for each number `x` (we check from 50 down to 0), we calculate how many unique size-`k` windows contain it. An occurrence of `x` at index `p` is covered by windows starting from `max(0, p - k + 1)` to `min(n - k, p)`. Since the indices of `x` are naturally sorted, the corresponding window intervals are also sorted by their start points. We can then calculate the size of their union in a single pass over the indices. This avoids creating intermediate lists of intervals and is highly efficient.

```java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public int findLargestAlmostMissingInteger(int[] nums, int k) {
        int n = nums.length;
        Map<Integer, List<Integer>> positions = new HashMap<>();
        for (int i = 0; i < n; i++) {
            positions.computeIfAbsent(nums[i], key -> new ArrayList<>()).add(i);
        }

        for (int x = 50; x >= 0; x--) {
            if (!positions.containsKey(x)) {
                continue;
            }

            List<Integer> indices = positions.get(x);
            int totalWindows = 0;
            int lastMergedEnd = -1; // Tracks the end of the last merged interval of window indices

            for (int p : indices) {
                int start = Math.max(0, p - k + 1);
                int end = Math.min(n - k, p);

                if (start > lastMergedEnd) { // This interval is disjoint from the previous ones
                    totalWindows += (end - start + 1);
                } else { // This interval overlaps with the previous one
                    if (end > lastMergedEnd) {
                        totalWindows += (end - lastMergedEnd);
                    }
                }
                lastMergedEnd = Math.max(lastMergedEnd, end);
            }

            if (totalWindows == 1) {
                return x; // Found the largest, can return immediately
            }
        }

        return -1;
    }
}
```
### Algorithm
*   First, pre-process the input array `nums` to find all indices for each number. Store this in a `HashMap<Integer, List<Integer>>` called `positions`.
*   Iterate through candidate numbers `x` from 50 down to 0.
*   If `x` is not present in the `positions` map, continue to the next number.
*   For a given `x`, retrieve its list of indices. Each occurrence at index `p` implies `x` is in any window of size `k` that covers `p`. A window starting at `i` covers `p` if `i <= p <= i + k - 1`, which is equivalent to `p - k + 1 <= i <= p`. This defines an interval of window start indices.
*   The goal is to find the size of the union of these intervals for all occurrences of `x`. This can be done efficiently by merging the intervals.
*   Initialize `total_windows = 0` and `last_merged_end = -1`.
*   For each position `p` of `x`:
    *   Calculate the window start index interval `[start, end]`, where `start = max(0, p - k + 1)` and `end = min(n - k, p)`.
    *   If this interval is disjoint from the previously merged one (`start > last_merged_end`), add its full length `(end - start + 1)` to `total_windows`.
    *   If it overlaps, add the length of the new portion `(end - last_merged_end)` to `total_windows`.
    *   Update `last_merged_end = max(last_merged_end, end)`.
*   If `total_windows` for `x` is 1, return `x` as it's the largest almost missing integer.
*   If the loop finishes, return -1.

# Solutions
### Java

```java
class Solution {
private
  int[] nums;
public
  int largestInteger(int[] nums, int k) {
    this.nums = nums;
    if (k == 1) {
      Map<Integer, Integer> cnt = new HashMap<>();
      for (int x : nums) {
        cnt.merge(x, 1, Integer : : sum);
      }
      int ans = -1;
      for (var e : cnt.entrySet()) {
        if (e.getValue() == 1) {
          ans = Math.max(ans, e.getKey());
        }
      }
      return ans;
    }
    if (k == nums.length) {
      return Arrays.stream(nums).max().getAsInt();
    }
    return Math.max(f(0), f(nums.length - 1));
  }
private
  int f(int k) {
    for (int i = 0; i < nums.length; ++i) {
      if (i != k && nums[i] == nums[k]) {
        return -1;
      }
    }
    return nums[k];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int largestInteger(vector<int> &nums, int k) {
    if (k == 1) {
      unordered_map<int, int> cnt;
      for (int x : nums) {
        ++cnt[x];
      }
      int ans = -1;
      for (auto &[x, v] : cnt) {
        if (v == 1) {
          ans = max(ans, x);
        }
      }
      return ans;
    }
    int n = nums.size();
    if (k == n) {
      return ranges ::max(nums);
    }
    auto f = [&](int k) -> int {
      for (int i = 0; i < n; ++i) {
        if (i != k && nums[i] == nums[k]) {
          return -1;
        }
      }
      return nums[k];
    };
    return max(f(0), f(n - 1));
  }
};

```

### Python

```python
class Solution:
    def largestInteger(self, nums: List[int], k: int) -> int: def f(k: int) -> int: for i, x in enumerate(nums): if i != k and x == nums[k]: return - 1 return nums[k] if k == 1: cnt = Counter(nums) return max((x for x, v in cnt . items() if v == 1), default=- 1) if k == len(nums): return max(nums) return max(f(0), f(len(nums) - 1))

```