Find the Largest Almost Missing Integer

Easy
1828.

Find the Largest Almost Missing Integer

Find the Largest Almost Missing Integer is an easy coding problem on arrays and hash table, asked in Amazon interviews.

You are given an integer array nums and an integer k.

An integer x is almost missing from nums if it occurs in exactly one of the subarrays of nums that have length k. (A subarray contains x if at least one of its elements equals x.)

Return the largest almost missing integer, or -1 if there is none.

Example 1

Input
nums = [4,8,1,6,5], k = 3
Output
5
Explanation
The windows are `[4,8,1]`, `[8,1,6]`, `[1,6,5]`. `4` and `5` each occur in exactly one of them; `8`, `6` and `1` occur in more.

Example 2

Input
nums = [2,7,7,3], k = 1
Output
3
Explanation
With `k = 1` each element is its own window: `2` and `3` occur once, `7` twice.

Example 3

Input
nums = [9,9], k = 1
Output
-1
Explanation
`9` occurs in both windows.

Constraints

  • 1 <= nums.length <= 50
  • 0 <= nums[i] <= 50
  • 1 <= k <= nums.length
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var largestInteger = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find the Largest Almost Missing Integer — Problem & Solution

Find the Largest Almost Missing Integer solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Find the Largest Almost Missing Integer is an easy coding problem on arrays and hash table, asked in Amazon interviews.

  • Difficulty: Easy
  • Topics: Arrays, Hash Table
  • Asked at: Amazon
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given an integer array nums and an integer k.

An integer x is almost missing from nums if it occurs in exactly one of the subarrays of nums that have length k. (A subarray contains x if at least one of its elements equals x.)

Return the largest almost missing integer, or -1 if there is none.

Example 1

Input: nums = [4,8,1,6,5], k = 3
Output: 5
Explanation: The windows are `[4,8,1]`, `[8,1,6]`, `[1,6,5]`. `4` and `5` each occur in exactly one of them; `8`, `6` and `1` occur in more.

Example 2

Input: nums = [2,7,7,3], k = 1
Output: 3
Explanation: With `k = 1` each element is its own window: `2` and `3` occur once, `7` twice.

Example 3

Input: nums = [9,9], k = 1
Output: -1
Explanation: `9` occurs in both windows.

Constraints

  • 1 <= nums.length <= 50
  • 0 <= nums[i] <= 50
  • 1 <= k <= nums.length

Hints for Find the Largest Almost Missing Integer

  1. Hint 1

    Think about which positions belong to only one window of length k. If 1 < k < n, every position except the two ends lies in at least two windows.

  2. Hint 2

    So for 1 < k < n, only nums[0] and nums[n-1] can be almost missing — and only if that value occurs nowhere else in the array.

  3. Hint 3

    Handle the two edge cases separately: k == n (one window holds everything) and k == 1 (a value must occur exactly once).

How to solve Find the Largest Almost Missing Integer

For 1 < k < n, an interior index is covered by at least two windows, so a value is almost missing only if its single occurrence is at index 0 or n - 1. The cases k == n and k == 1 are degenerate and read off directly.

Approach

  1. If k == n, there is one window, so every value is almost missing: return max(nums).
  2. Count how often each value occurs.
  3. If k == 1, each element is a window: return the largest value whose count is 1, or -1.
  4. Otherwise start with -1; if nums[0] occurs once, take it; if nums[n-1] occurs once, take the larger. Return the result.

Why it works

Index i lies in windows starting from max(0, i - k + 1) to min(i, n - k). For 0 < i < n - 1 with 1 < k < n that range has at least two starts, so any value occurring at an interior index appears in two windows. Index 0 lies only in the first window and index n - 1 only in the last, which are different windows when k < n — so a value occurring solely at one end is in exactly one window, and a value occurring at an end and anywhere else is in at least two.

Complexity

  • Time — O(n)
  • Space — O(V) with V = 51 possible values

Pitfalls

  • With k == n the general rule fails: the first and last windows are the same window, and every value counts.
  • A value at index 0 that also appears later is not almost missing.

Reference solution

Python

from typing import List

def largestInteger(nums: List[int], k: int) -> int:
    n = len(nums)
    if k == n:
        return max(nums)
    count = {}
    for v in nums:
        count[v] = count.get(v, 0) + 1
    if k == 1:
        once = [v for v, c in count.items() if c == 1]
        return max(once) if once else -1
    best = -1
    if count[nums[0]] == 1:
        best = nums[0]
    if count[nums[-1]] == 1:
        best = max(best, nums[-1])
    return best

Java

public static int largestInteger(int[] nums, int k) {
    int n = nums.length;
    int[] count = new int[51];
    int mx = -1;
    for (int v : nums) {
        count[v]++;
        mx = Math.max(mx, v);
    }
    if (k == n) return mx;
    int best = -1;
    if (k == 1) {
        for (int v = 0; v <= 50; v++) if (count[v] == 1) best = v;
        return best;
    }
    if (count[nums[0]] == 1) best = nums[0];
    if (count[nums[n - 1]] == 1) best = Math.max(best, nums[n - 1]);
    return best;
}

C++

int largestInteger(vector<int>& nums, int k) {
    int n = nums.size();
    vector<int> count(51, 0);
    int mx = -1;
    for (int v : nums) {
        count[v]++;
        mx = max(mx, v);
    }
    if (k == n) return mx;
    int best = -1;
    if (k == 1) {
        for (int v = 0; v <= 50; v++) if (count[v] == 1) best = v;
        return best;
    }
    if (count[nums[0]] == 1) best = nums[0];
    if (count[nums[n - 1]] == 1) best = max(best, nums[n - 1]);
    return best;
}

JavaScript

var largestInteger = function(nums, k) {
    var n = nums.length;
    var count = new Array(51).fill(0);
    var mx = -1;
    for (var i = 0; i < n; i++) {
        count[nums[i]]++;
        mx = Math.max(mx, nums[i]);
    }
    if (k === n) return mx;
    var best = -1;
    if (k === 1) {
        for (var v = 0; v <= 50; v++) if (count[v] === 1) best = v;
        return best;
    }
    if (count[nums[0]] === 1) best = nums[0];
    if (count[nums[n - 1]] === 1) best = Math.max(best, nums[n - 1]);
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets