Scale Engineer

Search Insert Position

Easy
#0035Time: O(n)Space: O(1)11 companies
Algorithms
Binary Search
Data structures
Array
Companies
AdobeAmazonAppleBloomberg

Prompt

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.

 

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

 

Constraints:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums contains distinct values sorted in ascending order.
  • -104 <= target <= 104

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves iterating through the array from the beginning to find the target or its insertion point. It's straightforward but less efficient.

Algorithm

  1. Iterate through the array nums from index i = 0 to n-1.
  2. For each element nums[i], check if it is greater than or equal to the target.
  3. If nums[i] >= target, return the current index i.
  4. If the loop completes, it means the target should be inserted at the end. Return the length of the array.

Walkthrough

We can traverse the array nums with a single loop. For each element nums[i], we compare it with the target. If nums[i] is greater than or equal to the target, we've found the correct position. This is because the array is sorted, so any subsequent element will also be greater. If we find such an element, we return its index i. If the loop finishes without finding any element greater than or equal to the target, it implies that the target is larger than all elements in the array. In this case, the correct insertion position is at the very end of the array, so we return the length of the array.

class Solution {    public int searchInsert(int[] nums, int target) {        for (int i = 0; i < nums.length; i++) {            if (nums[i] >= target) {                return i;            }        }        return nums.length;    }}

Complexity

Time

O(n)

Space

O(1)

Trade-offs

Pros

  • Simple to understand and implement.

  • Works correctly for all cases.

Cons

  • Inefficient for large input arrays.

  • Does not meet the O(log n) time complexity requirement specified in the problem description.

Solutions

class Solution {public  int searchInsert(int[] nums, int target) {    int left = 0, right = nums.length;    while (left < right) {      int mid = (left + right) >>> 1;      if (nums[mid] >= target) {        right = mid;      } else {        left = mid + 1;      }    }    return left;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem