LeetCode Problem 3471

Difficulty: 🟢 Easy
Topics: Array, Hash Table

Solution

LeetCode 3471 - Find the Largest Almost Missing Integer

Problem Understanding

The problem gives us an integer array nums and an integer k. We consider every contiguous subarray of length k. An integer is called almost missing if it appears in exactly one of those size-k subarrays.

Our goal is to find the largest integer that satisfies this property. If no integer appears in exactly one size-k subarray, we return -1.

To understand the requirement clearly, we are not counting how many times a value occurs inside a subarray. Instead, we count how many different size-k subarrays contain that value.

For example, suppose a value appears multiple times inside a single subarray. That still counts as appearing in only one subarray. On the other hand, if the value appears once in several different size-k subarrays, then it is not almost missing.

The input constraints are very small:

• 1 <= nums.length <= 50
• 0 <= nums[i] <= 50
• 1 <= k <= nums.length

These constraints tell us that even relatively inefficient approaches are acceptable. There are at most 50 elements, and values are also limited to the range [0, 50].

Some important edge cases include:

• k = 1, where every individual element forms its own subarray.
• k = n, where there is exactly one size-k subarray, namely the entire array.
• Arrays containing duplicate values.
• Values appearing multiple times within the same window.
• Cases where no value appears in exactly one size-k subarray.

Because the input size is so small, correctness and clarity are more important than squeezing out every possible optimization.

Approaches

Brute Force

The most direct approach is to generate every subarray of size k.

For each distinct value in nums, we examine every size-k subarray and check whether the value appears inside that subarray. We count how many subarrays contain the value. If the count equals exactly one, then the value is almost missing.

After processing all values, we return the largest valid value.

This approach is correct because it directly implements the definition from the problem statement. However, it repeatedly scans subarrays for every distinct value, causing unnecessary work.

Key Observation

Instead of processing each value separately, we can process each size-k subarray once.

For every window:

1. Collect the distinct values present in that window.
2. For each distinct value, increment a counter that records how many size-k subarrays contain that value.

At the end:

• A value is almost missing if its counter equals 1.
• Among all such values, we return the largest one.

A hash map is ideal here because it allows us to efficiently count how many windows contain each value.

Since the array size is at most 50, this solution is both simple and efficient.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n² × u)	O(u)	For each unique value, scan every window
Optimal	O(n × k)	O(u)	Process each window once and count contained values
			u = number of distinct values

Algorithm Walkthrough

Step 1

Create a hash map called window_count.

The key is a value from nums, and the value is the number of size-k subarrays that contain that integer.

Step 2

Generate every size-k subarray.

The starting index of a window ranges from 0 to n - k.

Step 3

For each window, create a set containing all distinct values in that window.

We use a set because a value should contribute at most once per subarray. If a number appears multiple times inside the same window, that window still counts only once.

Step 4

Iterate through the set.

For every distinct value in the current window, increment its count in window_count.

Step 5

After processing all windows, scan the hash map.

Any value whose count equals 1 is almost missing.

Step 6

Track the largest such value.

If no value has count 1, return -1.

Otherwise, return the largest qualifying value.

Why it works

The algorithm maintains the invariant that window_count[x] equals the number of size-k subarrays containing value x.

Each window contributes exactly once to every distinct value it contains. Therefore, after all windows have been processed, the recorded count exactly matches the problem definition. Selecting the largest value whose count is 1 returns the largest almost missing integer.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def largestInteger(self, nums: List[int], k: int) -> int:
        window_count = defaultdict(int)
        n = len(nums)

        for start in range(n - k + 1):
            window_values = set(nums[start:start + k])

            for value in window_values:
                window_count[value] += 1

        answer = -1

        for value, count in window_count.items():
            if count == 1:
                answer = max(answer, value)

        return answer

The implementation follows the algorithm directly.

A defaultdict(int) stores how many size-k windows contain each value. For every window, we build a set so that duplicate occurrences within the same window do not inflate the count.

Once all windows have been processed, we iterate through the map and look for values whose count equals exactly one. Among those values, we keep the maximum and return it.

If no such value exists, the initial value of -1 remains unchanged and is returned.

Go Solution

func largestInteger(nums []int, k int) int {
	windowCount := make(map[int]int)
	n := len(nums)

	for start := 0; start <= n-k; start++ {
		windowValues := make(map[int]bool)

		for i := start; i < start+k; i++ {
			windowValues[nums[i]] = true
		}

		for value := range windowValues {
			windowCount[value]++
		}
	}

	answer := -1

	for value, count := range windowCount {
		if count == 1 && value > answer {
			answer = value
		}
	}

	return answer
}

The Go implementation uses map[int]int for counting windows and map[int]bool as the temporary set for each window.

Unlike Python, Go does not have a built-in set type, so a map with boolean values is used to represent distinct elements in the current window. Otherwise, the logic is identical.

There are no overflow concerns because all values and counts are very small.

Worked Examples

Example 1

Input

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

Windows:

Window	Distinct Values
[3, 9, 2]	{3, 9, 2}
[9, 2, 1]	{9, 2, 1}
[2, 1, 7]	{2, 1, 7}

Building the counts:

Value	Count
1	2
2	3
3	1
7	1
9	2

Values appearing in exactly one window are:

3, 7

Largest value:

7

Result:

7

Example 2

Input

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

Windows:

Window	Distinct Values
[3, 9, 7, 2]	{3, 9, 7, 2}
[9, 7, 2, 1]	{9, 7, 2, 1}
[7, 2, 1, 7]	{7, 2, 1}

Counts:

Value	Count
1	2
2	3
3	1
7	3
9	2

Only value with count 1:

3

Result:

3

Example 3

Input

nums = [0, 0]
k = 1

Windows:

Window	Distinct Values
[0]	{0}
[0]	{0}

Counts:

Value	Count
0	2

No value has count 1.

Result:

-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n × k)	There are n - k + 1 windows, each requiring up to k elements to build the set
Space	O(u)	Hash map stores counts for distinct values

Here, u is the number of distinct values in the array. Since the constraints are tiny (n ≤ 50), the algorithm runs extremely quickly in practice.

Test Cases

sol = Solution()

assert sol.largestInteger([3, 9, 2, 1, 7], 3) == 7  # example 1
assert sol.largestInteger([3, 9, 7, 2, 1, 7], 4) == 3  # example 2
assert sol.largestInteger([0, 0], 1) == -1  # example 3

assert sol.largestInteger([5], 1) == 5  # single element
assert sol.largestInteger([1, 2, 3], 3) == 3  # entire array is one window
assert sol.largestInteger([1, 1, 1], 1) == -1  # repeated value in all windows
assert sol.largestInteger([1, 2, 1], 2) == 2  # middle value appears in one window
assert sol.largestInteger([4, 4, 2, 4], 2) == 2  # duplicate values across windows
assert sol.largestInteger([0, 1, 2, 3], 1) == 3  # every distinct value appears once
assert sol.largestInteger([7, 7, 7, 7], 4) == 7  # one window only
assert sol.largestInteger([1, 2, 3, 4, 5], 2) == 5  # largest qualifying value

Test Summary

Test	Why
[3,9,2,1,7], k=3	Official example 1
[3,9,7,2,1,7], k=4	Official example 2
[0,0], k=1	Official example 3
[5], k=1	Smallest possible array
[1,2,3], k=3	Single window case
[1,1,1], k=1	No almost missing value
[1,2,1], k=2	Value appearing in exactly one window
[4,4,2,4], k=2	Duplicates inside and across windows
[0,1,2,3], k=1	Every value appears in one window
[7,7,7,7], k=4	One window containing duplicates
[1,2,3,4,5], k=2	Multiple candidates, choose largest

Edge Cases

Edge Case 1: k = n

When the window size equals the entire array length, there is exactly one size-k subarray. Every distinct value in the array appears in that single window, so every distinct value is almost missing. The correct answer is simply the largest value in the array. The implementation handles this naturally because only one window is processed and every distinct value receives a count of 1.

Edge Case 2: Duplicate Values Inside a Window

Consider:

nums = [7, 7, 7, 7]
k = 4

The value 7 appears four times inside the window, but it should only count as appearing in one subarray. Using a set for each window ensures that a window contributes at most one count per value, preventing overcounting.

Edge Case 3: k = 1

When k = 1, every element forms its own subarray. The number of windows containing a value becomes exactly the frequency of that value in the array. Values occurring once are almost missing, while values occurring multiple times are not. The algorithm handles this automatically because each one-element window contributes exactly one count to its value.

Edge Case 4: No Valid Answer

Consider:

nums = [0, 0]
k = 1

The value 0 appears in two different size-1 windows, so its count is 2. Since no value has count 1, the algorithm never updates the answer from its initial value of -1, which is the correct result.

Edge Case 5: Multiple Valid Candidates

Consider:

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

Both 3 and 7 appear in exactly one size-k subarray. The problem asks for the largest such value, not the first one encountered. The implementation explicitly tracks the maximum qualifying value, ensuring the correct result is returned.