Given a sorted array of non-negative distinct integers, find the smallest missing non-negative element in it.
For example,
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
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#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; } |
Output:
The smallest missing element is 7
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
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)); } } |
Output:
The smallest missing element is 7
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
# 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)) |
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.