problemeasyalgorithmsleetcode-3471leetcode 3471leetcode3471

Find the Largest Almost Missing Integer

EasyUpdated: Jul 26, 2025
Practice on:
LeetCode

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

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 <= 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

  1. Use a dictionary to count, for each number, in how many windows of size k it appears.
  2. 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.
  3. After processing all windows, collect all numbers that appear in exactly one window.
  4. Return the largest such number, or -1 if none exists.

Code

C++
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;
    }
};
Go
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
}
Java
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;
    }
}
Kotlin
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
    }
}
Python
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
Rust
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
    }
}
TypeScript
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.

Comments