Missing Element in Sorted Array - Practice Coding Problems

Missing Element in Sorted Array - Problem

Given an integer array nums which is sorted in ascending order and all of its elements are unique, and given also an integer k, return the k-th missing number starting from the leftmost number of the array.

The missing numbers are the numbers that are not present in the array but would appear in the complete sequence starting from nums[0].

Example: If nums = [4, 7, 9, 10] and k = 1, the complete sequence starting from 4 would be [4, 5, 6, 7, 8, 9, 10, 11, ...]. The missing numbers are [5, 6, 8, 11, ...], so the 1st missing number is 5.

Input & Output

Example 1 — Basic Case

$ Input: nums = [4,7,9,10], k = 1

› Output: 5

💡 Note: The complete sequence starting from 4 is [4,5,6,7,8,9,10,11,...]. Missing numbers are [5,6,8,11,...], so the 1st missing is 5.

Example 2 — Larger K

$ Input: nums = [4,7,9,10], k = 3

› Output: 8

💡 Note: Missing numbers are [5,6,8,11,...]. The 3rd missing number is 8.

Example 3 — Missing Before Array

$ Input: nums = [1,2,4], k = 3

› Output: 6

💡 Note: Complete sequence: [1,2,3,4,5,6,...]. Missing: [3,5,6,...]. The 3rd missing is 6.

Constraints

1 ≤ nums.length ≤ 5 × 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
1 ≤ k ≤ 10⁹
nums is sorted in ascending order

Visualization

Tap to expand

Understanding the Visualization

Input

Sorted array [4,7,9,10] and k=1

Process

Identify missing numbers in complete sequence

Output

Return the 1st missing number: 5

Key Takeaway

🎯 Key Insight: Use the formula nums[i] - nums[0] - i to count missing numbers at any position

Asked in

A Amazon 35 G Google 28 F Facebook 22 M Microsoft 18

The key insight is that at any index i, the number of missing elements before that position is nums[i] - nums[0] - i. The optimal approach uses binary search to efficiently locate where the k-th missing number falls. Time: O(log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Linear Search	O(n²)	O(1)	Check each number sequentially to count missing elements
Binary Search	O(log n)	O(1)	Use binary search to efficiently locate the k-th missing number

Linear Search — Algorithm Steps

Start from nums[0]
For each number, check if it exists in array
Count missing numbers until we find the k-th one

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin from first array element

Check

For each number, see if it exists in array

Count

Count missing numbers until we reach k

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize, int k) {
    if (numsSize == 0) return k;
    
    int current = nums[0];
    int missingCount = 0;
    int i = 0;
    
    while (missingCount < k) {
        if (i < numsSize && nums[i] == current) {
            i++;
        } else {
            missingCount++;
            if (missingCount == k) {
                return current;
            }
        }
        current++;
    }
    
    return current - 1;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    
    char* ptr = strchr(line, '[');
    if (ptr) {
        ptr++;
        char* end = strchr(ptr, ']');
        if (end) *end = '\0';
        
        char* token = strtok(ptr, ",");
        while (token != NULL && numsSize < 1000) {
            nums[numsSize++] = atoi(token);
            token = strtok(NULL, ",");
        }
    }
    
    int k;
    scanf("%d", &k);
    
    printf("%d\n", solution(nums, numsSize, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of potentially n missing numbers, we search through the array of size n

⚠ Quadratic Growth

Space Complexity

O(1)

Only using a few variables, no extra data structures

✓ Linear Space

28.5K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Linear Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler