Find the Largest Almost Missing Integer

Introduction

Sliding window problems show up constantly in coding interviews because they test something more valuable than syntax: can you reason about coverage? Which elements get touched by how many windows, and why? Find the Largest Almost Missing Integer (LeetCode 3471) looks like a straightforward "check every window" problem at first glance, but it's really testing whether you notice a structural shortcut hiding in plain sight — most of the array can be eliminated before you check a single value.

This is the kind of problem interviewers like because the brute force is easy to write and easy to justify, but it wastes an enormous amount of work on positions that were never going to matter. Learning to spot that waste, and to prove why it's safe to skip it, is a transferable skill you'll use in dozens of other sliding window and array problems.

Problem Overview

You're given an integer array nums and a window size k. Slide a window of exactly k consecutive elements across the array, one step at a time — so you get a sequence of overlapping windows, each covering a different k-length stretch.

A value counts as "almost missing" if it appears in exactly one of these windows — not zero, and not two or more. Among all almost missing values, return the largest one. If no value qualifies, return -1.

The key subtlety: this is about how many windows contain the value's position, not how many times the value appears in the array. Those are related but not identical, and mixing them up is the most common way to get this problem wrong.

Example

nums = [3, 9, 2, 1, 7], k = 3

The windows are:

Window	Elements
0	[3, 9, 2]
1	[9, 2, 1]
2	[2, 1, 7]

• 3 (index 0) appears only in window 0 → exactly one window.
• 9 (index 1) appears in windows 0 and 1 → two windows, disqualified.
• 2 (index 2) appears in windows 0, 1, and 2 → disqualified.
• 1 (index 3) appears in windows 1 and 2 → disqualified.
• 7 (index 4) appears only in window 2 → exactly one window.

Qualifying values: 3 and 7. The answer is 7, the larger of the two.

Intuition

Start by asking a simpler question: for a fixed window size k sliding across an array of length n, how many windows pass over a given index i?

Pick an index dead center in the array. Windows can start anywhere from a certain point before it to a certain point after it, and as long as the window still contains i, it counts. For a middle index, that range of valid starting positions is exactly k positions wide — so a middle element gets covered by k different windows.

If k is anything more than 1, that's already more than one window. So no interior element can ever be almost missing, no matter what value it holds. You never need to check it.

Coverage only drops below k near the two edges. The first few indices get fewer windows sliding over them as you approach index 0, because there's no room for a window to start before the array does. The mirror image happens at the last few indices. Only index 0 and index n-1 are guaranteed to sit in exactly one window each — everything else near the edges is still touched by more than one unless k happens to be very small relative to n.

There's one trap: this reasoning assumes k < n. If k == n, there's only one window — the entire array — so literally every element sits in exactly one window, even if the value repeats. It's tempting to reuse "does this value appear only once in the array" as the qualifying check, but that's a different question entirely. Consider nums = [5, 5], k = 2: there's one window, both 5s are inside it, and the correct answer is 5 — not -1, even though 5 appears twice in the array.

Once you separate "how many windows cover this position" from "does this value repeat elsewhere," the rest is bookkeeping: build a frequency map of the array, identify the tiny set of guaranteed single-window positions, and check just those.

Brute Force Solution

Idea: For every distinct value in the array, count how many windows contain it, and keep it if the count is exactly 1.

Algorithm:

1. Generate every window of size k.
2. For each distinct value in the array, scan every window and count how many contain that value.
3. Keep values with a count of exactly 1.
4. Return the largest, or -1.

Advantages: Obviously correct, easy to reason about, no edge case analysis required.

Disadvantages: Every value is checked against every window — the work scales with both the number of elements and the number of windows, which is roughly O(n * (n - k)), effectively O(n²) for many inputs. It passes on small constraints but does a lot of unnecessary work.

Time Complexity: O(n²) in the general case. Space Complexity: O(n) for tracking window membership.

Optimal Solution

The optimal approach follows directly from the intuition above:

1. Build a frequency map of the entire array in one pass — a plain counter that answers "how many times does value v appear anywhere in nums?" in O(1).
2. Identify the edge positions — the indices actually guaranteed to sit in exactly one window:
   • If k == n: there is only one window total, so every index qualifies as an edge position.
   • If k == 1: every element is its own window, so again every index qualifies.
   • Otherwise: only index 0 and index n-1 are guaranteed single-window positions.
3. Check only those edge positions. For each one, look up its value's count in the frequency map. If the count is exactly 1 (the value doesn't repeat anywhere else in the array), it's genuinely almost missing.
4. Track the maximum among qualifying values. If none qualify, return -1.

The frequency check and the window-coverage check are answering two different questions, and you need both: the edge position guarantees the window-count is 1, and the frequency-count-of-1 guarantees the value itself doesn't sneak into a second occurrence elsewhere that could land in another window.

Python Code

from collections import Counter
from typing import List


def largest_almost_missing_integer(nums: List[int], k: int) -> int:
    n = len(nums)
    freq = Counter(nums)

    # Determine which positions are guaranteed to sit in exactly one window.
    if k == n or k == 1:
        edge_indices = range(n)
    else:
        edge_indices = (0, n - 1)

    best = -1
    for i in edge_indices:
        value = nums[i]
        if freq[value] == 1:
            best = max(best, value)

    return best

Code Walkthrough

• freq = Counter(nums) builds the full frequency map in a single O(n) pass — this answers "does this value repeat anywhere in the array?" for any value in O(1).
• The if k == n or k == 1 branch handles the two special cases where every position is a valid edge position: a single giant window, or every element being its own window.
• The else branch is the general case — only 0 and n - 1 are guaranteed to be covered by exactly one window.
• The loop only ever runs over 2 elements (or all n in the special cases), checking each candidate's frequency and keeping the largest qualifying value.
• best defaults to -1, which naturally becomes the answer if nothing survives the check.

Dry Run

nums = [3, 9, 2, 1, 7], k = 3

1. n = 5, k = 3 — neither k == n nor k == 1, so edge indices are (0, 4).
2. freq = {3: 1, 9: 1, 2: 1, 1: 1, 7: 1}.
3. Index 0 → value 3 → freq[3] == 1 → qualifies → best = 3.
4. Index 4 → value 7 → freq[7] == 1 → qualifies → best = max(3, 7) = 7.
5. Return 7.

Matches the expected output from the example above.

Complexity Analysis

Time: O(n) — one pass to build the frequency map, followed by a constant number of lookups (2 in the general case, n in the two special cases, which are themselves O(n) overall). No nested scanning of windows against values.

Space: O(n) for the frequency map, since in the worst case every value in the array is distinct.

This is correct because the frequency map is built once and reused for O(1) lookups, and the number of positions actually checked is bounded by a constant (or by n only in the special cases, which still keeps the whole algorithm linear).

Alternative Solutions

You could compute, for every index, exactly how many windows cover it using a formula (min(i, n - k, k - 1, n - i - 1) + 1), then filter to positions with a coverage count of 1. This generalizes the same idea but is unnecessary here — since we already know analytically which positions can have coverage 1 (the two edges, or all positions in the two special cases), computing the general formula for every index is extra work for the same answer.

Edge Cases

• Empty array: Not a valid input per constraints, but defensively returns -1 since there are no edge indices to check.
• k == n: Every index is a valid edge position; duplicates inside that single window still count as qualifying (see the [5, 5] example).
• k == 1: Every element is its own window, so the answer is simply the largest value in the array.
• All duplicate values: No value has freq[value] == 1 (unless k == n or k == 1), so the answer is -1.
• Two-element array with k == 1: Both elements qualify as their own windows; the larger one wins even if they're equal.

Common Mistakes

1. Confusing "appears once in the array" with "appears in exactly one window." These overlap for the general case but diverge completely when k == n.
2. Forgetting the k == n special case, which causes correct-looking code to wrongly return -1 on inputs like [5, 5] with k = 2.
3. Forgetting the k == 1 special case, where every index is technically an edge and the frequency check still matters.
4. Assuming positions near the start are automatically edge positions. Index 1 is not guaranteed to be in only one window — only index 0 and index n - 1 are, unless k is 1 or n.
5. Running the brute force window-by-window check on every value, which is correct but needlessly quadratic — missing the coverage argument entirely.

Interview Questions

• Why can't a value in the middle of the array ever be almost missing when 1 < k < n?
• How would the solution change if we wanted values appearing in at most one window instead of exactly one?
• Can you generalize the "edge position" formula for a version of this problem where the window doesn't have to be contiguous?
• How would you extend this to return all almost missing values, not just the largest?

Similar Problems

• Sliding Window Maximum (LeetCode 239) — same window-sliding mechanic, different aggregate being tracked.
• Minimum Size Subarray Sum (LeetCode 209) — another problem where reasoning about window boundaries avoids brute force.
• Contains Duplicate II (LeetCode 219) — uses a similar "does this value repeat nearby" frequency-style check.
• Sliding Window Median (LeetCode 480) — deeper sliding window problem where understanding what enters/exits the window each step is the whole challenge.

Key Takeaways

The core lesson generalizes far beyond this one problem: whenever you're sliding a fixed-size window across an array, coverage is not uniform — it's high in the middle and thins out at the edges. Before writing any brute force scan, ask which positions actually have a chance of satisfying your condition, and check only those. Here, that insight took an O(n²) scan down to a single O(n) pass followed by two lookups.

Watch the Video

For the full walkthrough with a live dry run, timing comparison against brute force, and the mid-explanation quiz, watch the video here: {LINK}

About the Series

This breakdown is part of Fun with Learning Technology, a daily series covering LeetCode problems, algorithms, and practical software engineering topics — built for developers who want to understand the why behind a solution, not just memorize the code. New videos drop daily.

Call To Action

If this explanation clicked for you, drop a like on the video and subscribe on YouTube — new problems every day. For the deeper technical write-ups like this one delivered straight to your inbox, subscribe to the Substack. Comments are open — tell me which problem you want broken down next.

---

from collections import Counter

class Solution:
    def largestInteger(self, nums, k):
        n = len(nums)
        freq = Counter(nums)
        edges = range(n) if k in (n, 1) else [0, n - 1]
        best = -1
        for i in edges:
            v = nums[i]
            if freq[v] == 1:
                best = max(best, v)
        return best