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 <= 500 <= nums[i] <= 501 <= k <= nums.length
Hints for Find the Largest Almost Missing Integer
Hint 1
Think about which positions belong to only one window of length
k. If1 < k < n, every position except the two ends lies in at least two windows.Hint 2
So for
1 < k < n, onlynums[0]andnums[n-1]can be almost missing — and only if that value occurs nowhere else in the array.Hint 3
Handle the two edge cases separately:
k == n(one window holds everything) andk == 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
- If
k == n, there is one window, so every value is almost missing: returnmax(nums). - Count how often each value occurs.
- If
k == 1, each element is a window: return the largest value whose count is 1, or-1. - Otherwise start with
-1; ifnums[0]occurs once, take it; ifnums[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 == nthe 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 bestJava
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