Find the Largest Almost Missing Integer

Difficulty: Easy | Acceptance: 37.30% | Paid: No Topics: Array, Hash Table

You are given an integer array nums. An integer x is called almost missing if x is not present in nums, but x + 1 is present in nums. Return the largest almost missing integer. If no such integer exists, return -1.

• Examples
• Constraints
• Hash Set
• Sorting

Examples

Example 1:

Input: nums = [1,2,3]
Output: 0
Explanation: 0 is not in nums, but 0 + 1 = 1 is in nums. No other integer larger than 0 satisfies the condition.

Example 2:

Input: nums = [1,3,4]
Output: 2
Explanation: 2 is not in nums, but 2 + 1 = 3 is in nums. 0 is also almost missing, but 2 is larger.

Example 3:

Input: nums = [5]
Output: 4
Explanation: 4 is not in nums, but 4 + 1 = 5 is in nums.

Constraints

1 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹

Hash Set

Intuition We can iterate through the unique numbers in the array. For every number y present in the array, we check if y - 1 is missing. If y - 1 is missing, then x = y - 1 is an “almost missing” integer. We simply track the maximum such x found.

Steps

• Insert all elements of nums into a Hash Set for O(1) lookups.
• Initialize ans to -1.
• Iterate through each number y in the set:
  • If y - 1 is not in the set, update ans with max(ans, y - 1).
• Return ans.

class Solution:
    def findLargestAlmostMissing(self, nums: List[int]) -> int:
        num_set = set(nums)
        ans = -1
        for y in num_set:
            if y - 1 not in num_set:
                ans = max(ans, y - 1)
        return ans

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Uses O(n) extra space for the set.

Sorting

Intuition If we sort the array, we can identify gaps between consecutive numbers. If nums[i] > nums[i-1] + 1, it means nums[i] - 1 is missing from the array. Since nums[i] is present, nums[i] - 1 is an almost missing integer. We also consider nums[0] - 1 as a candidate.

Steps

• Sort the array nums.
• Initialize ans to nums[0] - 1.
• Iterate through the array starting from index 1:
  • If nums[i] > nums[i - 1] + 1, update ans with max(ans, nums[i] - 1).
• Return ans.

class Solution:
    def findLargestAlmostMissing(self, nums: List[int]) -> int:
        nums.sort()
        ans = nums[0] - 1
        for i in range(1, len(nums)):
            if nums[i] > nums[i - 1] + 1:
                ans = max(ans, nums[i] - 1)
        return ans

Complexity

• Time: O(n log n)
• Space: O(1) or O(n) depending on the sorting algorithm.
• Notes: Slower than the Hash Set approach due to sorting, but uses less space if sorting is in-place.