Blog

Search Insert Position (Solution For Leetcode Problem #35)

  • Post last modified:December 15, 2022
  • Reading time:3 mins read

Java Solution for :  https://leetcode.com/problems/search-insert-position/

Understanding Problem

  • We have been given a sorted input array of distinct integers and a target value.
  • Our task is to find the position of the target value in the input array if its found, if it is not found then we need to return the position where we can insert this element to keep the sorted order.
  • For example,

nums = [1,2,3,5] , target = 5
result = 3

nums = [1,3,5,6], target = 4
result = 2

My Thought About Solution

  • The solution looks pretty simple to me. We can have some case checked to decide the solution.
  • We can iterate each element in the array and check some cases
    Case 1: if the target element is the current element then return the index of the current element
    Case 2: if the target element is smaller than current element and current element is the first element in the input array then return the index of the current element
    Case 3: if the target element is greater than the current element and smaller than the next element then return the current element index +1 since we need to insert the element in the between current and next element.
    Case 4: if the current element is the last element in the input array and the target is greater than it then the index would be the nums.length & return it
  • Data Structure & Complexity: 
    we just use int to store index and don’t use any data structure to store our output, input is an array and we just check elements at each index and don’t modify the input.
    time complexity = O(n) we just need one pass for the loop, n is the length of the input array
    space complexity = constant space, we just use int variable for storing an index

Pseudocode

1: traversed each element in nums
   case 1: if target == current_element , return current_element_index
    
   case 2: if target > current_element && target < next_element, return current_element_index+1;

     case 3: if target > current_element && current_element is last element, return input_array_length as index
   
   case 4: if target < current_element && current element is first element , return start index i.e 0 as index

2: return the search_index which we received after traversing each element in the loop

Solutions



Result

Our solution passes all the test cases and is accepted by Leetcode. The runtime is 0 ms and it beats 100% of the java solution.

Conclusion

This Leetcode problem is a very simple and good code for beginners to start with. Beginners can learn about loop traversing and comparing various conditions through if-else if or switch statements.

Let me know if you have some opinions on the solutions in the comment section!

Bonus Tip

  • If you want to upskill your coding interview game, you can definitely check out this bestseller course ( this is in Java )

Happy Leetcoding!

Tags: , , ,

Leave a Reply