Problem
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
.
A subarray is a contiguous sequence of elements within an array.
Examples
Example 1
|
|
Example 2
|
|
Example 3
|
|
Constraints
1 <= nums.length <= 50
0 <= nums[i] <= 50
1 <= k <= nums.length
Solution
Method 1 – Sliding Window + Frequency Map
Intuition
We want to find the largest integer that appears in exactly one subarray of size k. By sliding a window of size k and counting the frequency of each number in each window, we can track how many windows each number appears in.
Approach
- Use a dictionary to count, for each number, in how many windows of size k it appears.
- Slide a window of size k over the array:
- For each window, use a set to avoid double-counting numbers within the same window.
- For each number in the window, increment its window count.
- After processing all windows, collect all numbers that appear in exactly one window.
- Return the largest such number, or -1 if none exists.
Code
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Complexity
- ⏰ Time complexity:
O(n * k)
, where n is the length of nums. For each window, we process up to k elements. - 🧺 Space complexity:
O(n)
, for the frequency map and set per window.