Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/34.html

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

Level

Medium

Description

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

Your algorithm’s runtime complexity must be in the order of O(log n).

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

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]

Solution

Since the runtime complexity is restricted to be in the order of O(log n), and the array is sorted, binary search is an ideal solution.

Do binary search two rounds. The first round finds whether the given target is in the array nums, and if target exists, get the index of target (if there are duplicates, find any index that has the number target).

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

If the target value is present in the array, perform a second round of binary search. This time, search both sides of the index identified in the first round to locate the leftmost and rightmost indices of the target. For the second round, the binary search loop condition is that the left pointer must be less than the right pointer, and the equal case is not included in the loop condition. This condition is slightly different from traditional binary search.

Code

  • 
    public class Find_First_and_Last_Position_of_Element_in_Sorted_Array {
    
        class Solution {
    
            public int[] searchRange(int[] nums, int target) {
                int[] targetRange = {-1, -1};
    
                int leftIdx = extremeInsertionIndex(nums, target, true);
    
                // assert that `leftIdx` is within the array bounds and that `target`
                // is actually in `nums`.
                if (leftIdx == nums.length || nums[leftIdx] != target) {
                    return targetRange;
                }
    
                targetRange[0] = leftIdx;
                targetRange[1] = extremeInsertionIndex(nums, target, false) - 1; // @note: -1 to get right most index
    
                return targetRange;
            }
    
            // returns leftmost (or rightmost) index at which `target` should be
            // inserted in sorted array `nums` via binary search.
            private int extremeInsertionIndex(int[] nums, int target, boolean isLeft) {
                int lo = 0;
                int hi = nums.length;
    
                while (lo < hi) {
                    int mid = (lo + hi) / 2;
                    if (nums[mid] > target || (isLeft && target == nums[mid])) {
                        hi = mid;
                    }
                    else {
                        lo = mid+1;
                    }
                }
    
                return lo;
            }
        }
    }
    
    ############
    
    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;
        }
    }
    
  • // OJ: https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
    // Time: O(logN)
    // Space: O(1)
    class Solution {
    public:
        vector<int> searchRange(vector<int>& A, int target) {
            if (A.empty()) return {-1,-1};
            int N = A.size(), L = 0, R = N - 1;
            while (L <= R) {
                int M = (L + R) / 2;
                if (A[M] < target) L = M + 1;
                else R = M - 1;
            }
            if (L >= N || A[L] != target) return {-1,-1};
            int left = L;
            L = 0, R = N - 1;
            while (L <= R) {
                int M = (L + R) / 2;
                if (A[M] > target) R = M - 1;
                else L = M + 1;
            }
            return {left, R};
        }
    };
    
  • '''
    >>> bisect.bisect_left([1,1,1,2,2,2,7,7,7], 2)
    3
    >>> bisect.bisect_left([1,1,1,2,2,2,7,7,7], 2+1)
    6
    
    
    >>> bisect.bisect_right([1,1,1,2,2,2,7,7,7], 2)
    6
    >>> bisect.bisect_right([1,1,1,2,2,2,7,7,7], 2+1)
    6
    '''
    class Solution:
        def searchRange(self, nums: List[int], target: int) -> List[int]:
            l = bisect_left(nums, target)
            r = bisect_left(nums, target + 1)
            return [-1, -1] if l == r else [l, r - 1]
    
    ############
    
    class Solution:
        def searchRange(self, nums: List[int], target: int) -> List[int]:
            def findRange(left):
                l, r = 0, len(nums) - 1
                m = 0
                while l <= r:
                    m = l + (r - l) // 2
                    if nums[m] < target:
                        l = m + 1
                    elif nums[m] > target:
                        r = m - 1
                    elif left and m > 0 and nums[m - 1] == nums[m]: # so now nums[m] == target, but maybe not the leftmost or rightmost
                        r = m - 1
                    elif not left and m + 1 < len(nums) and nums[m + 1] == nums[m]:  # so now nums[m] == target, but maybe not the leftmost or rightmost
                        l = m + 1
                    else:
                        return m
                if m < len(nums) and nums[m] == target: # 1. cover not-found, or 2. cover input=[3] and target=3, first and last both 0, return [0,0]
                    return m
                else:
                    return -1
            return [findRange(True), findRange(False)]
    
    
  • func searchRange(nums []int, target int) []int {
    	l := sort.Search(len(nums), func(i int) bool { return nums[i] >= target })
    	r := sort.Search(len(nums), func(i int) bool { return nums[i] > target })
    	if l == r {
    		return []int{-1, -1}
    	}
    	return []int{l, r - 1}
    }
    
  • function searchRange(nums: number[], target: number): number[] {
        function search(x) {
            let left = 0,
                right = nums.length;
            while (left < right) {
                const mid = (left + right) >> 1;
                if (nums[mid] >= x) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            return left;
        }
        const l = search(target);
        const r = search(target + 1);
        return l == r ? [-1, -1] : [l, r - 1];
    }
    
    
  • /**
     * @param {number[]} nums
     * @param {number} target
     * @return {number[]}
     */
    var searchRange = function (nums, target) {
        function search(x) {
            let left = 0,
                right = nums.length;
            while (left < right) {
                const mid = (left + right) >> 1;
                if (nums[mid] >= x) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            return left;
        }
        const l = search(target);
        const r = search(target + 1);
        return l == r ? [-1, -1] : [l, r - 1];
    };
    
    
  • impl Solution {
        pub fn search_range(nums: Vec<i32>, target: i32) -> Vec<i32> {
            let n = nums.len();
            let search = |x| {
                let mut left = 0;
                let mut right = n;
                while left < right {
                    let mid = left + (right - left) / 2;
                    if nums[mid] < x {
                        left = mid + 1;
                    } else {
                        right = mid;
                    }
                }
                left
            };
            let l = search(target);
            let r = search(target + 1);
            if l == r {
                return vec![-1, -1];
            }
            vec![l as i32, (r - 1) as i32]
        }
    }
    
    

All Problems

All Solutions