Scale Engineer

Find First and Last Position of Element in Sorted Array

Med
#0034Time: O(n)Space: O(1)30 companies
Algorithms
Binary Search
Data structures
Array
Companies
AccentureAdobeAmazonApple

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

The most straightforward approach is to iterate through the entire array. We can use two variables, one to store the index of the first occurrence and another for the last. We traverse the array, and whenever we find the target element, we update these variables.

Algorithm

  • Initialize a result array ans to [-1, -1].
  • Iterate through the nums array from left to right with index i.
  • If nums[i] equals the target:
    • If ans[0] is still -1, it means this is the first time we've seen the target. Set ans[0] = i.
    • Always update the last seen position: ans[1] = i.
  • After the loop finishes, return the ans array.

Walkthrough

This method involves a single pass through the array from left to right. We keep track of the first and last indices where the target element is found. The first time we encounter the target, we record its index in a variable, say first. For every occurrence of the target, we update another variable, last. If the loop completes and we never found the target, the initial values indicating 'not found' (e.g., -1) are returned.

class Solution {    public int[] searchRange(int[] nums, int target) {        int[] result = new int[]{-1, -1};        // Find the first occurrence        for (int i = 0; i < nums.length; i++) {            if (nums[i] == target) {                result[0] = i;                break;            }        }         // If the first occurrence was not found, the element doesn't exist.        if (result[0] == -1) {            return result;        }         // Find the last occurrence, searching backwards        for (int i = nums.length - 1; i >= 0; i--) {            if (nums[i] == target) {                result[1] = i;                break;            }        }         return result;    }}

Complexity

Time

O(n)

Space

O(1)

Trade-offs

Pros

  • Very simple to understand and implement.

Cons

  • Inefficient for large arrays.

  • Time complexity of O(n) does not meet the problem's requirement of O(log n).

  • It doesn't leverage the fact that the input array is sorted.

Solutions

public class Solution {    public int[] SearchRange(int[] nums, int target) {        int l = Search(nums, target);        int r = Search(nums, target + 1);        return l == r ? new int[] {            -1, -1        } : new int[] {            l,            r - 1        };    }    private int Search(int[] nums, int x) {        int left = 0, right = nums.Length;        while (left < right) {            int mid = (left + right) >>> 1;            if (nums[mid] >= x) {                right = mid;            } else {                left = mid + 1;            }        }        return left;    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem