โ† Accolite questions

Find Missing Numbers in a Sorted Array

Filed under Accolite

Free read 1 of 3

Check 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

  1. Check if the sequence increments by 1 continuously from the first element to the last element.

Solution

O(N + K) time where K is number of missing elements, O(K) space

Python
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.