LeetCode Problem-6 (Search Insert Position)

Search Insert Position

Today, we’re diving into a popular problem often encountered on coding platforms like LeetCode. It’s a fantastic exercise for those looking to sharpen their algorithm skills, especially in binary search and understanding time complexity. The problem statement is straightforward yet intriguing:

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. The challenge? Your solution should run in O(log n) time complexity.

Let’s break down the problem with examples before jumping into the solution.

Problem Examples

• 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

These examples illustrate the task: find where the target fits in the sorted list, either as an existing member or where it should be inserted to maintain order.

A Simple Approach

One straightforward method to solve this problem is as follows:

1. Check if the target exists in the array: If it does, return its index immediately.
2. If not found, insert the target into the array: Append the target to the array, sort the array again, and return the new index of the target.

Here’s how this approach looks in code:

pythonCopy codeclass Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        if target in nums:
            return nums.index(target)
        else:
            nums.append(target)
            nums.sort()
            return nums.index(target)

This solution is intuitive and will work correctly for any input. However, it does not meet the O(log n) time complexity requirement due to the sorting step, which can be O(n log n) in the worst case. Despite its simplicity, this approach is not the most efficient for large datasets.

The Efficient Approach: Binary Search

To achieve O(log n) complexity, a binary search algorithm is ideal. Binary search efficiently narrows down the search space by comparing the target with the middle element of the array and deciding which half of the array to continue searching in.

Here’s a more efficient solution that adheres to the problem’s time complexity requirement:

pythonCopy codeclass Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        
        while left <= right:
            mid = (left + right) // 2
            
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        
        return left

In this approach, we:

1. Initialize two pointers to indicate the start (left) and end (right) of the array.
2. Continuously narrow our search to the relevant half of the array until the left exceeds right.
3. If the target is found, return its index. If not, left will point to where the target should be inserted.

Why Binary Search?

Binary search is favored for its efficiency in handling sorted data, especially large datasets. By halving the search space with each iteration, it drastically reduces the number of comparisons needed to find the target or its insert position, achieving O(log n) runtime complexity.