Find the Largest Almost Missing Integer
Asked at Meta, Microsoft
Problem
Given an integer array nums and an integer target, find the largest integer that appears at most once in nums and is less than or equal to target. If no such integer exists, return -1. This tests frequency counting and filtering.
Asked At
| Company | Difficulty | |
|---|---|---|
| Meta | Easy | View all Meta questions → |
| Microsoft | Easy | View all Microsoft questions → |
How to Think About It
Count frequencies: use a hash map to count how many times each number appears. Then filter numbers that appear at most once AND are <= target. Return the largest among them.
Visual walkthrough for nums = [3, 2, 5, 5, 7], target = 5:
Frequencies: {3:1, 2:1, 5:2, 7:1}
Numbers appearing at most once: 3, 2, 7
Numbers <= 5: 3, 2
Largest: 3. Result: 3.
Why not just sort: sorting helps find the largest <= target, but you still need to check frequency. A hash map + single pass is simpler and equally efficient at O(n).
The algorithm: build frequency map. Initialize result = -1. For each number in nums, if freq[num] <= 1 and num <= target, update result = max(result, num). Return result.
Edge cases: all numbers appear more than once (return -1), all numbers > target (return -1), target < minimum element (return -1), empty array (return -1).
Optimal Approach
Step 1: Build a frequency map by counting occurrences of each number in nums.
Step 2: Initialize result = -1.
Step 3: For each number in nums:
- If freq[num] <= 1 and num <= target:
- result = max(result, num)
Step 4: Return result.
Walkthrough for nums = [4, 1, 3, 2, 7, 4], target = 5:
- Frequencies: {4:2, 1:1, 3:1, 2:1, 7:1}
- num=4: freq=2, fails (2 > 1)
- num=1: freq=1, 1<=5. result=max(-1,1)=1
- num=3: freq=1, 3<=5. result=max(1,3)=3
- num=2: freq=1, 2<=5. result=max(3,2)=3
- num=7: freq=1, 7>5, fails
- num=4: freq=2, fails
- Result: 3
Time: O(n) for counting and filtering. Space: O(n) for the frequency map.
What Trips People Up in Real Interviews
Missing the "at most once" constraint. Numbers appearing exactly once OR zero times qualify. A number appearing twice or more does NOT qualify. Check freq[num] <= 1, not freq[num] == 1.
Forgetting to check the target constraint. The number must also be <= target. A number appearing once but greater than target doesn't qualify.
Returning -1 when the result variable was never updated. Initialize result to -1 so that if no number qualifies, -1 is automatically returned.
Using a HashSet instead of a HashMap. A HashSet tells you if a number exists but not its frequency. You need a HashMap (or Counter) to count occurrences.
Iterating through unique numbers instead of all numbers. If nums = [5, 5], both 5s have frequency 2. You must count all occurrences, not just unique values.
Solution Code
def largestInteger(nums, target):
from collections import Counter
freq = Counter(nums)
result = -1
for num in nums:
if freq[num] <= 1 and num <= target:
result = max(result, num)
return resultFrequently Asked Questions
What is the Find the Largest Almost Missing Integer problem?
Given an integer array nums and an integer target, find the largest integer that appears at most once in nums and is less than or equal to target. If no such integer exists, return -1. This tests frequency counting and filtering.
How do you solve Find the Largest Almost Missing Integer?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Find the Largest Almost Missing Integer?
Find the Largest Almost Missing Integer is asked at Meta, Microsoft. It is a easy difficulty problem.
What are common mistakes on Find the Largest Almost Missing Integer?
- Missing the "at most once" constraint. Numbers appearing exactly once OR zero times qualify. A number appearing twice or more does NOT qualify. Check `freq[num] <= 1`, not `freq[num] == 1`.
- Forgetting to check the target constraint. The number must also be <= target. A number appearing once but greater than target doesn't qualify.
- Returning -1 when the result variable was never updated. Initialize result to -1 so that if no number qualifies, -1 is automatically returned.
- Using a `HashSet` instead of a `HashMap`. A `HashSet` tells you if a number exists but not its frequency. You need a `HashMap` (or `Counter`) to count occurrences.
- Iterating through unique numbers instead of all numbers. If nums = [5, 5], both 5s have frequency 2. You must count all occurrences, not just unique values.