Search Insert Position - Practice Coding Problems

Search Insert Position - Problem

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

Input & Output

Example 1 — Target Found

$ Input: nums = [1,3,5,6], target = 5

› Output: 2

💡 Note: Target 5 exists at index 2, so return 2

Example 2 — Insert in Middle

$ Input: nums = [1,3,5,6], target = 2

› Output: 1

💡 Note: Target 2 should be inserted at index 1 to maintain sorted order: [1,2,3,5,6]

Example 3 — Insert at End

$ Input: nums = [1,3,5,6], target = 7

› Output: 4

💡 Note: Target 7 is larger than all elements, so insert at the end (index 4)

Constraints

1 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
nums contains distinct values sorted in ascending order
-10⁴ ≤ target ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Sorted array [1,3,5,6] and target = 2

Process

Find where target should be inserted to maintain order

Output

Return index 1 (between 1 and 3)

Key Takeaway

🎯 Key Insight: Binary search leverages the sorted property to find insertion points in O(log n) time

Asked in

G Google 45 a Amazon 38 M Microsoft 32 f Facebook 28

The key insight is to leverage the sorted array property with binary search. Since the array is sorted, we can eliminate half the search space at each step by comparing the target with the middle element. Best approach is binary search with Time: O(log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Linear Search	O(n)	O(1)	Iterate through array to find target or insertion position
Binary Search	O(log n)	O(1)	Use binary search to find target or insertion position in O(log n) time

Linear Search — Algorithm Steps

Iterate through each index
If nums[i] >= target, return i
If no such element found, return array length

Visualization

Tap to expand

Step-by-Step Walkthrough

Start from Beginning

Compare target with first element

Continue Forward

Move to next element if current is smaller than target

Found Position

Return index when element >= target found

Code -

solution.c — C

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

int solution(int* nums, int numsSize, int target) {
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] >= target) {
            return i;
        }
    }
    return numsSize;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[10000];
    int numsSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n') {
            nums[numsSize++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int target;
    scanf("%d", &target);
    
    int result = solution(nums, numsSize, target);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single loop through array in worst case

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

1.3M Views

High Frequency

~15 min Avg. Time

8.4K 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