Smallest Absent Positive Greater Than Average - Video Solutions

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.