LeetCode 35: Search Insert Position Solution in Python Explained

Problem Statement

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

Constraints

  • 1 <= nums.length <= 10^4: Array length is between 1 and 10,000.
  • -10^4 <= nums[i], target <= 10^4: Elements and target are within this range.
  • nums contains distinct values sorted in ascending order.

Example

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

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

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

Understanding the Problem

How do you solve LeetCode 35: Search Insert Position in Python? For nums = [1,3,5,6] and target = 5, return 2 (its index). For target = 2, return 1 (where 2 fits between 1 and 3). The array is sorted with no duplicates, so binary search can efficiently find the position. We’ll explore two approaches: a Binary Search Solution (optimal and primary) and an Alternative with Linear Search (simple but slower). The binary search method achieves O(log n) time by finding the insertion point directly.

Solution 1: Binary Search Approach (Primary)

Explanation

Use binary search to find the insertion point. Since the array is sorted, the final left pointer will indicate where target should go—either its existing index or the position where it would fit. Compare target with the middle element and adjust the search range accordingly.

Here’s a visual for [1,3,5,6], target = 2:

Initial: left = 0, right = 3, mid = 1 (3)
3 > 2: right = 0, mid = 0 (1)
1 < 2: left = 1
left = 1 (insert position)
  1. Initialize Pointers.
  • left = 0, right = len(nums) - 1.
  1. Binary Search.
  • Adjust bounds based on nums[mid] vs. target.
  1. Return Insertion Point.
  • left is the answer after the loop.

Step-by-Step Example

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

We need index 2.

  • Goal: Find position of 5.
  • Result for Reference: 2.
  • Start: nums = [1,3,5,6], left = 0, right = 3.
  • Step 1: mid = 1, nums[1] = 3 < 5, left = 2.
  • Step 2: mid = 2, nums[2] = 5 = 5, found, return 2.
  • Finish: Return 2 (or continue loop, left = 2).

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

We need index 1.

  • Goal: Find insertion point for 2.
  • Result for Reference: 1.
  • Start: left = 0, right = 3.
  • Step 1: mid = 1, nums[1] = 3 > 2, right = 0.
  • Step 2: mid = 0, nums[0] = 1 < 2, left = 1.
  • Step 3: left = 1 > right = 0, stop.
  • Finish: Return left = 1.

Example 3: nums = [1,3,5,6], target = 7

We need index 4.

  • Goal: Insert 7.
  • Start: left = 0, right = 3.
  • Step 1: mid = 1, 3 < 7, left = 2.
  • Step 2: mid = 2, 5 < 7, left = 3.
  • Step 3: mid = 3, 6 < 7, left = 4.
  • Step 4: left = 4 > right = 3, stop.
  • Finish: Return 4.

Here’s the Python code with line-by-line explanation:

def searchInsert(nums: list[int], target: int) -> int:
    # Line 1: Initialize pointers
    left, right = 0, len(nums) - 1

    # Line 2: Binary search loop
    while left <= right:
        # Line 3: Compute mid
        mid = (left + right) // 2
        # Line 4: If target found
        if nums[mid] == target:
            return mid
        # Line 5: Target in right half
        elif nums[mid] < target:
            left = mid + 1
        # Line 6: Target in left half
        else:
            right = mid - 1

    # Line 7: Return insertion point
    return left

Alternative: Linear Search Approach

Explanation

Scan the array linearly to find the first position where target is greater than or equal to an element, or the end if it’s larger than all. This is O(n) and doesn’t meet the O(log n) requirement but is intuitive.

  1. Scan Array.
  2. Find Position.
  3. Return Index.

Step-by-Step Example (Alternative)

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

  • Goal: Index 1.
  • Step 1: i = 0, 1 < 2, continue.
  • Step 2: i = 1, 3 > 2, stop.
  • Finish: Return 1.

How the Code Works (Linear)

def searchInsertLinear(nums: list[int], target: int) -> int:
    # Line 1: Scan array
    for i in range(len(nums)):
        # Line 2: If target fits here
        if nums[i] >= target:
            return i
    # Line 3: Target larger than all
    return len(nums)

Complexity

  • Binary Search:
    • Time: O(log n) – Binary search on sorted array.
    • Space: O(1) – No extra space.
  • Linear Search:
    • Time: O(n) – Single pass.
    • Space: O(1).

Efficiency Notes

Binary Search is O(log n), meeting LeetCode’s requirement, while Linear Search (O(n)) is too slow but simpler for beginners.

Key Insights

Tips to master LeetCode 35:

  • Insertion Point: left naturally lands on the answer.
  • Sorted Power: Binary search shines with order.
  • Edge Cases: Handle extremes like 0 or beyond max.

Additional Example

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

  • Goal: Index 2.
  • Binary: mid = 1, 3 < 4, left = 2, stop, return 2.
  • Result: 2.

Edge Cases

  • Single Element: [1], target = 0 – Return 0.
  • Target Smaller: [2,3,4], target = 1 – Return 0.
  • Target Larger: [1,2,3], target = 4 – Return 3.

Final Thoughts

The Binary Search solution is a breeze for LeetCode 35 in Python—fast, clean, and logarithmic. For a related challenge, explore LeetCode 34: Find First and Last Position of Element in Sorted Array to level up your binary search skills! Ready to nail it? Solve LeetCode 35 on LeetCode now and test it with arrays like [1,3,5] or targets like 0 or 7 to perfect your insertion logic. Jump in and ace it!