Find Missing Numbers in a Sorted Array
Filed under Accolite
Free read 1 of 3Check if the sequence increments by 1 continuously from the first element to the last element.
The question
Given a sorted array of numbers, identify all missing numbers in the sequence in O(N) time complexity.
Constraints
- Array is sorted in ascending order
- Elements may include duplicates or arbitrary gaps
Examples
- Input
- arr = [1, 2, 4, 6]
- Output
- [3, 5]
- Why
- Between 2 and 4, 3 is missing. Between 4 and 6, 5 is missing.
Approach
Check if the sequence increments by 1 continuously from the first element to the last element.
Check every number in a hash set against a full range, taking O(max - min) time.
Iterate through the sorted array comparing adjacent elements. If arr[i+1] - arr[i] > 1, add all intermediate integers to the result list.
Arrays with length < 2 or arrays with duplicate elements.
Solution
O(N + K) time where K is number of missing elements, O(K) space
def findMissing(arr):
missing = []
for i in range(len(arr) - 1):
diff = arr[i+1] - arr[i]
if diff > 1:
for val in range(arr[i] + 1, arr[i+1]):
missing.append(val)
return missing
Tips
- What they are testing: Test arrays with no missing numbers, multiple consecutive missing numbers, and negative numbers.
- Common mistake: Using nested loops or inefficient searches leading to O(N^2) instead of linear O(N) scan.
Related Accolite questions
Collected from public candidate posts and coding forums. Updated Nov 2026.