Find First and Last Position of Element in Sorted Array (Leetcode 34)

Difficulty: Medium Link: April Leetcode Challenge : Day 29

Problem Description

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

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

Follow up: Could you write an algorithm with O(log n) runtime complexity?

Examples

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
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

Solution

A naive straightforward solution can be to iterate over the array and keep track of the first and last positions using two variables. This would be a linear operation and very easy to implement however, this is not an optimal solution. Whenever we are given a sorted array we should be thinking about logarithmic complexity. The property we should be leveraging is the for any element in the sorted array, the elements greater than it would be towards the right side and lesser elements would be towards the left side. Which algorithm enables us to do that?

Binary Search

Sorted Arrays and binary search always go hand in hand. We can modify the vanilla binary search to find the first /last positions by first finding index for target and then finding the index for number slightly bigger than the target.

First, we can perform the standard left binary search (find) on T. Next, we can easily check to see if T exists in N already by checking the value stored at the result of that first search (N[Tleft]). If we don’t find T at that index, then T does not exist in N and we should return [-1, -1].

Otherwise, we still need to find the right end of the range of T values in N. To do this, we can just use find again, this time with the next integer (T + 1). Since this will find the index after the end of the range of T values, we can just move back one position to find the end of the T range.

Alternative approach could be to make two functions, one for finding the lower bound and other for finding the upper bound. Since both would be using the binary search, asymptotic bounds would be within LogN. This approach is simple but a bit redundant and while we can instead do it in a single function by passing an identifier like a flag to indicate if we want to left extreme or the right extreme.

Code

Swift

class Solution {
func searchRange(_ nums: [Int], _ target: Int) -> [Int] {
let leftPos = find(nums, target, 0)
// Left position exceeds bounds or not found
if leftPos == nums.count || nums[leftPos] != target {
return [-1, -1]
}
// If left Position found, then atleast 1 occurence of the element is presence
// Then we can find the right position by finding for target + 1
let rightPos = find(nums,target + 1,leftPos) 1
return [leftPos, rightPos]
}
func find(_ nums:[Int], _ target:Int,_ left:Int) -> Int {
var left = left, right = nums.count 1
while left <= right {
let mid = left + (right left) / 2
if nums[mid] < target {
left = mid + 1
}
else{
right = mid 1
}
}
return left
}
}

Python

Python has built-in binary search functions for both sides: bisect_left() and bisect_right(). The bisect_left() will return index before all repetitions of target and the second one: after. So, if these two indexes are equal, it means that we did not found this element, so we return [-1, -1]. If we found, we return [l, r - 1].

from bisect import bisect, bisect_left
class Solution:
def searchRange(self, nums, target):
l = bisect_left(nums,target)
r = bisect(nums,target)
return [1, 1] if l == r else [l, r 1]

Java

class Solution {
public int[] searchRange(int[] N, int T) {
int Tleft = find(T, N, 0);
if (Tleft == N.length || N[Tleft] != T) return new int[] {1, 1};
return new int[] {Tleft, find(T+1, N, Tleft) 1};
}
public int find(int target, int[] arr, int left) {
int right = arr.length 1;
while (left <= right) {
int mid = left + right >> 1;
if (arr[mid] < target) left = mid + 1;
else right = mid 1;
}
return left;
}
}

Complexity Analysis

  • Time Complexity: O(log N) for the binary search
  • Space Complexity: O(1)

Leave a Reply

Your email address will not be published. Required fields are marked *