Skip to main content

6. Search Insert Position

easyAsked at Figma

Given a sorted array and a target, return the index where target is, or where it would be inserted. Figma uses this as the canonical binary-search invariant test — the same logic that powers their CRDT position-finder when inserting a new operation into a sorted op-log.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Figma loops.

  • Glassdoor (2026-Q1)— Used as the binary-search trap in Figma onsite — many candidates botch the boundary.
  • LeetCode Discuss (2025-12)— Surfaced in Figma OAs alongside log-position-finding questions.

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.

Constraints

  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums contains distinct values sorted in ascending order.
  • -10^4 <= target <= 10^4

Examples

Example 1

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

Example 2

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

Example 3

Input
nums = [1,3,5,6], target = 7
Output
4

Approaches

1. Linear scan

Walk until you hit target or exceed it.

Time
O(n)
Space
O(1)
function searchInsert(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] >= target) return i;
  }
  return nums.length;
}

Tradeoff: Linear. Violates the O(log n) requirement.

2. Binary search (lower-bound)

Standard binary search; on miss, lo lands on the first index >= target.

Time
O(log n)
Space
O(1)
function searchInsert(nums, target) {
  let lo = 0, hi = nums.length;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (nums[mid] < target) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

Tradeoff: Classic lower_bound template. hi = nums.length (not length-1) handles the past-the-end insertion.

Figma-specific tips

Figma interviewers treat this as the gateway problem for binary search — they want to see you use 'hi = length' (open interval) rather than 'length-1' (closed interval), since the lower-bound pattern is what their CRDT op-log insertion code uses. State the invariant before coding: 'nums[lo..hi) contains the answer.' That sentence often decides whether you advance past the screen.

Common mistakes

  • Using hi = nums.length - 1 — fails when target is larger than every element.
  • Returning mid on equality — works but obscures the lower-bound pattern; cleaner to merge the branches.
  • Off-by-one in the recurrence — write the invariant down before coding.

Follow-up questions

An interviewer at Figma may pivot to one of these next:

  • Find First and Last Position (LC 34) — pair of lower_bound + upper_bound.
  • Insert into a sorted CRDT log — generalize to fractional indices.
  • Search in Rotated Sorted Array (LC 33).

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why hi = nums.length and not nums.length - 1?

Because the answer can BE nums.length (when target is bigger than everything). Half-open interval [lo, hi) naturally accommodates that.

When do I exit?

When lo === hi the interval is empty and lo is the insertion point. It works for both 'found' (target sits at lo) and 'not found' (target would go at lo).

Practice these live with InterviewChamp.AI

Drill Search Insert Position and other Figma interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →