6. Search Insert Position
easyAsked at GojekGiven a sorted array and a target, return the index if found, else the index where it should be inserted.
By Sam K., 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^4nums has distinct values
Examples
Example 1
nums = [1,3,5,6], target = 52Example 2
nums = [1,3,5,6], target = 21Approaches
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.