Find the Largest Almost Missing Integer

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

1
2
3
4
5
6
7
8
9
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

1
2
3
4
5
6
7
8
9
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

1
2
3
4
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 <= 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    int findLargestAlmostMissing(vector<int>& nums, int k) {
        unordered_map<int, int> cnt;
        for (int i = 0; i + k <= nums.size(); ++i) {
            unordered_set<int> seen;
            for (int j = i; j < i + k; ++j) seen.insert(nums[j]);
            for (int x : seen) cnt[x]++;
        }
        int ans = -1;
        for (auto& [x, c] : cnt) if (c == 1) ans = max(ans, x);
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
func findLargestAlmostMissing(nums []int, k int) int {
    cnt := map[int]int{}
    for i := 0; i+k <= len(nums); i++ {
        seen := map[int]bool{}
        for j := i; j < i+k; j++ {
            seen[nums[j]] = true
        }
        for x := range seen {
            cnt[x]++
        }
    }
    ans := -1
    for x, c := range cnt {
        if c == 1 && x > ans {
            ans = x
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public int findLargestAlmostMissing(int[] nums, int k) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int i = 0; i + k <= nums.length; i++) {
            Set<Integer> seen = new HashSet<>();
            for (int j = i; j < i + k; j++) seen.add(nums[j]);
            for (int x : seen) cnt.put(x, cnt.getOrDefault(x, 0) + 1);
        }
        int ans = -1;
        for (var e : cnt.entrySet()) if (e.getValue() == 1) ans = Math.max(ans, e.getKey());
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    fun findLargestAlmostMissing(nums: IntArray, k: Int): Int {
        val cnt = mutableMapOf<Int, Int>()
        for (i in 0..nums.size - k) {
            val seen = mutableSetOf<Int>()
            for (j in i until i + k) seen.add(nums[j])
            for (x in seen) cnt[x] = cnt.getOrDefault(x, 0) + 1
        }
        var ans = -1
        for ((x, c) in cnt) if (c == 1 && x > ans) ans = x
        return ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def find_largest_almost_missing(nums: list[int], k: int) -> int:
    cnt: dict[int, int] = {}
    for i in range(len(nums) - k + 1):
        seen = set(nums[i:i+k])
        for x in seen:
            cnt[x] = cnt.get(x, 0) + 1
    ans = -1
    for x, c in cnt.items():
        if c == 1 and x > ans:
            ans = x
    return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
impl Solution {
    pub fn find_largest_almost_missing(nums: Vec<i32>, k: i32) -> i32 {
        use std::collections::{HashMap, HashSet};
        let mut cnt = HashMap::new();
        let k = k as usize;
        for i in 0..=nums.len()-k {
            let mut seen = HashSet::new();
            for j in i..i+k { seen.insert(nums[j]); }
            for &x in &seen { *cnt.entry(x).or_insert(0) += 1; }
        }
        let mut ans = -1;
        for (&x, &c) in &cnt { if c == 1 && x > ans { ans = x; } }
        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
    findLargestAlmostMissing(nums: number[], k: number): number {
        const cnt: Record<number, number> = {};
        for (let i = 0; i + k <= nums.length; i++) {
            const seen = new Set(nums.slice(i, i + k));
            for (const x of seen) cnt[x] = (cnt[x] ?? 0) + 1;
        }
        let ans = -1;
        for (const x in cnt) if (cnt[x] === 1 && +x > ans) ans = +x;
        return ans;
    }
}

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.

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Constraints#

Solution#

Method 1 – Sliding Window + Frequency Map#

Intuition#

Approach#

Code#

Complexity#