Vansh Aggarwal

Posted on Mar 24

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

#leetcode #dsa #programming #tutorial

Cracking LeetCode 34: Finding Elements' First and Last Homes in a Sorted Array (The Binary Search Way!)

Hey fellow coders! 👋 Vansh2710 here, diving into another exciting LeetCode challenge. Today, we're tackling problem 34: Find First and Last Position of Element in Sorted Array. Don't let the name intimidate you – this problem is a fantastic way to deepen your understanding of a fundamental algorithm: Binary Search!

Ready to level up your searching skills? Let's go!

The Problem: Where Does My Target Live?

Imagine you have a super organized list of numbers, sorted from smallest to largest. Your task is simple: find a specific number (let's call it target) in this list. But there's a twist! If the target appears multiple times, you don't just need to know if it's there; you need to find the very first spot it shows up and the very last spot it appears.

If the target isn't in your list at all, you should return [-1, -1].

Let's look at an example:

Suppose your list nums is [5, 7, 7, 8, 8, 10] and your target is 8.

The first 8 is at index 3.
The last 8 is at index 4.
So, the output should be [3, 4].

What if target is 6? It's not in the list, so we return [-1, -1].

Crucial Constraint: Your solution must run in O(log n) time complexity. This is a huge hint! What algorithm is famous for O(log n) on sorted data? You guessed it: Binary Search!

Intuition: Beyond the Basic Binary Search

Okay, so we know we need binary search. A standard binary search can tell us if an element exists and, if so, one of its positions. But how do we find the first and last occurrences specifically?

The "aha!" moment is realizing that we can modify binary search slightly to pinpoint these specific positions.

Finding the First Occurrence: If we find an instance of target, we store its index as a potential "first occurrence." Then, we need to keep searching in the left half of the array to see if an even earlier target exists. We keep doing this until we can't find anything earlier.
Finding the Last Occurrence: Similarly, if we find an instance of target, we store its index as a potential "last occurrence." Then, we need to keep searching in the right half of the array to see if an even later target exists. We keep doing this until we can't find anything later.

By performing these two slightly modified binary searches, one for the first boundary and one for the last, we can solve the problem efficiently!

Approach: Two Binary Searches, One Goal

Our strategy will involve three main steps:

Implement firstOcc(nums, target): This function will use a modified binary search to find the index of the first occurrence of target.
- Initialize start = 0, end = nums.size() - 1, and ans = -1.
- While start <= end:
  - Calculate mid.
  - If nums[mid] == target:
    - We found a potential first occurrence. Store mid in ans.
    - To find an even earlier occurrence, we need to search in the left half: end = mid - 1.
  - If nums[mid] < target: The target must be in the right half, so start = mid + 1.
  - If nums[mid] > target: The target must be in the left half, so end = mid - 1.
- Return ans.
Implement lastOcc(nums, target): This function will use another modified binary search to find the index of the last occurrence of target.
- Initialize start = 0, end = nums.size() - 1, and ans = -1.
- While start <= end:
  - Calculate mid.
  - If nums[mid] == target:
    - We found a potential last occurrence. Store mid in ans.
    - To find an even later occurrence, we need to search in the right half: start = mid + 1.
  - If nums[mid] < target: The target must be in the right half, so start = mid + 1.
  - If nums[mid] > target: The target must be in the left half, so end = mid - 1.
- Return ans.
Combine in searchRange: Call firstOcc and lastOcc with the input nums and target, then return their results as a pair [first, last].

Code: Bringing It All Together

Here's the C++ implementation of our strategy:

#include <vector> // Required for std::vector
#include <algorithm> // Required if using std::min, std::max, etc. (not strictly needed here)

class Solution {
private:
    // Helper function to find the first occurrence of target
    int firstOcc(const std::vector<int>& arr, int key) {
        int n = arr.size();
        int s = 0, e = n - 1;
        int ans = -1; // Default to -1 if not found

        while (s <= e) {
            int mid = s + (e - s) / 2; // Avoids potential overflow compared to (s+e)/2

            if (arr[mid] == key) {
                ans = mid;         // Found a potential first occurrence
                e = mid - 1;       // Try to find an even earlier one in the left half
            } else if (arr[mid] < key) {
                s = mid + 1;       // Target is in the right half
            } else { // arr[mid] > key
                e = mid - 1;       // Target is in the left half
            }
        }
        return ans;
    }

    // Helper function to find the last occurrence of target
    int lastOcc(const std::vector<int>& arr, int key) {
        int n = arr.size();
        int s = 0, e = n - 1;
        int ans = -1; // Default to -1 if not found

        while (s <= e) {
            int mid = s + (e - s) / 2; // Avoids potential overflow

            if (arr[mid] == key) {
                ans = mid;         // Found a potential last occurrence
                s = mid + 1;       // Try to find an even later one in the right half
            } else if (arr[mid] < key) {
                s = mid + 1;       // Target is in the right half
            } else { // arr[mid] > key
                e = mid - 1;       // Target is in the left half
            }
        }
        return ans;
    }

public:
    std::vector<int> searchRange(std::vector<int>& nums, int target) {
        // Handle empty array case
        if (nums.empty()) {
            return {-1, -1};
        }

        int first = firstOcc(nums, target);
        int last = lastOcc(nums, target);

        return {first, last};
    }
};

Time & Space Complexity Analysis

Time Complexity: O(log n)
- We are performing two separate binary searches. Each binary search divides the search space in half with every step, leading to O(log n) complexity.
- Since we do this twice, the total time complexity remains 2 * O(log n), which simplifies to O(log n). This satisfies the problem's strict requirement!
Space Complexity: O(1)
- We are only using a few constant-sized variables (s, e, mid, ans, n, first, last). We are not using any additional data structures whose size grows with the input array nums. Therefore, the space complexity is constant.

Key Takeaways

Binary Search isn't just for true/false! You can modify its core logic to find specific occurrences (first, last, just greater than, just smaller than, etc.) within a sorted array.
O(log n) is your friend for sorted data: When you see "sorted array" and "O(log n)" together, immediately think Binary Search!
Divide and Conquer: Breaking down a complex problem (finding a range) into simpler, reusable sub-problems (finding first occurrence, finding last occurrence) is a powerful technique.
Edge Cases: Always consider empty arrays or targets not present in the array. Our ans = -1 initialization handles the "not found" scenario gracefully.

That's it for LeetCode 34! Hopefully, you now feel more confident in wielding the power of modified binary search. Keep practicing, and happy coding!

Author Account: Vansh2710
Time Published: 2026-03-24 18:28:49

DEV Community