LeetCode 35: Search Insert Position - All Approaches Explained

Problem Statement

The Search Insert Position problem, LeetCode 35, is an easy-difficulty challenge where you’re given a sorted integer array nums in ascending order and a target integer target. Your task is to find the index where target should be inserted to maintain the sorted order. If target already exists in nums, return its index. The solution must run in O(log n) time complexity.

Constraints

• 1 ≤ nums.length ≤ 10⁴.
• -10⁴ ≤ nums[i] ≤ 10⁴.
• nums contains distinct values sorted in ascending order.
• -10⁴ ≤ target ≤ 10⁴.

Example

Copy codeInput: nums = [1,3,5,6], target = 5
Output: 2
Explanation: 5 is at index 2.

Copy codeInput: nums = [1,3,5,6], target = 2
Output: 1
Explanation: 2 should be inserted at index 1 to maintain order: [1,2,3,5,6].

Copy codeInput: nums = [1,3,5,6], target = 7
Output: 4
Explanation: 7 should be inserted at the end, index 4: [1,3,5,6,7].

Copy codeInput: nums = [1,3,5,6], target = 0
Output: 0
Explanation: 0 should be inserted at the start, index 0: [0,1,3,5,6].

Understanding the Problem

We need to find the correct insertion point for target in a sorted array with no duplicates, in O(log n) time, suggesting binary search. Key points:

• If target exists, its index is the answer.
• If not, the answer is the index where target would fit (where nums[i-1] < target <= nums[i]).
• The array is sorted, so we can leverage this property. Let’s explore two approaches:

1. Linear Search : Simple but inefficient.
2. Binary Search : Optimized solution (best approach).

Approach 1: Linear Search

Intuition

Scan the array from left to right until we find target or a position where target should be inserted based on the sorted order.

How It Works

• Iterate through nums.
• If nums[i] >= target, return i (insertion point or match).
• If we reach the end, return the length of the array (insert at end).

Step-by-Step Example

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

• i=0: 1 < 2, continue.
• i=1: 3 > 2, return 1 (insert before 3).
• Result: 1.
004aad

Python Code

Copy codedef searchInsert_linear(nums, target):
    for i in range(len(nums)):
        if nums[i] >= target:
            return i
    return len(nums)

# Test cases
print(searchInsert_linear([1,3,5,6], 5))  # Output: 2
print(searchInsert_linear([1,3,5,6], 2))  # Output: 1
print(searchInsert_linear([1,3,5,6], 7))  # Output: 4
print(searchInsert_linear([1,3,5,6], 0))  # Output: 0

Detailed Walkthrough

• Iteration : Stops at first element ≥ target.
• For [1,3,5,6], target=7:
  • All elements < 7, return 4 (end).
• Straightforward but slow.

Complexity

• Time Complexity : O(n). Linear scan.
• Space Complexity : O(1). No extra space.

Pros and Cons

• Pros : Simple to implement.
• Cons : Doesn’t meet O(log n) requirement.

Approach 2: Binary Search (Best Approach)

Intuition

Since the array is sorted with no duplicates, use binary search to find the insertion point efficiently. The key is that when the search terminates, the left pointer naturally ends up at the position where target should be inserted. This is the best approach because it achieves O(log n) time, leverages the sorted property, and is the expected interview solution.

How It Works

• Use two pointers: left and right.
• Compute mid and compare nums[mid] with target:
  • If equal, return mid.
  • If less, search right half (left = mid + 1).
  • If greater, search left half (right = mid - 1).
• When left > right, left is the insertion point.

Step-by-Step Example

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

• Left=0, Right=3, Mid=1:
  • nums[mid]=3 > 2, right=0.
• Left=0, Right=0, Mid=0:
  • nums[mid]=1 < 2, left=1.
• Left=1, Right=0: Stop, return 1 (insert at 1).

For nums = [1,3,5,6], target = 5:

• Left=0, Right=3, Mid=1:
  • nums[mid]=3 < 5, left=2.
  004aad
• Left=2, Right=3, Mid=2:
  • nums[mid]=5 = 5, return 2.

Python Code (Best Approach)

Copy codedef searchInsert(nums, target):
    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

# Test cases
print(searchInsert([1,3,5,6], 5))  # Output: 2
print(searchInsert([1,3,5,6], 2))  # Output: 1
print(searchInsert([1,3,5,6], 7))  # Output: 4
print(searchInsert([1,3,5,6], 0))  # Output: 0

Detailed Walkthrough

• Binary Search : Narrows down to insertion point.
• For [1,3,5,6], target=7:
  • Mid=1, 3<7, left=2.
  • Mid=2, 5<7, left=3.
  • Mid=3, 6<7, left=4.
  • Left=4, return 4.
• For [1,3,5,6], target=0:
  • Mid=1, 3>0, right=0.
  • Mid=0, 1>0, right=-1.
  • Left=0, return 0.
• left always ends at the insertion position.

Complexity

• Time Complexity : O(log n). Binary search halves the search space.
• Space Complexity : O(1). Only uses pointers.

Why It’s the Best

• Meets O(log n) requirement.
• Efficiently finds exact or insertion position.
• Standard interview solution for binary search.

Comparison of Approaches

Edge Cases to Consider

1. Target less than all : [1,3,5], target=0 → 0.
2. Target greater than all : [1,3,5], target=6 → 3.
3. Target in middle : [1,3,5], target=2 → 1.
4. Single element : [1], target=1 → 0; target=2 → 1.

Final Thoughts

• Linear Search : Correct but inefficient.
• Binary Search : The best approach —fast, meets constraints, and elegant. Master this binary search technique for its simplicity and interview relevance. Try modifying it to handle duplicates as a follow-up challenge!