Find the largest almost missing integer

Array Hash Table

37.1% acceptance

Feb 25, 2026

107

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn largest_integer(nums: Vec<i32>, k: i32) -> i32 {
    let k = k as usize;
    let n = nums.len();

    // O(n) approach based on three cases:
    //
    // Case 1 – k == n: exactly one window exists; every element qualifies.
    // Case 2 – k == 1: each element is its own window; a value qualifies iff
    //           it appears exactly once in nums (first == last occurrence).
    // Case 3 – 1 < k < n: a value qualifies iff ALL its occurrences are at
    //           index 0  (only included in the first window) or ALL are at
    //           index n-1 (only included in the last window).
    //           Proof sketch: for a single occurrence at position p, the number
    //           of windows containing it is min(n-k,p) - max(0,p-k+1) + 1 = 1
    //           only when p=0 or p=n-1.  Multiple occurrences spread across
    //           other positions always produce more than one window.

    if k == n {
      return *nums.iter().max().unwrap();
    }

    use std::collections::HashMap;
    // Record (first_index, last_index) for each distinct value.
    let mut occ: HashMap<i32, (usize, usize)> = HashMap::new();
    for (i, &v) in nums.iter().enumerate() {
      let e = occ.entry(v).or_insert((i, i));
      e.1 = i;
    }

    let mut result = -1i32;
    if k == 1 {
      // Qualifies iff value appears exactly once (first == last).
      for (&v, &(f, l)) in &occ {
        if f == l {
          result = result.max(v);
        }
      }
    } else {
      // 1 < k < n: qualifies iff all occurrences sit at index 0 or n-1.
      for (&v, &(f, l)) in &occ {
        if (f == 0 && l == 0) || (f == n - 1 && l == n - 1) {
          result = result.max(v);
        }
      }
    }
    result
  }
}