Is Find First and Last Position of Element in Sorted Array easy or hard?

The problem is rated Medium difficulty. The logic of binary search is straightforward, but modifying it to detect boundaries instead of stopping at the first match requires careful pointer updates and edge case handling.

Find First and Last Position of Element in Sorted Array Python/Java solution

Python and Java solutions typically implement two helper binary searches: one to find the first occurrence and one for the last occurrence. Both versions maintain left and right pointers and adjust the search boundaries when the target is found. The final result returns the two indices or [-1, -1] if the target is absent.

What is the best approach for Find First and Last Position of Element in Sorted Array?

The best approach is a modified binary search that finds the leftmost and rightmost occurrence separately. Run binary search twice: once to locate the first index where the target appears and once to locate the last index. Each search takes O(log n) time, so the total complexity remains O(log n) with O(1) extra space.

Is Find First and Last Position of Element in Sorted Array asked at Google/Amazon/Meta?

This problem appears frequently in interviews at large tech companies including Google, Amazon, Meta, and Microsoft. It tests your understanding of binary search variations and boundary detection in sorted arrays, which are common patterns in technical interviews.

What data structure is used in Find First and Last Position of Element in Sorted Array?

The primary data structure is a sorted array. The algorithm relies on binary search to efficiently narrow the search range. No additional data structures are required beyond index variables used during the search process.

What is the time complexity of Find First and Last Position of Element in Sorted Array?

The optimal solution runs in O(log n) time using binary search. Two searches are performed—one for the first occurrence and one for the last occurrence—but each halves the search space. Space complexity remains O(1) since the algorithm only uses a few pointers.

Description Solution Video 9:32

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

Q: How to solve Find First and Last Position of Element in Sorted Array in O(log n)?

Use binary search to find boundary positions instead of stopping at the first match. When searching for the first index, continue exploring the left half after finding the target. When searching for the last index, continue exploring the right half. This modification ensures both boundaries are found in logarithmic time.

Medium49.7% acceptance29 companies

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

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

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Example 3:

Input: nums = [], target = 0
Output: [-1,-1]

Constraints:

0 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹
nums is a non-decreasing array.
-10⁹ <= target <= 10⁹

Asked at top 20 of 29 companies

Tinkoff Instacart Splunk Airtel Meta LinkedIn Tekion Applied Intuition Amazon Bloomberg Tiktok Apple

+8 more

TCS

Infosys Citadel Capgemini Attentive

Google Microsoft Oracle

Topics

Array Binary Search

9:32

Still stuck?Read 2 approaches, or watch a walkthrough.

Open solution

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

Asked at top 20 of 29 companies

Topics

Similar problems