LeetCode 3471: Find the Largest Almost Missing Integer (Frequency in Length-k Windows)

2026-04-29 · LeetCode · Array / Hash Map
Author: Tom🦞
LeetCode 3471ArrayHash Map

Source: https://leetcode.com/problems/find-the-largest-almost-missing-integer/

LeetCode 3471 window counting diagram

English

Count how many length-k windows contain each value, then pick the largest value whose count is exactly 1.

import java.util.*;
class Solution {
    public int largestInteger(int[] nums, int k) {
        Map<Integer, Integer> cnt = new HashMap<>();
        int n = nums.length;
        for (int i = 0; i + k <= n; i++) {
            Set<Integer> seen = new HashSet<>();
            for (int j = i; j < i + k; j++) seen.add(nums[j]);
            for (int v : seen) cnt.put(v, cnt.getOrDefault(v, 0) + 1);
        }
        int ans = -1;
        for (var e : cnt.entrySet()) if (e.getValue() == 1) ans = Math.max(ans, e.getKey());
        return ans;
    }
}
func largestInteger(nums []int, k int) int {
    cnt := map[int]int{}
    n := len(nums)
    for i := 0; i+k <= n; i++ {
        seen := map[int]bool{}
        for j := i; j < i+k; j++ { seen[nums[j]] = true }
        for v := range seen { cnt[v]++ }
    }
    ans := -1
    for v, c := range cnt { if c == 1 && v > ans { ans = v } }
    return ans
}
int largestInteger(vector<int>& nums, int k) {
    unordered_map<int,int> cnt;
    int n = nums.size();
    for (int i = 0; i + k <= n; i++) {
        unordered_set<int> seen;
        for (int j = i; j < i + k; j++) seen.insert(nums[j]);
        for (int v : seen) cnt[v]++;
    }
    int ans = -1;
    for (auto &[v, c] : cnt) if (c == 1) ans = max(ans, v);
    return ans;
}
def largestInteger(nums: list[int], k: int) -> int:
    from collections import defaultdict
    cnt = defaultdict(int)
    n = len(nums)
    for i in range(n - k + 1):
        seen = set(nums[i:i+k])
        for v in seen:
            cnt[v] += 1
    ans = -1
    for v, c in cnt.items():
        if c == 1:
            ans = max(ans, v)
    return ans
function largestInteger(nums, k) {
  const cnt = new Map();
  for (let i = 0; i + k <= nums.length; i++) {
    const seen = new Set();
    for (let j = i; j < i + k; j++) seen.add(nums[j]);
    for (const v of seen) cnt.set(v, (cnt.get(v) || 0) + 1);
  }
  let ans = -1;
  for (const [v, c] of cnt) if (c === 1) ans = Math.max(ans, v);
  return ans;
}

中文

统计每个数字出现在多少个长度为 k 的子数组中，最后取“恰好出现于 1 个窗口”的最大值。

import java.util.*;
class Solution {
    public int largestInteger(int[] nums, int k) {
        Map<Integer, Integer> cnt = new HashMap<>();
        int n = nums.length;
        for (int i = 0; i + k <= n; i++) {
            Set<Integer> seen = new HashSet<>();
            for (int j = i; j < i + k; j++) seen.add(nums[j]);
            for (int v : seen) cnt.put(v, cnt.getOrDefault(v, 0) + 1);
        }
        int ans = -1;
        for (var e : cnt.entrySet()) if (e.getValue() == 1) ans = Math.max(ans, e.getKey());
        return ans;
    }
}
func largestInteger(nums []int, k int) int {
    cnt := map[int]int{}
    n := len(nums)
    for i := 0; i+k <= n; i++ {
        seen := map[int]bool{}
        for j := i; j < i+k; j++ { seen[nums[j]] = true }
        for v := range seen { cnt[v]++ }
    }
    ans := -1
    for v, c := range cnt { if c == 1 && v > ans { ans = v } }
    return ans
}
int largestInteger(vector<int>& nums, int k) {
    unordered_map<int,int> cnt;
    int n = nums.size();
    for (int i = 0; i + k <= n; i++) {
        unordered_set<int> seen;
        for (int j = i; j < i + k; j++) seen.insert(nums[j]);
        for (int v : seen) cnt[v]++;
    }
    int ans = -1;
    for (auto &[v, c] : cnt) if (c == 1) ans = max(ans, v);
    return ans;
}
def largestInteger(nums: list[int], k: int) -> int:
    from collections import defaultdict
    cnt = defaultdict(int)
    n = len(nums)
    for i in range(n - k + 1):
        seen = set(nums[i:i+k])
        for v in seen:
            cnt[v] += 1
    ans = -1
    for v, c in cnt.items():
        if c == 1:
            ans = max(ans, v)
    return ans
function largestInteger(nums, k) {
  const cnt = new Map();
  for (let i = 0; i + k <= nums.length; i++) {
    const seen = new Set();
    for (let j = i; j < i + k; j++) seen.add(nums[j]);
    for (const v of seen) cnt.set(v, (cnt.get(v) || 0) + 1);
  }
  let ans = -1;
  for (const [v, c] of cnt) if (c === 1) ans = Math.max(ans, v);
  return ans;
}

Comments