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

Explanation

In this problem, an algorithm that can find the first and last position of an occurrence of a specific target value in a given sorted array needs to be implemented.

The algorithm is required to have a time complexity of O(log n), which indicates that a binary search strategy is a good approach for this problem.

A binary search divides a sorted collection into two halves and determines which half the desired value is in, discarding the other half. It continues this subdivision and selection until it either finds the desired value or no longer has a subset to search within, at which point it returns that the value is not in the collection. In each step of the process, it effectively halves the number of elements it needs to search, which leads to the O(log n) time complexity.

Consider the example:

1
2
3input: nums = [5,7,7,8,8,10], target = 8
4output: [3,4]

The target value 8 appears at indices 3 and 4. That's why the result is [3, 4].

If the target value is not present in the array, the method will return [-1,-1].

Python

1
2python
3from typing import List
4
5class Solution:
6  def searchRange(self, nums: List[int], target: int) -> List[int]:
7    l = 0
8    r = len(nums) - 1
9
10    while l <= r:
11      mid = l + (r - l) // 2
12      if nums[mid] < target:
13        l = mid + 1
14      else:
15        r = mid - 1
16
17    if l >= len(nums) or nums[l] != target:
18      first = -1
19    else:
20      first = l
21
22    l = 0
23    r = len(nums) - 1
24    while l <= r:
25      mid = l + (r - l) // 2
26      if nums[mid] <= target:
27        l = mid + 1
28      else:
29        r = mid - 1
30
31    if r >= len(nums) or nums[r] != target:
32      last = -1
33    else:
34      last = r
35  
36    return [first, last]

Java

1
2java
3class Solution {
4    public int[] searchRange(int[] nums, int target) {
5        int low = 0, high = nums.length - 1;
6        while (low < high) {
7            int mid = low + (high - low) / 2;
8            if (nums[mid] < target) {
9                low = mid + 1;
10            } else {
11                high = mid;
12            }
13        }
14        
15        if (nums[low] != target) {
16            return new int[] {-1, -1};
17        }
18        
19        int first = low;
20        high = nums.length - 1;
21        
22        while (low < high) {
23            int mid = low + (high - low) / 2 + 1;
24            if (nums[mid] > target) {
25                high = mid - 1;
26            } else {
27                low = mid;
28            }
29        }
30        
31        return new int[] {first, low};
32    }
33}

JavaScript

1
2javascript
3var searchRange = function(nums, target) {
4    let leftIndex = getFirstIndex(nums, target);
5    let rightIndex = getLastIndex(nums, target);
6  
7    return [leftIndex, rightIndex];
8};
9  
10var getFirstIndex = function(nums, target) {
11    let index = -1;
12    let start = 0;
13    let end = nums.length - 1;
14
15    while (start <= end) {
16        let mid = Math.floor((start + end) / 2);
17  
18        if (nums[mid] >= target) {
19            end = mid - 1;
20        } else {
21            start = mid + 1;
22        }
23
24        if (nums[mid] === target) index = mid;
25    }
26    
27    return index;
28};
29  
30var getLastIndex = function(nums, target) {
31    let index = -1;
32    let start = 0;
33    let end = nums.length - 1;
34
35    while (start <= end) {
36        let mid = Math.floor((start + end) / 2);
37  
38        if (nums[mid] <= target) {
39            start = mid + 1;
40        } else {
41            end = mid - 1;
42        }
43
44        if (nums[mid] === target) index = mid;
45    }
46    
47    return index;
48};

C++

1
2cpp
3class Solution {
4public:
5    vector<int> searchRange(vector<int>& nums, int target) {
6        vector<int> result(2, -1);
7        int left = 0;
8        int right = nums.size() - 1;
9        while (left <= right) {
10            int mid = left + (right - left) / 2;
11            if (nums[mid] < target)
12                left = mid + 1;
13            else
14                right = mid - 1;
15        }
16        
17        if (left >= nums.size() || nums[left] != target)
18            return result;
19        result[0] = left;
20
21        right = nums.size() - 1;
22        while (left <= right) {
23            int mid = left + (right - left) / 2;
24            if (nums[mid] <= target)
25                left = mid + 1;
26            else
27                right = mid - 1;
28        }
29        result[1] = right;
30        return result;
31    }
32};

C#

1
2csharp
3public class Solution {
4    public int[] SearchRange(int[] nums, int target) {
5        int[] result = new int[] {-1, -1};
6        int left = 0;
7        int right = nums.Length - 1;
8        
9        while (left < right) {
10            int mid = left + (right - left) / 2;
11            if (nums[mid] < target)
12                left = mid + 1;
13            else
14                right = mid;
15        }
16        
17        if (nums[left] != target) 
18            return result;
19        
20        result[0] = left;
21        right = nums.Length - 1;
22        
23        while (left < right) {
24            int mid = (left + (right - left) / 2) + 1;
25            if (nums[mid] > target)
26                right = mid - 1;
27            else
28                left = mid;
29        }
30        
31        result[1] = right;
32        return result;
33    }
34}

All of the above solutions return the correct results and maintain their time complexity within O(log n) by using a modified binary search algorithm twice to find the first and last occurrence of the target value.Each solution works with the same principle in mind, but they might differ slightly due to language specifics. First, a binary search is performed to find the first occurrence of the target. If the target is found, then its position is saved, and another binary search is performed to find the last occurrence.

Python solution first initializes two pointers at the start and end of the array (list). Then it conducts a binary search until it finds an element equal to or larger than the target. Once found, it checks if the element is the target or not, and saves the position as the first occurrence of the target. The process is then repeated to find the last occurrence, but this time, the binary search is adjusted to find an element equal to or smaller than the target.

The Java and C# solutions also follow the same procedure to find the first occurrence. After storing the first occurrence, they also slightly adjust the binary search to find the last occurrence. The only difference from Python is that they perform the check for the target's absence earlier, right after the first binary search.

In JavaScript, two separate helper functions are created to find the first and last occurrence, providing a more modular approach. In each helper function, a binary search is performed, which updates the current index if the target is found.

The C++ approach is similar to the Python solution with a slight difference in the handling of the 'not found' case. Instead of checking the absence separately after each binary search, it checks after the first binary search and immediately returns the result if the target is not found.

These solutions are very efficient because they minimize the number of elements to be inspected using the binary search technique, which effectively halves the number of elements to be searched at each step, hence, achieving the required time complexity of O(log n).