Vansh Aggarwal

Posted on Apr 25

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

#leetcode #dsa #programming #tutorial

Uncover the Hidden Range: Finding First & Last Occurrences in Sorted Arrays (LeetCode #34)

Hey everyone! Vansh2710 here, diving deep into another classic LeetCode problem that might seem tricky at first, but unravels beautifully with a touch of algorithmic magic. Today, we're tackling problem #34: Find First and Last Position of Element in Sorted Array.

This problem is a fantastic way to stretch your understanding of one of the most fundamental algorithms: Binary Search! Ready to find those elusive boundaries? Let's get started!

Problem Explanation

Imagine you have a super organized bookshelf where all the books are sorted alphabetically. Now, someone asks you to find all copies of "The Great Gatsby" and tell them exactly where the first one starts and the last one ends on the shelf. That's essentially what we're doing here!

Given an array of integers nums that is already sorted in non-decreasing order (meaning numbers are either increasing or staying the same), and a specific target integer:

We need to find the starting index (first occurrence) and the ending index (last occurrence) of the target value in nums.
If the target isn't found anywhere in the array, we should return [-1, -1].
Crucially, your solution must run in O(log n) time complexity. This is a massive hint!

Let's look at the examples:

Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
(The first '8' is at index 3, the last '8' is at index 4)

Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
(6 is not in the array)

Example 3:
Input: nums = [], target = 0
Output: [-1,-1]
(Empty array, target cannot be found)

Constraints to keep in mind:

The array nums can be empty or have up to 10^5 elements.
Numbers and target can be quite large or small (negative values included).
nums is guaranteed to be sorted non-decreasingly.

Intuition: The "Aha!" Moment

The moment you see "sorted array" and "O(log n) runtime complexity" in the same sentence, your brain should immediately yell "BINARY SEARCH!" 🚀

A standard binary search is excellent for telling you if an element exists in a sorted array, and if so, it typically returns one of its indices. But here, we need two specific indices: the very first and the very last.

So, how do we adapt our trusty binary search? Instead of stopping once we find the target, we need to keep searching!

If we find the target and we're looking for the first occurrence, we mark that index as a potential answer, but then we try to find an even earlier target by searching in the left half of the current segment.
Conversely, if we find the target and we're looking for the last occurrence, we mark that index and then try to find an even later target by searching in the right half.

This tweak transforms our standard binary search into a powerful tool for finding boundaries!

Approach: Two-Pronged Binary Search

Our strategy will involve two separate, slightly modified binary searches:

find_first_occurrence(nums, target): This function will find the index of the first target in the array.
find_last_occurrence(nums, target): This function will find the index of the last target in the array.

Let's detail each one:

1. Finding the First Occurrence

Initialize ans = -1 (this will store our result, default to not found).
Set start = 0 and end = len(nums) - 1.
While start <= end:
- Calculate mid = start + (end - start) // 2 to prevent potential integer overflow.
- If nums[mid] == target:
  - We found the target! This mid could be our first occurrence. Store it: ans = mid.
  - But wait, there might be an even earlier target to its left. So, we try to shrink our search space to the left: end = mid - 1.
- If nums[mid] < target:
  - The target must be in the right half (or not present). So, search right: start = mid + 1.
- If nums[mid] > target:
  - The target must be in the left half (or not present). So, search left: end = mid - 1.
Return ans.

2. Finding the Last Occurrence

Initialize ans = -1.
Set start = 0 and end = len(nums) - 1.
While start <= end:
- Calculate mid = start + (end - start) // 2.
- If nums[mid] == target:
  - We found the target! This mid could be our last occurrence. Store it: ans = mid.
  - But wait, there might be an even later target to its right. So, we try to shrink our search space to the right: start = mid + 1.
- If nums[mid] < target:
  - The target must be in the right half (or not present). So, search right: start = mid + 1.
- If nums[mid] > target:
  - The target must be in the left half (or not present). So, search left: end = mid - 1.
Return ans.

Finally, our main searchRange function will simply call these two helper functions and return their results as [first_occurrence, last_occurrence].

Code

class Solution:
    def searchRange(self, nums: list[int], target: int) -> list[int]:
        # Helper function to find the first occurrence of the target
        def find_first_occurrence(arr: list[int], val: int) -> int:
            ans = -1
            left, right = 0, len(arr) - 1
            while left <= right:
                mid = left + (right - left) // 2
                if arr[mid] == val:
                    ans = mid      # Potentially the first occurrence
                    right = mid - 1 # Try to find an even earlier occurrence in the left half
                elif arr[mid] < val:
                    left = mid + 1
                else: # arr[mid] > val
                    right = mid - 1
            return ans

        # Helper function to find the last occurrence of the target
        def find_last_occurrence(arr: list[int], val: int) -> int:
            ans = -1
            left, right = 0, len(arr) - 1
            while left <= right:
                mid = left + (right - left) // 2
                if arr[mid] == val:
                    ans = mid     # Potentially the last occurrence
                    left = mid + 1 # Try to find an even later occurrence in the right half
                elif arr[mid] < val:
                    left = mid + 1
                else: # arr[mid] > val
                    right = mid - 1
            return ans

        first = find_first_occurrence(nums, target)
        last = find_last_occurrence(nums, target)

        return [first, last]

Time & Space Complexity Analysis

Let's break down the efficiency of our solution:

Time Complexity: O(log n)

We perform two independent binary searches: find_first_occurrence and find_last_occurrence.
Each binary search operates on a sorted array of n elements and halves its search space in each step. This gives each individual search a time complexity of O(log n).
Since we do two of these operations sequentially, the total time complexity is O(log n) + O(log n), which simplifies to O(log n).
This perfectly satisfies the problem's constraint!

Space Complexity: O(1)

Our solution uses a few constant variables (left, right, mid, ans).
We are not using any auxiliary data structures that grow with the input size n (like extra arrays or lists).
Therefore, the space complexity is O(1).

Key Takeaways

Binary Search Power-Up: Binary search isn't just for checking existence! By carefully adjusting the start and end pointers when nums[mid] == target, you can find specific boundaries like first/last occurrences, smallest element greater than target, etc.
Two Searches for Two Boundaries: For problems requiring both a start and an end index in a sorted array, often two slightly modified binary searches are the most straightforward and efficient approach.
Edge Cases: Always consider empty arrays or cases where the target isn't found. Our solution handles these gracefully by initializing ans = -1 and letting the binary search naturally return it if no target is ever found.
mid Calculation: Using mid = left + (right - left) // 2 is a good practice to prevent potential integer overflow, especially in languages like C++ where left + right could exceed MAX_INT for very large left and right. In Python, this is less critical due to arbitrary precision integers, but it's a good habit!

Hopefully, this breakdown helps you understand how to approach range-finding problems in sorted arrays! Keep practicing, and you'll master these variations in no time. Happy coding!

Author Account: Vansh2710
Time Published: 2026-04-25 23:25:30

DEV Community