Find First and Last Position of Element in Sorted Array

Find First and Last Position of Element in Sorted Array is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Binary Search Patterns pattern, in the Find First/Last Occurrence subpattern.

Problem statement

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 <= 105

- -109 <= nums[i] <= 109

- nums is a non-decreasing array.

- -109 <= target <= 109

Topics and companies

Topics: Array, Binary Search.

Reported in interviews at Facebook, Amazon, Uber, Google, Microsoft, LinkedIn, Bloomberg, Snapchat, Oracle.

How to practise Find First and Last Position of Element in Sorted Array on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(logn) time and O(1) space.

Open Find First and Last Position of Element in Sorted Array in the code editor, or read the Find First and Last Position of Element in Sorted Array editorial for a worked solution with its approach and complexity analysis.

Where Find First and Last Position of Element in Sorted Array sits in the DSA pattern sheet

• Binary Search Patterns pattern guide
• Find First/Last Occurrence subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Find First and Last Position of Element in Sorted Array

Other problems that use the same Find First/Last Occurrence and Binary Search Patterns techniques:

• Find K Closest Elements — Medium, same subpattern
• Binary Search — Easy, same pattern
• Capacity To Ship Packages Within D Days — Medium, same pattern
• Find in Mountain Array — Hard, same pattern
• Find K-th Smallest Pair Distance — Hard, same pattern
• Find Minimum in Rotated Sorted Array — Medium, same pattern