Leetcode 35 Solution

This article provides solution to leetcode question 35 (search-insert-position)
Categories:
Tags:
Access this page by simply typing in "lcs 35" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/search-insert-position

Thinking Process

Very basic binary search problem. Using our binary search framework. The condition function is f(x) = (x >= target). Put it in the binary_search_template, we get the final result.

Time & Space Complexity

Assuming N is the size of the array:

  • Time complexity: O(lg N)
  • Space complexity: O(1)

Solution

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

        while l < r:
            m = (l + r) // 2

            if nums[m] >= target:
                r = m
            else:
                l = m + 1

        return l if nums[l] >= target else len(nums)