Find First and Last Position of Element in Sorted Array

Find First and Last Position of Element in Sorted Array

What is this problem about?

The Find First and Last Position of Element in Sorted Array interview question asks you to locate the start and end indices of a target value within a sorted list of integers. Because the array is sorted, duplicate values will always appear contiguously. If the target is not found, you should return [-1, -1]. The key constraint is that the solution must run in logarithmic time—$O(\log n)$.

Why is this asked in interviews?

This Find First and Last Position of Element in Sorted Array coding problem is a staple at top-tier companies like Google, Apple, and Microsoft. It evaluates whether a candidate can adapt the standard Binary Search interview pattern to handle duplicate elements. It tests your ability to think critically about boundary conditions—specifically, how to modify the search to look for the "leftmost" or "rightmost" instance of a value rather than just any match.

Algorithmic pattern used

The problem uses Binary Search. Instead of one search, you perform two variations:

1. Lower Bound Search: When you find the target, instead of stopping, you continue searching the left half to see if an even earlier instance exists.
2. Upper Bound Search: When you find the target, you continue searching the right half to find the last possible instance. This ensures you find the exact range of the target values in $O(\log n)$ time.

Example explanation

Array: [5, 7, 7, 8, 8, 10], Target: 8.

1. First Position:
   • Binary search finds 8 at index 4.
   • Continue searching the left [5, 7, 7, 8].
   • Finds 8 at index 3.
   • No more 8s to the left. First position = 3.
2. Last Position:
   • Binary search finds 8 at index 3.
   • Continue searching the right [8, 10].
   • Finds 8 at index 4.
   • No more 8s to the right. Last position = 4. Result: [3, 4].

Common mistakes candidates make

• Linear Scanning: Finding one instance of the target and then scanning left and right. This results in $O(n)$ worst-case complexity (e.g., if all elements are the target), which violates the $O(\log n)$ requirement.
• Off-by-one errors: Mismanaging the low and high pointers, especially when deciding whether to include the mid index in the next search range.
• Inefficient redundancy: Writing two completely separate, nearly identical search functions instead of using a single parameterized helper function.

Interview preparation tip

Master the "Binary Search Template." Learn how to consistently handle the while(low <= high) vs while(low < high) conditions. Being able to explain why you choose one over the other for boundary-finding problems is a sign of a strong coder.