Find the Largest Almost Missing Integer
EasyPrompt
You are given an integer array nums and an integer k.
An integer x is almost missing from nums if x appears in exactly one subarray of size k within nums.
Return the largest almost missing integer from nums. If no such integer exists, return -1.
Example 1:
Input: nums = [3,9,2,1,7], k = 3
Output: 7
Explanation:
- 1 appears in 2 subarrays of size 3:
[9, 2, 1]and[2, 1, 7]. - 2 appears in 3 subarrays of size 3:
[3, 9, 2],[9, 2, 1],[2, 1, 7]. - 3 appears in 1 subarray of size 3:
[3, 9, 2]. - 7 appears in 1 subarray of size 3:
[2, 1, 7]. - 9 appears in 2 subarrays of size 3:
[3, 9, 2], and[9, 2, 1].
We return 7 since it is the largest integer that appears in exactly one subarray of size k.
Example 2:
Input: nums = [3,9,7,2,1,7], k = 4
Output: 3
Explanation:
- 1 appears in 2 subarrays of size 4:
[9, 7, 2, 1],[7, 2, 1, 7]. - 2 appears in 3 subarrays of size 4:
[3, 9, 7, 2],[9, 7, 2, 1],[7, 2, 1, 7]. - 3 appears in 1 subarray of size 4:
[3, 9, 7, 2]. - 7 appears in 3 subarrays of size 4:
[3, 9, 7, 2],[9, 7, 2, 1],[7, 2, 1, 7]. - 9 appears in 2 subarrays of size 4:
[3, 9, 7, 2],[9, 7, 2, 1].
We return 3 since it is the largest and only integer that appears in exactly one subarray of size k.
Example 3:
Input: nums = [0,0], k = 1
Output: -1
Explanation:
There is no integer that appears in only one subarray of size 1.
Constraints:
1 <= nums.length <= 500 <= nums[i] <= 501 <= k <= nums.length
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly translates the problem definition into code. It checks every possible number from the allowed range (0 to 50) to see if it meets the 'almost missing' criteria. For each number, it iterates through all subarrays of size k and counts how many of them contain that number. If the count is one, we've found an almost missing integer. By checking numbers in descending order, the first one we find is guaranteed to be the largest.
Algorithm
- Initialize a variable
max_almost_missingto -1 to store the result. - Iterate through all possible integer values
xthat 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 counterwindow_countto 0. - Iterate through all possible starting positions
iof a subarray of sizek, from0tonums.length - k. - For each subarray starting at
i, check ifxis present withinnums[i]tonums[i+k-1]. - If
xis found in the current subarray, incrementwindow_count. - After checking all subarrays, if
window_countis exactly 1, it meansxis an almost missing integer. Since we are iterating from the largest possible value downwards, thisxis the largest one. Returnximmediately. - 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.
Walkthrough
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.
class Solution { public int findLargestAlmostMissingInteger(int[] nums, int k) { int n = nums.length; // Iterate from the largest possible value down to 0 for (int x = 50; x >= 0; x--) { int windowCount = 0; // Iterate through all subarrays of size k for (int i = 0; i <= n - k; i++) { boolean found = false; // Check if x is in the current subarray for (int j = i; j < i + k; j++) { if (nums[j] == x) { found = true; break; } } if (found) { windowCount++; } } // If x appeared in exactly one window, it's the largest one found so far if (windowCount == 1) { return x; } } return -1; }}Complexity
Time
O(V * n * k), where `V` is the range of values (51 in this case), `n` is the length of `nums`, and `k` is the subarray size. Since `V` is a small constant, the complexity is effectively O(n * k).
Space
O(1), as we only use a few variables to keep track of counts and loop indices.
Trade-offs
Pros
Very simple to understand and implement.
Minimal space complexity.
Cons
The time complexity of O(V * n * k) can be slow if the range of values (V) or the array size (n) were large.
It repeatedly scans subarrays, which is inefficient.
Solutions
Solution
class Solution {private int[] nums;public int largestInteger(int[] nums, int k) { this.nums = nums; if (k == 1) { Map<Integer, Integer> cnt = new HashMap<>(); for (int x : nums) { cnt.merge(x, 1, Integer : : sum); } int ans = -1; for (var e : cnt.entrySet()) { if (e.getValue() == 1) { ans = Math.max(ans, e.getKey()); } } return ans; } if (k == nums.length) { return Arrays.stream(nums).max().getAsInt(); } return Math.max(f(0), f(nums.length - 1)); }private int f(int k) { for (int i = 0; i < nums.length; ++i) { if (i != k && nums[i] == nums[k]) { return -1; } } return nums[k]; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.