Insert Position in Sorted Array Editorial

Practice Problem Link: Insert Position in Sorted Array | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a sorted array containing distinct integers and a number ‘key’, find the index of the key in the array.

If the key is not present, return the index at which it would be inserted considering that we need to maintain the sort order.

Naive Approach

The simple solution is to just iterate the array and find if the key is present in the array by comparing each element of the array with the key. If the key is present then return its index otherwise return the next index of the number just less than the key.

Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Implementation

C++

int getInsertPosition(vector<int> &arr, int key) {
   int index = - 1;
   for (int i = 0; i < arr.size(); i++) {
       if (arr[i] == key) {
           return i;
       }
       if (arr[i] < key) {
           index = i;
       }
   }
   return index + 1;
}

Java

class Solution {
   int getInsertPosition (int[] arr, int key) {
       int index = - 1;
         for (int i = 0; i < arr.length; i++) {
           if (arr[i] == key) {
               return i;
           }
           if (arr[i] < key) {
               index = i;
           }
       }
       return index + 1;
   }
}

Optimal Approach

Since the array is sorted. Binary search can be used to check if the key is present in the array.

• Initialize four variables, low = 0, high = n - 1 and mid and index = -1.
• Perform a binary search while (high >= low) and assign mid = (high + low ) /  2;
• If the key is equal to arr[mid], return mid. If the key is greater than arr[mid] then assign index = mid and search for the key in the second half otherwise search for the key in the first half.
• If the key is not found then return index + 1 as the position where the key should be inserted.

Analysis

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

Implementation

C++

int indx;
int findIndex (vector<int> &arr, int low, int high, int key) {
   if (high >= low) {
       int mid = (high + low) / 2;
       if (arr[mid] == key) {
           return mid;
       } else if (arr[mid] < key) {
           indx = mid;
           return findIndex (arr, mid + 1, high, key);
       } else {
           return findIndex (arr, low, mid - 1, key);
       }
   }
   return indx + 1;
}
int getInsertPosition(vector<int> &arr, int key) {
   indx = -1;
   int n = arr.size();
   return findIndex (arr, 0, n - 1, key);
}

Java

class Solution {
   int indx;
   int findIndex (int[] arr, int low, int high, int key) {
       if (high >= low) {
           int mid = (high + low) / 2;
           if (arr[mid] == key) {
               return mid;
           } else if (arr[mid] < key) {
               indx = mid;
               return findIndex (arr, mid + 1, high, key);
           } else {
               return findIndex (arr, low, mid - 1, key);
           }
       }
       return indx + 1;
   }
   int getInsertPosition (int[] arr, int key) {
       indx = -1;
       int n = arr.length;
       return findIndex(arr, 0, n - 1, key);
   }
}