Site icon Study Algorithms

[Leetcode] – Search Insert Position Solution

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

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.

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.

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:

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:

Exit mobile version