Home Arrays [Leetcode] – Search Insert Position Solution

[Leetcode] – Search Insert Position Solution

by nikoo28
0 comment 3 mins read

According to the given problem statement, we are provided a sorted array of distinct integers, and a target value. You need to search the insert position of this element such that the resultant array will remain in an increasing order. We desire a time complexity of O(\log n).

Let us understand the problem easily by a sample test case.

Input: arr = [ 1, 3, 5, 6 ]
Target value = 2
Output: 1

a sample test case
Fig: Sample test case

Now, if 2 needs to be inserted in the array, it will come between 1 and 3, such that the array remains in a non-decreasing order. Theoretically, we search the insert position of the element we want to add.

figure showing the search insert position
Fig: Search Insert Position

Brute Force Solution:

A pretty straight forward approach is a brute force solution where we start from the beginning of the array and keep on moving ahead until we see elements smaller than the target value.

a brute force solution approach
Fig: Brute Force Solution

As we traverse, we reach the element 15, and then we see 17. It clearly shows that we need to insert the element between these 2 elements and the position should be [5]. All the other elements shift once the insert actually happens.

This approach will work in O(n) time, but we need something faster.

Using Binary Search:

When we target a time complexity around O(\log n), Binary Search should be at the top of your mind. That is how we divide the problem into 2 halves and proceed.

The approach here will be very simple:

  • Choose a low index as the [0] index
  • The high index will be the last element of the array.
  • Get the mid point by mid = low + \frac{(high - low)}{2}
  • Check if the target value is greater than the left element, and smaller than the right element.
  • If yes, this is the search insert position, else update the low and high index accordingly.
using binary search to reach the result
Fig: Using Binary Search

Code:

public int searchInsert(int[] nums, int target) { int low = 0; int high = nums.length - 1; while (low <= high) { int mid = low + (high - low) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] > target) { high = mid - 1; } else { low = mid + 1; } } return low; }
Code language: Java (java)

Time Complexity: O(\log n)
Space Complexity: O(1)

Video Explanation:

You may also like

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More