3471. Find the Largest Almost Missing Integer

Array
Hash Table
Enumeration
Counting

TIME

O(n * k)

SPACE

O(n)

Intuition

"Appears in exactly one subarray of size k" is a direct counting question, and with n <= 50 there are at most 50 windows to inspect. For each window take the set of values it holds (a value appearing twice inside one window still counts as that one window), tally across windows, and keep the values whose tally is 1.

Two boundary behaviours fall out for free:

k == 1: each window is a single element, so a value's tally equals its number of occurrences, it qualifies iff it occurs exactly once.
k == n: there is only one window, so every distinct value has tally 1 and the answer is simply the maximum.

Approach

For each start index i in [0, n - k], collect the distinct values in nums[i .. i + k - 1].
Increment a counter for each distinct value in that window.
Return the largest value whose counter equals 1, or -1 if none.

Complexity

Time: O(n * k), every window scanned once
Space: O(n), the tally map

Edge Cases

No qualifying value (Example 3) → -1
Duplicates inside a single window count that window once (hence the per-window set)
k == n → one window → answer is max(nums)
k == 1 → answer is the largest value occurring exactly once
Values may be 0, so -1 is a safe "not found" sentinel

Code

from typing import List
from collections import defaultdict


class Solution:
    def largestInteger(self, nums: List[int], k: int) -> int:
        """
        3471. Find the Largest Almost Missing Integer
        Time: O(n * k)
        Space: O(n)
        """
        n = len(nums)
        windows = defaultdict(int)  # value -> number of size-k windows containing it

        for i in range(n - k + 1):
            # a value repeated inside one window still counts that window once
            for v in set(nums[i:i + k]):
                windows[v] += 1

        best = -1
        for v, c in windows.items():
            if c == 1 and v > best:
                best = v
        return best

import java.util.HashSet;
import java.util.Set;

/**
 * 3471. Find the Largest Almost Missing Integer
 * Time: O(n * k)
 * Space: O(n)
 */
class Solution {
    public int largestInteger(int[] nums, int k) {
        int n = nums.length;
        int[] windows = new int[51]; // value -> number of size-k windows containing it

        for (int i = 0; i + k <= n; i++) {
            // a value repeated inside one window still counts that window once
            Set<Integer> seen = new HashSet<>();
            for (int j = i; j < i + k; j++) {
                seen.add(nums[j]);
            }
            for (int v : seen) {
                windows[v]++;
            }
        }

        for (int v = 50; v >= 0; v--) {
            if (windows[v] == 1) {
                return v;
            }
        }
        return -1;
    }
}