LeetCode Solution: 34. Find First and Last Position of Element in Sorted Array

#leetcode #dsa #programming #tutorial

Finding Your Way: First and Last Occurrences in a Sorted Array (LeetCode 34 Explained!)

Hey there, future coding rockstars! 👋 Vansh here, and today we're diving into a super common, yet incredibly insightful problem from LeetCode: "Find First and Last Position of Element in Sorted Array."

This problem is a fantastic way to level up your understanding of one of the most fundamental algorithms out there: Binary Search. While simple binary search finds if an element exists, this problem challenges us to find its boundaries in a sorted list. Let's break it down!

🔍 Problem Explanation: What are We Even Doing?

Imagine you have a phonebook (remember those?) where all names are sorted alphabetically. Now, imagine you're looking for every "Smith" in that phonebook. You don't just want any Smith; you want to know where the first "Smith" starts and where the last "Smith" ends. That's exactly what this problem asks!

Formally, we're given:

An array of integers nums. Crucially, this array is sorted in non-decreasing order (meaning numbers either stay the same or go up).
A target integer value.

Our mission:

Find the starting index (first occurrence) of target.
Find the ending index (last occurrence) of target.
Return these as an array [start_index, end_index].
If the target isn't found anywhere in nums, we should return [-1, -1].

The kicker? We must do this with an O(log n) runtime complexity. This is a strong hint for using Binary Search!

Let's look at a few examples:

Example 1: nums = [5,7,7,8,8,10], target = 8

The first 8 is at index 3.
The last 8 is at index 4.
Output: [3, 4]

Example 2: nums = [5,7,7,8,8,10], target = 6

6 is not in the array.
Output: [-1, -1]

Example 3: nums = [], target = 0

The array is empty. 0 can't be found.
Output: [-1, -1]

🤔 Intuition: The "Aha!" Moment

When you see a sorted array and an O(log n) complexity requirement, your brain should immediately scream: BINARY SEARCH!

A standard binary search helps you find if an element exists and its index. But here, if target appears multiple times, a standard binary search might give you any of its occurrences, not necessarily the first or last.

The "aha!" moment is realizing that we can adapt binary search to specifically look for the leftmost (first) occurrence and then, with a slight modification, for the rightmost (last) occurrence.

Think about it:

To find the first occurrence: If we find the target at mid, we store this mid as a potential answer, but then we try to find an even earlier target by continuing our search in the left half of the current array (end = mid - 1).
To find the last occurrence: If we find the target at mid, we store this mid as a potential answer, but then we try to find an even later target by continuing our search in the right half of the current array (start = mid + 1).

This way, we "squeeze" our search space until we pinpoint the extreme positions!

🪜 Approach: Step-by-Step Logic

We'll essentially perform two separate binary searches: one for the first occurrence and one for the last occurrence.

Let's define a helper function, say find_occurrence(nums, target, find_first), that can do both based on a flag.

1. `find_occurrence(nums, target, find_first)` Function Logic:

Initialize ans = -1. This will store our found index.
Initialize start = 0 and end = len(nums) - 1. These define our search space.
While start <= end:
- Calculate mid = start + (end - start) // 2. (Using (end - start) // 2 instead of (start + end) // 2 helps prevent potential integer overflow for very large start and end values, though less critical in Python).
- Case 1: nums[mid] == target
  - We found a target! Store mid in ans.
  - Now, the crucial part:
    - If find_first is True (we're looking for the first occurrence): We know mid could be our first, but there might be an even earlier one. So, we shrink our search space to the left: end = mid - 1.
    - If find_first is False (we're looking for the last occurrence): We know mid could be our last, but there might be an even later one. So, we shrink our search space to the right: start = mid + 1.
- Case 2: nums[mid] < target
  - The target must be in the right half (if it exists). Shift our search to the right: start = mid + 1.
- Case 3: nums[mid] > target
  - The target must be in the left half (if it exists). Shift our search to the left: end = mid - 1.
Return ans.

2. Main Function Logic:

Call find_occurrence(nums, target, True) to get the first_occurrence.
Call find_occurrence(nums, target, False) to get the last_occurrence.
Return [first_occurrence, last_occurrence].

This elegant modification to binary search allows us to pinpoint both boundaries efficiently!

💻 Code

Here's the Python implementation based on our approach:

class Solution:
    def searchRange(self, nums: list[int], target: int) -> list[int]:

        def find_occurrence(nums, target, find_first):
            """
            Helper function to find either the first or last occurrence of the target.

            Args:
                nums (list): The sorted array.
                target (int): The value to search for.
                find_first (bool): If True, search for the first occurrence.
                                   If False, search for the last occurrence.

            Returns:
                int: The index of the found occurrence, or -1 if not found.
            """
            ans = -1
            start = 0
            end = len(nums) - 1

            while start <= end:
                mid = start + (end - start) // 2

                if nums[mid] == target:
                    ans = mid  # Store potential answer
                    if find_first:
                        end = mid - 1 # Try to find an even earlier occurrence on the left
                    else:
                        start = mid + 1 # Try to find an even later occurrence on the right
                elif nums[mid] < target:
                    start = mid + 1 # Target is in the right half
                else: # nums[mid] > target
                    end = mid - 1 # Target is in the left half
            return ans

        # Find the first occurrence
        first_pos = find_occurrence(nums, target, True)

        # Find the last occurrence
        last_pos = find_occurrence(nums, target, False)

        return [first_pos, last_pos]

⏱️ Time & Space Complexity Analysis

Time Complexity: O(log n)
- We perform two independent binary searches. Each binary search takes O(log n) time because we repeatedly halve the search space. Therefore, O(log n) + O(log n) simplifies to O(log n). This satisfies the problem's constraint!
Space Complexity: O(1)
- We only use a few constant extra variables (start, end, mid, ans). We don't allocate any data structures that grow with the input size n.

💡 Key Takeaways

Binary Search is your best friend for sorted arrays! Always consider it when you see "sorted" and "O(log n)".
Binary Search isn't just for exact matches. It's a versatile algorithm that can be adapted to find boundaries, closest elements, and more, with slight modifications to its core logic (especially how you adjust start and end when nums[mid] == target).
Modularize your code. Breaking down the problem into a helper function for find_occurrence makes the main searchRange function clean, readable, and less repetitive.

This problem is a fantastic stepping stone from basic binary search to more complex variations. Master this, and you'll be well on your way to tackling trickier search problems!

Happy coding! ✨

Author: Vansh2710 | Published: 2026-05-01 23:33:33

DEV Community

LeetCode Solution: 34. Find First and Last Position of Element in Sorted Array

Finding Your Way: First and Last Occurrences in a Sorted Array (LeetCode 34 Explained!)