Find First and Last Position of Element in Sorted Array

MEDIUM

Description

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⁹

Approaches

Checkout 2 different approaches to solve Find First and Last Position of Element in Sorted Array. Click on different approaches to view the approach and algorithm in detail.

Linear Scan

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.

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 Analysis

Time Complexity: O(n)Space Complexity: O(1)

Pros and Cons

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.

Code Solutions

Checking out 5 solutions in different languages for Find First and Last Position of Element in Sorted Array. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Find First and Last Position of Element in Sorted Array

Algorithms:

Binary Search

Data Structures:

Array

Companies:

Accenture |Adobe |Amazon |Apple |