#35 Search Insert Position

frequently reported atBloomberg Microsoft Amazon Google

the problem

In plain words

Given a sorted array of distinct integers and a target, return its index if found; otherwise return the index where it would be inserted to keep the order. Must be O(log n).

in nums = [1,3,5,6], target = 5

out 2

in nums = [1,3,5,6], target = 2

out 1

in nums = [1,3,5,6], target = 7

out 4

Goes after everything — index n.

1 ≤ n ≤ 10⁴
-10⁴ ≤ nums[i], target ≤ 10⁴
Distinct, sorted ascending

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternBinary search (exact & bounds)

"Index if found, else insert position" is one question: the first index whose value is ≥ target. That's lower bound.

solutions

From brute force to optimal

Scan from the left; stop at the first value that is not smaller than target.

i = 0.
While i < n and nums[i] < target: i++.
Return i.

timeO(n)

Worst case scans everything (target bigger than all).

spaceO(1)

One index.

javajava.util.*

1class Solution {2    public int searchInsert(int[] nums, int target) {3        int i = 0;4        while (i < nums.length && nums[i] < target) i++; // first value >= target5        return i;6    }7}

Binary search for the first index with nums[i] ≥ target; the range is [0, n] because n is a valid answer.

lo = 0, hi = n.
If nums[mid] ≥ target → hi = mid (keep it).
Else lo = mid + 1.
Return lo.

timeO(log n)

Halves [0, n] each step.

spaceO(1)

Two indices.

javajava.util.*

1class Solution {2    public int searchInsert(int[] nums, int target) {3        int lo = 0, hi = nums.length;          // the answer may be n (insert at the end)4        while (lo < hi) {5            int mid = lo + (hi - lo) / 2;6            if (nums[mid] >= target) hi = mid; // mid could be the spot: keep it7            else lo = mid + 1;                 // mid is too small8        }9        return lo;                             // first index with nums[i] >= target10    }11}

sim

Dry run

loading simulation…

javajava.util.*

1class Solution {2    public int searchInsert(int[] nums, int target) {3        int lo = 0, hi = nums.length;          // the answer may be n (insert at the end)4        while (lo < hi) {5            int mid = lo + (hi - lo) / 2;6            if (nums[mid] >= target) hi = mid; // mid could be the spot: keep it7            else lo = mid + 1;                 // mid is too small8        }9        return lo;                             // first index with nums[i] >= target10    }11}

The library already computes the insertion point when the key is missing.

r = Arrays.binarySearch(nums, target).
Return r ≥ 0 ? r : −r − 1.

timeO(log n)

One library binary search.

spaceO(1)

No extra structures.

javajava.util.*

1class Solution {2    public int searchInsert(int[] nums, int target) {3        int i = Arrays.binarySearch(nums, target); // values are distinct, so a hit is exact4        return i >= 0 ? i : -i - 1;                // -(insertionPoint) - 1  →  insertionPoint5    }6}

in the room

How to say it in the interview

talk track

Point out that the answer can be n, which is why hi starts at nums.length.
Mention the library one-liner, but write the loop — that's what's being tested.

traps

Starting hi at n − 1: then the answer n (target bigger than everything) can never be returned.
Mixing templates: while (lo <= hi) with hi = mid loops forever.
Returning −1 when the target is missing — this problem wants the insert position.

what they ask next

Follow-ups

What if values could repeat and you want the leftmost insert spot?

Lower bound already gives the leftmost; the rightmost spot is upper bound (first value > target).

before you submit

Edge cases to test

Target bigger than everything → n (one past the end).
Target smaller than everything → 0.
A one-element array, with the target before, equal to, or after it.

practise next