LeetCode #34: Find First and Last Position of Element in Sorted Array — Solved in Java

Linear Scan and Binary Search For Left And Right Boundaries

Image Source

This LeetCode problem asks for the first and last positions of a value inside a sorted array, and the answer needs to return both indices in a simple two-element result. A missing value returns a pair of negative ones, and every array is already ordered from smallest to largest, which keeps the search focused on tracing where a matching stretch begins and where it ends.

Solving this in Java works best when you think about how the search should happen before touching any code. A direct walk across the array tells you where the value first appears and where it stops, while a tighter plan reads the sorted layout and jumps through the data in controlled steps. The two styles reach the right answer, but they follow different thought methods, and that contrast helps you decide which technique fits what you want to present.

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

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^5

• -10^9 <= nums[i] <= 10^9

• nums is a non-decreasing array.

• -10^9 <= target <= 10^9

Solution 1: Linear Scan Over The Sorted Array

Linear scanning works nicely when you want to walk through the array without leaning on any deeper structure. This method treats the data at face value and focuses on finding the first hit and the last hit by moving from opposite ends.