.png)
Smallest Missing Number in Sorted Array
Problem Statement
You are given a sorted array of distinct non-negative integers.
Your task is to find the smallest missing non-negative number from the array.
Example 1
Input
arr = [0, 1, 2, 3, 5, 6]
Output
4
Example 2
Input
arr = [1, 2, 3, 4]
Output
0
Example 3
Input
arr = [0, 1, 2, 3]
Output
4
Why This Problem Is Important
- Classic binary search application
- Tests observation: arr[i] == i property
- Common in Amazon, Google, Microsoft
- Foundation for index-based searching problems
Approaches Overview
| Approach | Technique | Time | Space |
|---|---|---|---|
| 1 | Linear Scan | O(n) | O(1) |
| 2 | Binary Search | O(log n) | O(1) |
Approach 1: Linear Scan
Idea
- Traverse the array
- First index where arr[i] != i → answer
- If all match → answer = n
Time & Space
- Time: O(n)
- Space: O(1)
Python
def smallestMissing(arr):
for i in range(len(arr)):
if arr[i] != i:
return i
return len(arr)
print(smallestMissing([0,1,2,3,5,6]))
C++
#include
using namespace std;
int smallestMissing(vector& arr){
for(int i=0;i arr = {0,1,2,3,5,6};
cout << smallestMissing(arr);
}
Java
class Main {
public static int smallestMissing(int[] arr){
for(int i=0;iJavaScript
function smallestMissing(arr){
for(let i=0;iC#
using System;
class Program {
static int SmallestMissing(int[] arr){
for(int i=0;iOutput
4
Approach 2: Binary Search (Optimal)
Key Observation
- If arr[mid] == mid → missing number is right side
- If arr[mid] > mid → missing number is left side
Time & Space
- Time: O(log n)
- Space: O(1)
Python
def smallestMissing(arr):
low, high = 0, len(arr)-1
while low <= high:
mid = (low + high) // 2
if arr[mid] == mid:
low = mid + 1
else:
high = mid - 1
return low
print(smallestMissing([0,1,2,3,5,6]))
C++
#include
using namespace std;
int smallestMissing(vector& arr){
int low = 0, high = arr.size()-1;
while(low <= high){
int mid = low + (high-low)/2;
if(arr[mid] == mid)
low = mid + 1;
else
high = mid - 1;
}
return low;
}
int main(){
vector arr = {0,1,2,3,5,6};
cout << smallestMissing(arr);
}
Java
class Main {
public static int smallestMissing(int[] arr){
int low = 0, high = arr.length - 1;
while(low <= high){
int mid = low + (high-low)/2;
if(arr[mid] == mid)
low = mid + 1;
else
high = mid - 1;
}
return low;
}
public static void main(String[] args){
int[] arr = {0,1,2,3,5,6};
System.out.println(smallestMissing(arr));
}
}
JavaScript
function smallestMissing(arr){
let low = 0, high = arr.length - 1;
while(low <= high){
let mid = Math.floor((low + high) / 2);
if(arr[mid] === mid)
low = mid + 1;
else
high = mid - 1;
}
return low;
}
console.log(smallestMissing([0,1,2,3,5,6]));
C#
using System;
class Program {
static int SmallestMissing(int[] arr){
int low = 0, high = arr.Length - 1;
while(low <= high){
int mid = low + (high-low)/2;
if(arr[mid] == mid)
low = mid + 1;
else
high = mid - 1;
}
return low;
}
static void Main(){
int[] arr = {0,1,2,3,5,6};
Console.WriteLine(SmallestMissing(arr));
}
}
Output
4
Final Summary
| Approach | When to Use |
|---|---|
| Linear Scan | Small arrays, quick checks |
| Binary Search | Interview-preferred, optimal |
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.jpg)
.png)
.jpg)
.jpg)
.png)
