6. Search Insert Position
easyAsked at MonzoFind the index where a transaction amount should be inserted to keep an array sorted.
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 it were inserted in order. You must write an algorithm with O(log n) runtime complexity.
Constraints
1 <= nums.length <= 10^4Sorted ascending
Examples
Example 1
Input
nums = [1,3,5,6], target = 5Output
2Example 2
Input
nums = [1,3,5,6], target = 2Output
1Approaches
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 binary search; return left on miss.
- 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:
Monzo-specific tips
Monzo expects lower-bound binary search to be muscle memory — it appears in their statement-merging and rate-table lookup code.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.