Search Insert Position Leetcode Solution

In this problem, we are given a sorted array and a target integer. We have to find its Search Insert Position.

1. If the target value is present in the array, return its index.
2. Return the index at which the target should be inserted so as to keep the order sorted(in non-decreasing manner).

Example

1 2 3 4 5 
Target = 3

2

1 3 5 7 9
Target = 8

4

Explanation

Approach(Linear Search)

We can run a loop to find the first index whose value exceeds or equals the target value. Proof:

• If the value equals, then this index is the required index.
• Target would have been inserted at this position, otherwise.

Algorithm

1. Run a loop from first index to the end of the array
2. If array[i] exceeds or equals target value, then return i
3. return n, as we found no index such that array[index] >= target, so target should be inserted in the end
4. Print the result

Implementation of algorithm to find Search Insert Position of Target

C++ Program

#include <bits/stdc++.h>
using namespace std;

int searchInsert(vector<int>& a, int target)
{
    int n = a.size();
    for(int i = 0 ; i < n ; i++)
    {
        if(a[i] >= target)
            return i;
    }
    return n;
}


int main()
{
    vector <int> a = {1 , 3 , 5 , 7 , 9};
    int target = 8;
    cout << searchInsert(a , target) << '\n';
}

Java Program

class search_insert_position
{
    static int searchInsert(int[] a , int target)
    {
        int n = a.length;
        for(int i = 0 ; i < n ; i++)
        {
            if(a[i] >= target)
                return i;
        }
        return n;
    }

    public static void main(String args[])
    {
        int a[] = {1 , 3 , 5 , 7 , 9} , target = 8;
        System.out.println(searchInsert(a , target));
    }
}

4

Complexity Analysis of finding Search Insert Position of Target

Time Complexity

O(N), where N = size of the array. In the worst case, we need to append the target at the end of the array.

Space complexity

O(1). We use constant space for variables.

Approach(Binary Search)

The array is sorted. The first conclusion that we can make from this is: If the value at some index idx is less than the target, then there is no need to check elements which are left to idx, as they would be even smaller. So we can use a Binary Search to find the Search Insert Position.

Algorithm

1. Create a binarySearch() function that returns the required index
2. Initialize ans = 0, which will store the required index
3. Set left and right limits as 0 and N – 1 respectively, N = size of the array
4. Until left <= right
   • Find the middle index of these limits as mid = left+ right / 2
   • If a[mid] == target, return mid
   • In case the value is greater, we move to the left half using right = mid – 1 and save ans = mid
   • This leaves the case when a[mid] < target, we save ans = mid + 1 and move to the right half using left = mid + 1
   • Return ans
5. Print the result

Implementation of algorithm to find Search Insert Position of Target Leetcode Solution

C++ Program

#include <bits/stdc++.h>
using namespace std;

int binarySearch(vector <int> &a , int target)
{
    int l = 0 , r = (int)a.size() - 1 , mid , ans = -1;
    while(l <= r)
    {
        mid = l + (r - l) / 2;
        if(a[mid] == target)
            return mid;
        if(a[mid] < target)
        {
            l = mid + 1;
            ans = mid + 1;
        }
        else
        {
            ans = mid;
            r = mid - 1;
        }
    }
    return ans;
}

int searchInsert(vector<int>& a, int target)
{
    return binarySearch(a , target);
}

int main()
{
    vector <int> a = {1 , 3 , 5 , 7 , 9};
    int target = 8;
    cout << searchInsert(a , target) << '\n';
}

Java Program

class search_insert_position
{
    static int binarySearch(int[] a , int target)
    {
        int l = 0 , r = a.length - 1 , mid , ans = -1;
        while(l <= r)
        {
            mid = l + (r - l) / 2;
            if(a[mid] == target)
                return mid;
            if(a[mid] < target)
            {
                l = mid + 1;
                ans = mid + 1;
            }
            else
            {
                ans = mid;
                r = mid - 1;
            }
        }
        return ans;
    }

    static int searchInsert(int[] a , int target)
    {
        return binarySearch(a , target);
    }

    public static void main(String args[])
    {
        int a[] = {1 , 3 , 5 , 7 , 9} , target = 8;
        System.out.println(searchInsert(a , target));
    }
}

4

Complexity Analysis of finding Search Insert Position of Target Leetcode Solution

Time Complexity

O(logN). In the worst case, we can make logN comparisons.

 Space complexity

O(1). Again, we use constant space for variables.