Skip to main content

6. Search Insert Position

easyAsked at Duolingo

Find the index where target appears or should be inserted to keep the array sorted.

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

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 should be inserted in order to keep the array sorted.

Constraints

  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i], target <= 10^4
  • nums has distinct values, sorted ascending

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

Approaches

1. Linear scan

Walk until you find a value >= target.

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

Tradeoff:

2. Binary search lower bound

Maintain [lo, hi] and bisect; the final lo is the insertion point. Classic lower-bound binary search.

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:

Duolingo-specific tips

Duolingo schedulers binary-search into sorted review-due timestamps thousands of times per session—nail the half-open invariant on whiteboards.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →