Smallest Absent Positive Greater Than Average

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

Given an integer array nums, return the smallest positive integer that is strictly greater than the average of the array and is not present in the array.

The average is calculated as the sum of all elements divided by the number of elements. It is guaranteed that an answer exists.

Examples

Example 1:

Input: nums = [1, 2, 3]
Output: 4
Explanation: The average is (1 + 2 + 3) / 3 = 2.
The integers greater than 2 are 3, 4, 5, ...
3 is present in the array.
4 is not present in the array and is positive.
Thus, the answer is 4.

Example 2:

Input: nums = [3, 4, 5]
Output: 6
Explanation: The average is (3 + 4 + 5) / 3 = 4.
The integers greater than 4 are 5, 6, 7, ...
5 is present in the array.
6 is not present in the array and is positive.
Thus, the answer is 6.

Example 3:

Input: nums = [-1, -2, -3]
Output: 1
Explanation: The average is (-1 - 2 - 3) / 3 = -2.
The integers greater than -2 are -1, 0, 1, 2, ...
The smallest positive integer not in the array is 1.

Constraints

1 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹
It is guaranteed that an answer exists.

• Examples
• Constraints
• Approach 1: Brute Force
• Approach 2: Hash Set
• Approach 3: Sorting and Binary Search

Examples

Example 1:

Input: nums = [1, 2, 3]
Output: 4

Example 2:

Input: nums = [3, 4, 5]
Output: 6

Example 3:

Input: nums = [-1, -2, -3]
Output: 1

Constraints

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

Approach 1: Brute Force

Intuition Calculate the average, then iterate through integers starting from the floor of the average plus one. For each integer, check if it exists in the array and if it is positive.

Steps

• Calculate the average of the array.
• Initialize a candidate integer x to floor(average) + 1.
• Loop indefinitely:
  • Check if x is positive and not present in nums.
  • If both conditions are met, return x.
  • Otherwise, increment x and repeat.

class Solution:
    def smallestAbsentPositive(self, nums: list[int]) -> int:
        avg = sum(nums) / len(nums)
        x = int(avg) + 1
        while True:
            if x > 0 and x not in nums:
                return x
            x += 1

Complexity

• Time: O(N * M), where N is the length of the array and M is the value of the answer. In the worst case, we scan the array for every candidate integer.
• Space: O(1)
• Notes: Simple to implement but inefficient for large arrays or large gaps in numbers.

Approach 2: Hash Set

Intuition Optimize the lookup process by storing all array elements in a Hash Set. This allows us to check for the presence of a candidate integer in O(1) time on average.

Steps

• Calculate the average of the array.
• Store all elements of nums in a Hash Set.
• Initialize a candidate integer x to floor(average) + 1.
• Loop indefinitely:
  • Check if x is positive and not present in the Hash Set.
  • If both conditions are met, return x.
  • Otherwise, increment x and repeat.

class Solution:
    def smallestAbsentPositive(self, nums: list[int]) -> int:
        avg = sum(nums) / len(nums)
        num_set = set(nums)
        x = int(avg) + 1
        while True:
            if x > 0 and x not in num_set:
                return x
            x += 1

Complexity

• Time: O(N + M), where N is the length of the array (to build the set) and M is the value of the answer (to find the missing number).
• Space: O(N) to store the Hash Set.
• Notes: Significantly faster than brute force for lookups, trading space for time.

Approach 3: Sorting and Binary Search

Intuition Sort the array to organize the numbers. Then, iterate through candidate integers starting from floor(average) + 1. For each candidate, use binary search to check if it exists in the sorted array.

Steps

• Sort the array nums.
• Calculate the average.
• Initialize x to floor(average) + 1.
• Loop indefinitely:
  • Use binary search to check if x exists in nums.
  • If x is positive and not found, return x.
  • Otherwise, increment x.

import bisect

class Solution:
    def smallestAbsentPositive(self, nums: list[int]) -> int:
        nums.sort()
        avg = sum(nums) / len(nums)
        x = int(avg) + 1
        while True:
            if x > 0:
                idx = bisect.bisect_left(nums, x)
                if idx == len(nums) or nums[idx] != x:
                    return x
            x += 1

Complexity

• Time: O(N log N + M log N), where N is the length of the array (for sorting) and M is the value of the answer.
• Space: O(1) or O(N) depending on the sorting algorithm’s space complexity.
• Notes: Useful if the array is already sorted or if memory is constrained and O(N) space for a Hash Set is undesirable, though generally slower than the Hash Set approach due to the log N factor for each check.