35. Search Insert Position LeetCode Solution

In this guide we will provide 35. Search Insert Position LeetCode Solution with best time and space complexity. The solution to Search Insert Position problem is provided in various programming languages like C++, Java and python. This will be helpful for you if you are preparing for placements, hackathon, interviews or practice purposes. The solutions provided here are very easy to follow and with detailed explanations.

Table of Contents

• Problem Statement
• Complexity Analysis
• Search Insert Position solution in C++
• Search Insert Position soution in Java
• Search Insert Position solution Python
• Additional Resources

Problem Statement of Search Insert Position

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [1,3,5,6], target = 5
Output: 2

Example 2:

Input: nums = [1,3,5,6], target = 2
Output: 1

Example 3:

Input: nums = [1,3,5,6], target = 7
Output: 4

Constraints:

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums contains distinct values sorted in ascending order.
-104 <= target <= 104

Complexity Analysis

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

35. Search Insert Position LeetCode Solution in C++

class Solution {
 public:
  int searchInsert(vector<int>& nums, int target) {
    int l = 0;
    int r = nums.size();

    while (l < r) {
      const int m = (l + r) / 2;
      if (nums[m] == target)
        return m;
      if (nums[m] < target)
        l = m + 1;
      else
        r = m;
    }

    return l;
  }
};
/* code provided by PROGIEZ */

35. Search Insert Position LeetCode Solution in Java

class Solution {
  public int searchInsert(int[] nums, int target) {
    int l = 0;
    int r = nums.length;

    while (l < r) {
      final int m = (l + r) / 2;
      if (nums[m] == target)
        return m;
      if (nums[m] < target)
        l = m + 1;
      else
        r = m;
    }

    return l;
  }
}
// code provided by PROGIEZ

35. Search Insert Position LeetCode Solution in Python

class Solution:
  def searchInsert(self, nums: list[int], target: int) -> int:
    l = 0
    r = len(nums)

    while l < r:
      m = (l + r) // 2
      if nums[m] == target:
        return m
      if nums[m] < target:
        l = m + 1
      else:
        r = m

    return l
 #code by PROGIEZ

Additional Resources

• Explore all Leetcode problems solutions at Progiez here
• Explore all problems on Leetcode website here

Feel free to give suggestions! Contact Us