Find the Largest Almost Missing Integer - Solution & Explanation

Problem Overview: You are given an integer array nums and a window size k. An integer is considered almost missing if it appears in exactly one subarray of length k. The task is to return the largest such integer. If no integer satisfies the condition, return -1.

Approach 1: Brute Force Sliding Window (O(n * k) time, O(n) space)

Generate every subarray of size k and track which numbers appear inside each window. Use a HashMap to count how many windows contain each value. For every window starting at index i, iterate through the next k elements and insert them into a temporary set so duplicates inside the same window are counted only once. Then update the global counter for those elements. After processing all windows, scan the map and return the largest number whose window count equals 1. This method is straightforward but inefficient because each window requires iterating over k elements. Time complexity is O(n * k) with O(n) extra space for counting.

Approach 2: Case Analysis with Hash Table (O(n) time, O(n) space)

The key observation is how many windows of size k can contain an element based on its index. For most positions in the array, an element belongs to multiple windows. In fact, when 1 < k < n, only the boundary elements (nums[0] and nums[n-1]) can appear in exactly one window. All interior indices are covered by at least two windows. This dramatically reduces the search space.

Handle three cases directly:

k == n: There is only one window (the entire array). Every number appears in exactly one window, so return the maximum element.

k == 1: Each window contains a single element. The number of windows containing a value equals its frequency. Use a frequency map and return the largest element with frequency 1.

1 < k < n: Only nums[0] and nums[n-1] can appear in exactly one window. Count element frequencies using a hash map from Hash Table. If either boundary value occurs exactly once in the entire array, it qualifies. Return the larger valid candidate; otherwise return -1.

This reasoning removes the need to simulate windows entirely. The algorithm becomes a single pass frequency count over the array, followed by constant-time checks. The final complexity is O(n) time with O(n) space.

Recommended for interviews: The case analysis approach. Interviewers like candidates who first reason about how many windows can contain a position instead of brute forcing every window. Mentioning the brute force sliding window shows baseline understanding, but recognizing that only boundary indices can belong to exactly one window demonstrates strong problem decomposition and knowledge of hash-based counting.