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

June 10, 2024

Table of Contents

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.

Examples:

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]

Solution in Python:

To solve this problem efficiently with a runtime complexity of O(log n), we can use a binary search approach. We will implement two separate binary searches: one to find the leftmost (first) occurrence of the target and one to find the rightmost (last) occurrence of the target.

Python

from typing import List

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def findLeft(nums, target):
            left, right = 0, len(nums) - 1
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1
            return left
        
        def findRight(nums, target):
            left, right = 0, len(nums) - 1
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] <= target:
                    left = mid + 1
                else:
                    right = mid - 1
            return right
        
        left_index = findLeft(nums, target)
        right_index = findRight(nums, target)
        
        # Check if the target is not in the array
        if left_index <= right_index and right_index < len(nums) and nums[left_index] == target and nums[right_index] == target:
            return [left_index, right_index]
        else:
            return [-1, -1]

Detailed Explanation:

Binary Search for Leftmost Index (findLeft):
- Initialize left to 0 and right to the last index of nums.
- Use a while loop that runs as long as left is less than or equal to right.
- Calculate mid as the midpoint of left and right.
- If the element at mid is less than the target, move the left pointer to mid + 1.
- Otherwise, move the right pointer to mid - 1.
- This search will stop at the smallest index where nums[index] is greater than or equal to the target.
Binary Search for Rightmost Index (findRight):
- Initialize left to 0 and right to the last index of nums.
- Use a while loop that runs as long as left is less than or equal to right.
- Calculate mid as the midpoint of left and right.
- If the element at mid is less than or equal to the target, move the left pointer to mid + 1.
- Otherwise, move the right pointer to mid - 1.
- This search will stop at the largest index where nums[index] is less than or equal to the target.
Final Check:
- After finding the potential leftmost and rightmost indices, we need to check if the target exists within the range.
- If the left_index is less than or equal to the right_index, and both indices are within the bounds of the array, and the elements at these indices are equal to the target, return these indices.
- If not, return [-1, -1] indicating the target is not present in the array.

This approach ensures the solution runs in O(log n) time complexity due to the binary search used for both the leftmost and rightmost indices.

Solution in Javascript:

JavaScript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function(nums, target) {
    // Helper function to find the leftmost index of the target
    function findLeft(nums, target) {
        let left = 0, right = nums.length - 1;
        while (left <= right) {
            let mid = Math.floor((left + right) / 2);
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

    // Helper function to find the rightmost index of the target
    function findRight(nums, target) {
        let left = 0, right = nums.length - 1;
        while (left <= right) {
            let mid = Math.floor((left + right) / 2);
            if (nums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return right;
    }

    // Find the leftmost index of the target
    let leftIndex = findLeft(nums, target);
    // Find the rightmost index of the target
    let rightIndex = findRight(nums, target);

    // Check if the target is not in the array
    if (leftIndex <= rightIndex && rightIndex < nums.length && nums[leftIndex] === target && nums[rightIndex] === target) {
        return [leftIndex, rightIndex];
    } else {
        return [-1, -1];
    }
};

Solution in Java:

Java

import java.util.Arrays;

class Solution {
    public int[] searchRange(int[] nums, int target) {
        // Find the leftmost index of the target
        int leftIndex = findLeft(nums, target);
        // Find the rightmost index of the target
        int rightIndex = findRight(nums, target);

        // Check if the target is not in the array
        if (leftIndex <= rightIndex && rightIndex < nums.length && nums[leftIndex] == target && nums[rightIndex] == target) {
            return new int[]{leftIndex, rightIndex};
        } else {
            return new int[]{-1, -1};
        }
    }

    // Helper function to find the leftmost index of the target
    private int findLeft(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

    // Helper function to find the rightmost index of the target
    private int findRight(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return right;
    }

    // Example usage:
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(Arrays.toString(solution.searchRange(new int[]{5, 7, 7, 8, 8, 10}, 8))); // Output: [3, 4]
        System.out.println(Arrays.toString(solution.searchRange(new int[]{5, 7, 7, 8, 8, 10}, 6))); // Output: [-1, -1]
        System.out.println(Arrays.toString(solution.searchRange(new int[]{}, 0))); // Output: [-1, -1]
    }
}

Solution in C#:

C#

using System;

public class Solution {
    public int[] SearchRange(int[] nums, int target) {
        // Find the leftmost index of the target
        int leftIndex = FindLeft(nums, target);
        // Find the rightmost index of the target
        int rightIndex = FindRight(nums, target);

        // Check if the target is not in the array
        if (leftIndex <= rightIndex && rightIndex < nums.Length && nums[leftIndex] == target && nums[rightIndex] == target) {
            return new int[] { leftIndex, rightIndex };
        } else {
            return new int[] { -1, -1 };
        }
    }

    // Helper function to find the leftmost index of the target
    private int FindLeft(int[] nums, int target) {
        int left = 0, right = nums.Length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

    // Helper function to find the rightmost index of the target
    private int FindRight(int[] nums, int target) {
        int left = 0, right = nums.Length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return right;
    }

    
}

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

Description:

Solution in Python:

Solution in Javascript:

Solution in Java:

Solution in C#:

Popular

206. Reverse Linked List – Leetcode Solutions

133. Clone Graph – Leetcode Solutions

185. Department Top Three Salaries – Leetcode Solutions

4. Median of Two Sorted Arrays – Leetcode Solutions

211. Design Add and Search Words Data Structure – Leetcode Solutions

227. Basic Calculator II – Leetcode Solutions

The cmath Module in Python

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

Description:

Solution in Python:

Solution in Javascript:

Solution in Java:

Solution in C#:

Related Post

Popular