Skip to main content

6. Search Insert Position

easyAsked at Plaid

Find the index where a target value should be inserted into a sorted array. Plaid asks this because finding the slot to splice a new ledger entry into a sorted journal is exactly this primitive.

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

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • LeetCode Discuss (2026)— Plaid OA — sorted ledger insertion variant.
  • Blind (2025)— Plaid backend screen — find insert position for sorted timestamps.

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 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 find a number >= target.

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: Misses the O(log n) requirement. Mention only as the naive starting point.

2. Binary search lower bound

Standard lower-bound binary search — converges on the leftmost index where nums[i] >= 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 half-open interval [lo, hi). hi = nums.length (not length-1) is the key — it returns the insert-at-end position naturally.

Plaid-specific tips

Plaid grades binary search on whether your invariants are crisp. Articulate the loop invariant ('answer is in [lo, hi)') before coding. Bonus signal: name this as a 'lower bound' search and mention how it generalizes to merging sorted webhook batches into a master timeline.

Common mistakes

  • Using hi = nums.length - 1 — misses the insert-at-end case.
  • Off-by-one in the loop condition (<= vs <) — easy to underflow or skip the correct answer.
  • Using (lo + hi) / 2 in languages where integer overflow matters — JS is fine but mention the awareness.

Follow-up questions

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

  • Return the rightmost position (upper bound) instead.
  • Search Range — find both the first and last occurrence of a value (LC 34).
  • Generalize to find the position where a new transaction by timestamp belongs in a sorted journal.

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 half-open [lo, hi)?

It collapses cleanly: when lo == hi the answer is exactly lo. The closed-interval [lo, hi] variant requires more careful handling of hi = mid - 1.

What if duplicates are allowed?

Lower bound returns the first occurrence; upper bound returns one-past-last. Decide which the caller wants — Plaid usually wants 'first slot for chronological order'.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →