Problem Link

LeetCode 34 – Find First and Last Position of Element in Sorted Array

👉 https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

📌 Problem Overview

You are given a sorted array (non-decreasing order) and a target value.

Your task:

1. Return the starting and ending index of the target.
2. If target does not exist → return [-1, -1]
3. Required Time Complexity: O(log n)

Example 1

Example 2

🧠 My First Intuition – Brute Force (O(n))

When I first saw this problem, my thinking was simple:

"Since the array is sorted, I just need to find the first occurrence and the last occurrence."

So I used two loops:

1. One loop from left → to find first occurrence
2. One loop from right → to find last occurrence

Here is my submitted solution:

✅ Why This Works

1. Since the array is sorted, occurrences of the same number are grouped together.
2. First loop (reverse) finds last occurrence.
3. Second loop (forward) finds first occurrence.

❌ Problem with This Approach

Time Complexity = O(n)

Worst case:

1. Target is not present
2. We scan entire array twice

But the problem clearly states:

You must write an algorithm with O(log n) runtime complexity.

That means: We must use Binary Search.

🚀 Optimized Approach – Binary Search (O(log n))

💡 Key Intuition

If the array is sorted:

1. We can use Binary Search to find the first occurrence
2. We can use Binary Search again to find the last occurrence

Instead of stopping when we find the target:

1. For first occurrence → continue searching left
2. For last occurrence → continue searching right

🧠 Idea Breakdown

1️⃣ Find First Occurrence

When we find target at mid:

1. Store index
2. Move left → high = mid - 1
3. Because there might be another occurrence before it

2️⃣ Find Last Occurrence

When we find target at mid:

1. Store index
2. Move right → low = mid + 1
3. Because there might be another occurrence after it

💻 Optimized Code (Binary Search Approach)

🔍 Why This Works

Binary Search normally stops when target is found.

Here, we modify it slightly:

1. Keep searching even after finding target.
2. Narrow the search space toward the boundary we want.

This guarantees:

1. First occurrence → leftmost index
2. Last occurrence → rightmost index

⏱ Complexity Analysis

Brute Force Approach

1. Time: O(n)
2. Space: O(1)

Binary Search Approach

1. Time: O(log n)
2. Space: O(1)

This satisfies the problem constraint.

🎯 Key Learning from This Problem

This problem teaches an important pattern:

When array is sorted and you need boundaries → Think Binary Search.

It is not just about finding the element.

It is about finding:

1. First occurrence (Lower Bound)
2. Last occurrence (Upper Bound)

This pattern appears in many interview problems.

📚 Similar Problems to Practice

1. https://leetcode.com/problems/binary-search/
2. https://leetcode.com/problems/search-insert-position/
3. https://leetcode.com/problems/search-in-rotated-sorted-array/
4. https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/
5. https://leetcode.com/problems/sqrtx/

🏁 Final Thoughts

My journey solving this problem:

1. First thought → Use two loops (works but O(n))
2. Then realized constraint → Must be O(log n)
3. Optimized using two Binary Searches

This is how problem solving improves:

1. Start with correct solution.
2. Then optimize.
3. Then recognize patterns.

LeetCode 34 is one of the most important Binary Search boundary problems.

If you master this, you unlock an entire category of advanced Binary Search questions.