3678. Smallest Absent Positive Greater Than Average Solution

Q: Is Smallest Absent Positive Greater Than Average easy or hard?

The problem is categorized as Easy. The main challenge is recognizing that repeated existence checks should use a hash set instead of scanning the array each time.

Q: Smallest Absent Positive Greater Than Average Python/Java solution

In Python, store elements in a set and iterate from floor(avg) + 1 until a value is not in the set. In Java, use HashSet for the same constant-time membership checks. Both implementations run in O(n) time and O(n) space.

The problem

You are given an integer array nums.

Return the smallest absent positive integer in nums such that it is strictly greater than the average of all elements in nums.

The average of an array is defined as the sum of all its elements divided by the number of elements.

Example 1:

Input: nums = [3,5]

Output: 6

Explanation:

The average of nums is (3 + 5) / 2 = 8 / 2 = 4.
The smallest absent positive integer greater than 4 is 6.

Example 2:

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

Output: 3

Explanation:

The average of nums is (-1 + 1 + 2) / 3 = 2 / 3 = 0.667.
The smallest absent positive integer greater than 0.667 is 3.

Example 3:

Input: nums = [4,-1]

Output: 2

Explanation:

The average of nums is (4 + (-1)) / 2 = 3 / 2 = 1.50.
The smallest absent positive integer greater than 1.50 is 2.

Constraints:

1 <= nums.length <= 100
-100 <= nums[i] <= 100

Approach overview

Problem Overview: You are given an integer array. Compute the array's average, then return the smallest positive integer strictly greater than that average that does not appear in the array.

Approach 1: Incremental Check (Brute Force) (Time: O(n * k), Space: O(1))

First compute the average of the array in O(n). Start checking integers from floor(average) + 1 upward. For each candidate value, scan the entire array to see if it exists. If the value is not found, return it as the answer. If it exists, increment the candidate and repeat the scan.

This approach uses only constant extra memory but performs a full array scan for every candidate value. If many consecutive integers after the average exist in the array, the repeated scans increase runtime significantly. It works for small inputs but does not scale well.

Approach 2: Hash Set Lookup (Time: O(n), Space: O(n))

Store all array values in a hash-based structure such as a HashSet or set. Building the set takes O(n) time. Compute the array average, then start from floor(average) + 1. For each candidate value, perform a constant-time hash lookup to check whether it exists in the set.

The key insight is that membership checks drop from O(n) scans to O(1) average-time lookups. As soon as you encounter a value that is not present in the set and is positive, you return it. Even if several consecutive integers appear after the average, the checks remain efficient.

This method works well for general array inputs and leverages constant-time lookups provided by a hash table. It is the standard way to handle “missing value” problems where frequent existence checks are required.

Recommended for interviews: The hash set solution. Interviewers expect you to recognize that repeated membership checks on an array are expensive and replace them with constant-time lookups using a hash table. Explaining the brute-force scan first shows problem understanding, while switching to a hash-based structure demonstrates optimization skills.

Solution

We use a hash map s to record the elements that appear in the array nums.

Then, we calculate the average value avg of the array nums, and initialize the answer ans as max(1, \lfloor avg \rfloor + 1).

If ans appears in s, we increment ans until it no longer appears in s.

Finally, we return ans.

The time complexity is O(n), and the space complexity is O(n), where n is the length of the array nums.

Python

class Solution:
    def smallestAbsent(self, nums: List[int]) -> int:
        s = set(nums)
        ans = max(1, sum(nums) // len(nums) + 1)
        while ans in s:
            ans += 1
        return ans

Java

class Solution {
    public int smallestAbsent(int[] nums) {
        Set<Integer> s = new HashSet<>();
        int sum = 0;
        for (int x : nums) {
            s.add(x);
            sum += x;
        }
        int ans = Math.max(1, sum / nums.length + 1);
        while (s.contains(ans)) {
            ++ans;
        }
        return ans;
    }
}

C++

class Solution {
public:
    int smallestAbsent(vector<int>& nums) {
        unordered_set<int> s;
        int sum = 0;
        for (int x : nums) {
            s.insert(x);
            sum += x;
        }
        int ans = max(1, sum / (int) nums.size() + 1);
        while (s.contains(ans)) {
            ++ans;
        }
        return ans;
    }
};

TypeScript

function smallestAbsent(nums: number[]): number {
    const s = new Set<number>(nums);
    const sum = nums.reduce((a, b) => a + b, 0);
    let ans = Math.max(1, Math.floor(sum / nums.length) + 1);
    while (s.has(ans)) {
        ans++;
    }
    return ans;
}

func smallestAbsent(nums []int) int {
	s := map[int]bool{}
	sum := 0
	for _, x := range nums {
		s[x] = true
		sum += x
	}
	ans := max(1, sum/len(nums)+1)
	for s[ans] {
		ans++
	}
	return ans
}

Try this approach in the editor

Complexity analysis

Approach	Time	Space	When to Use
Incremental Check (Brute Force)	O(n * k)	O(1)	When memory must stay minimal and input size is small
Hash Set Lookup	O(n)	O(n)	General case when fast membership checks are needed

Frequently asked questions

Is Smallest Absent Positive Greater Than Average easy or hard?

The problem is categorized as Easy. The main challenge is recognizing that repeated existence checks should use a hash set instead of scanning the array each time.

Smallest Absent Positive Greater Than Average Python/Java solution

In Python, store elements in a set and iterate from floor(avg) + 1 until a value is not in the set. In Java, use HashSet<Integer> for the same constant-time membership checks. Both implementations run in O(n) time and O(n) space.

How to solve Smallest Absent Positive Greater Than Average in O(n)?

Compute the array average in one pass. Insert all numbers into a hash set, then start from floor(average) + 1 and repeatedly check whether the value exists in the set. The first positive integer not found in the set is the answer. Hash lookups keep the total complexity O(n).

What is the best approach for Smallest Absent Positive Greater Than Average?

The hash set approach is the most efficient. Insert all array values into a set in O(n) time, compute the average, then check integers starting from floor(average) + 1. Each membership test is O(1), so the overall solution runs in O(n) time with O(n) space.

Is Smallest Absent Positive Greater Than Average asked at Google/Amazon/Meta?

Problems involving missing numbers and hash-based membership checks appear frequently in interviews at companies like Amazon, Google, and Meta. Variations often test your ability to use sets or hash maps to reduce repeated array scans.

What data structure is used in Smallest Absent Positive Greater Than Average?

A hash table or hash set is the key data structure. It stores all array elements and allows O(1) average-time membership checks when searching for the smallest missing integer greater than the average.

What is the time complexity of Smallest Absent Positive Greater Than Average?

The optimal solution runs in O(n) time. Building the hash set takes O(n), and checking candidate numbers uses constant-time lookups. Space complexity is O(n) due to storing the array elements in the set.

Smallest Absent Positive Greater Than Average solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Smallest Absent Positive Greater Than Average solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Related problems