Skip to main content

6. Search Insert Position

easyAsked at Gojek

Given a sorted array and a target, return the index if found, else the index where it should be inserted.

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 would be if inserted in order. You must write an algorithm with O(log n) runtime.

Constraints

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

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 forward until found or exceeded.

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

Maintain [lo, hi] range. On equality return mid; otherwise close on lo when loop ends.

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:

Gojek-specific tips

Gojek interviewers expect log-N reasoning here because their dispatch service constantly does range queries on driver-location sorted indexes.

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 Gojek interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →