399. Find the Largest Almost Missing Integer

Slide a window of size k across nums. For every window, mark each distinct value as seen once more. A value that ends up seen in exactly one window is 'almost missing' — return the largest such value.

Idea

An integer x is almost missing when it appears in exactly one subarray (window) of size k. So we simply need, for every value, the count of size-k windows that contain it. Then we take the largest value whose count is exactly 1.

Because the constraints are tiny (n <= 50), we can afford to look at every window directly. There are n - k + 1 windows. For each window we take the set of its values (so a value repeated inside one window is still counted once for that window) and bump a counter for each distinct value.

Walk-through

Take nums = [3, 9, 2, 1, 7], k = 3. The windows of size 3 are:

1. [3, 9, 2] → distinct {3, 9, 2}
2. [9, 2, 1] → distinct {9, 2, 1}
3. [2, 1, 7] → distinct {2, 1, 7}

Counting how many windows each value lands in:

Values with count exactly 1 are 3 and 7. The largest is 7, so we return 7.

If no value has a count of exactly 1, we return -1.

Complexity

• Time: O(n · k) — each of the n - k + 1 windows scans k elements. With n <= 50 this is trivial.
• Space: O(n) — the counter holds at most one entry per distinct value.

class Solution {
    public int largestInteger(int[] nums, int k) {
        int n = nums.length;
        Map<Integer, Integer> count = new HashMap<>();
        for (int start = 0; start + k <= n; start++) {
            Set<Integer> window = new HashSet<>();
            for (int j = start; j < start + k; j++) {
                window.add(nums[j]);
            }
            for (int v : window) {
                count.merge(v, 1, Integer::sum);
            }
        }
        int ans = -1;
        for (Map.Entry<Integer, Integer> e : count.entrySet()) {
            if (e.getValue() == 1) {
                ans = Math.max(ans, e.getKey());
            }
        }
        return ans;
    }
}