Find the smallest missing element from a sorted array

Given a sorted array of non-negative distinct integers, find the smallest missing non-negative element in it.

For example,

Input: nums[] = [0, 1, 2, 6, 9, 11, 15]
Output: The smallest missing element is 3

Input: nums[] = [1, 2, 3, 4, 6, 9, 11, 15]
Output: The smallest missing element is 0

Input: nums[] = [0, 1, 2, 3, 4, 5, 6]
Output: The smallest missing element is 7

Practice this problem

A simple analysis of the problem shows us that the smallest missing number would be the element’s index, which is not equal to its element. For instance, consider array [0, 1, 2, 6, 9, 11, 15]. Here, the smallest missing element is 3 since 6 is present at index 3 (instead of element 3). If all elements in the array are at their right position, then the smallest missing number is equal to the array size; For instance, 6 in the case of [0, 1, 2, 3, 4, 5].

A naive solution would be to run a linear search on the array and return the first index, which doesn’t match its value. If no mismatch happens, then return the array size. The problem with this approach is that its worst-case time complexity is O(n), where n is the size of the input. This solution also does not take advantage of the fact that the input is sorted.

We can easily solve this problem in O(log(n)) time by modifying the binary search algorithm. The idea is to compare the mid-index with the middle element. If both are the same, then the mismatch is in the right subarray; otherwise, it lies in the left subarray. So, we discard one half accordingly and recur for the other. Following is the C, Java, and Python implementation based on the idea:

C

#include <stdio.h>

// Function to find the smallest missing element in a sorted

// array of distinct non-negative integers

int findSmallestMissing(int nums[], int low, int high)

{

// base condition

if (low > high) {

return low;

}

int mid = low + (high - low) / 2;

// if the mid-index matches with its value, then the mismatch

// lies on the right half

if (nums[mid] == mid) {

return findSmallestMissing(nums, mid + 1, high);

}

else {

// mismatch lies on the left half

return findSmallestMissing(nums, low, mid - 1);

}

int main(void)

{

int nums[] = { 0, 1, 2, 3, 4, 5, 6 };

int n = sizeof(nums) / sizeof(nums[0]);

int low = 0, high = n - 1;

printf("The smallest missing element is %d", findSmallestMissing(nums, low, high));

return 0;

}

Download Run Code

Output:

The smallest missing element is 7

Java

class Main

{

// Function to find the smallest missing element in a sorted

// array of distinct non-negative integers

public static int findSmallestMissing(int[] nums, int left, int right)

{

// base condition

if (left > right) {

return left;

}

int mid = left + (right - left) / 2;

// if the mid-index matches with its value, then the mismatch

// lies on the right half

if (nums[mid] == mid) {

return findSmallestMissing(nums, mid + 1, right);

}

else {

// mismatch lies on the left half

return findSmallestMissing(nums, left, mid - 1);

}

public static void main(String[] args)

{

int[] nums = { 0, 1, 2, 3, 4, 5, 6 };

int left = 0, right = nums.length - 1;

System.out.println("The smallest missing element is "

+ findSmallestMissing(nums, left, right));

}

Download Run Code

Output:

The smallest missing element is 7

Python

# Function to find the smallest missing element in a sorted

# list of distinct non-negative integers

def findSmallestMissing(nums, left=None, right=None):

# initialize left and right

if left is None and right is None:

(left, right) = (0, len(nums) - 1)

# base condition

if left > right:

return left

mid = left + (right - left) // 2

# if the mid-index matches with its value, then the mismatch

# lies on the right half

if nums[mid] == mid:

return findSmallestMissing(nums, mid + 1, right)

# mismatch lies on the left half

else:

return findSmallestMissing(nums, left, mid - 1)

if __name__ == '__main__':

nums = [0, 1, 2, 3, 4, 5, 6]

print('The smallest missing element is', findSmallestMissing(nums))

Download Run Code

Output:

The smallest missing element is 7

The time complexity of the above solution is O(log(n)) and requires O(log(n)) implicit space for the call stack.