Search Insert Position

EASY✓ CHIP-TIMEDLC #35 — FULL STATEMENT ↗

The drill: Find the index where a target either sits inside a sorted array or would need to be inserted to keep it sorted — the array holds distinct values in ascending order.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A sorted array of distinct integers arrives along with a target value, and the drill wants the index where that target belongs.

When the target already appears in the array, its own index is the answer. When it doesn't, the answer is the index it would need to occupy to keep the array in ascending order — sliding everything from that point onward one step to the right.

That insertion point is always well defined, including the two edge cases of inserting before the first element or after the last one.

EX 01

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

→ 2

EXACT HIT

EX 02

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

→ 1

INSERT BETWEEN TWO VALUES

EX 03

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

→ 4

INSERT PAST THE END

array length can reach into the tens of thousands
values are distinct and arranged in ascending order
target may fall before the first or after the last element
answer is a single index, hit or insertion point alike

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

If the target isn't in the array, the answer is still a single specific index — the one spot ordering demands it slot into. What determines that spot?

HINT 2 THE STRUCTURE

The insertion index is exactly the count of elements smaller than the target — find the first position whose value is not less than target.

HINT 3 ONE STEP FROM THE ANSWER

Binary-search for the leftmost index where nums[mid] >= target; when the loop ends, lo is that boundary — hit or insertion point alike.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE LOWER BOUNDPATTERN · LOWER BOUND SEARCHnums = [-5, -3, -1, 2, 4, 8] · target = 3

-5

-3

-1

STEP 1

Target 3 isn't required to exist — only its correct slot does. Search window starts as the whole array, indices 0 to 5.

STEP 1 / 8 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/search-insert-position.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        lo, hi = 0, len(nums)
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] < target:
                lo = mid + 1
            else:
                hi = mid
        return lo

TIME O(LOG N)SPACE O(1)PYTHON · RACE PACE · 10 LN

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        for i, v in enumerate(nums):
            if v >= target:
                return i
        return len(nums)

TIME O(N)SPACE O(1)PYTHON · TRAINING PACE · 6 LN

class Solution {
    public int searchInsert(int[] nums, int target) {
        int lo = 0, hi = nums.length;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }
}

TIME O(LOG N)SPACE O(1)JAVA · RACE PACE · 14 LN

class Solution {
    public int searchInsert(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= target) {
                return i;
            }
        }
        return nums.length;
    }
}

TIME O(N)SPACE O(1)JAVA · TRAINING PACE · 10 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED