Find the Largest Almost Missing Integer

• 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.

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.

1class Solution {2    public int findLargestAlmostMissingInteger(int[] nums, int k) {3        int n = nums.length;4        // Iterate from the largest possible value down to 05        for (int x = 50; x >= 0; x--) {6            int windowCount = 0;7            // Iterate through all subarrays of size k8            for (int i = 0; i <= n - k; i++) {9                boolean found = false;10                // Check if x is in the current subarray11                for (int j = i; j < i + k; j++) {12                    if (nums[j] == x) {13                        found = true;14                        break;15                    }16                }17                if (found) {18                    windowCount++;19                }20            }21            // If x appeared in exactly one window, it's the largest one found so far22            if (windowCount == 1) {23                return x;24            }25        }26        return -1;27    }28}

• 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.

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.

1import java.util.HashMap;2import java.util.HashSet;3import java.util.Map;4import java.util.Set;5 6class Solution {7    public int findLargestAlmostMissingInteger(int[] nums, int k) {8        int n = nums.length;9        Map<Integer, Integer> windowCounts = new HashMap<>();10 11        for (int i = 0; i <= n - k; i++) {12            Set<Integer> uniqueInWindow = new HashSet<>();13            for (int j = i; j < i + k; j++) {14                uniqueInWindow.add(nums[j]);15            }16            for (int num : uniqueInWindow) {17                windowCounts.put(num, windowCounts.getOrDefault(num, 0) + 1);18            }19        }20 21        int maxAlmostMissing = -1;22        for (Map.Entry<Integer, Integer> entry : windowCounts.entrySet()) {23            if (entry.getValue() == 1) {24                maxAlmostMissing = Math.max(maxAlmostMissing, entry.getKey());25            }26        }27 28        return maxAlmostMissing;29    }30}

• 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.

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.

1import java.util.ArrayList;2import java.util.HashMap;3import java.util.List;4import java.util.Map;5 6class Solution {7    public int findLargestAlmostMissingInteger(int[] nums, int k) {8        int n = nums.length;9        Map<Integer, List<Integer>> positions = new HashMap<>();10        for (int i = 0; i < n; i++) {11            positions.computeIfAbsent(nums[i], key -> new ArrayList<>()).add(i);12        }13 14        for (int x = 50; x >= 0; x--) {15            if (!positions.containsKey(x)) {16                continue;17            }18 19            List<Integer> indices = positions.get(x);20            int totalWindows = 0;21            int lastMergedEnd = -1; // Tracks the end of the last merged interval of window indices22 23            for (int p : indices) {24                int start = Math.max(0, p - k + 1);25                int end = Math.min(n - k, p);26 27                if (start > lastMergedEnd) { // This interval is disjoint from the previous ones28                    totalWindows += (end - start + 1);29                } else { // This interval overlaps with the previous one30                    if (end > lastMergedEnd) {31                        totalWindows += (end - lastMergedEnd);32                    }33                }34                lastMergedEnd = Math.max(lastMergedEnd, end);35            }36 37            if (totalWindows == 1) {38                return x; // Found the largest, can return immediately39            }40        }41 42        return -1;43    }44}