LeetCode #34 Find First and Last Position of Element in Sorted Array Solution & Explanation

Klook.com
Post Views: 320

LeetCode Problem

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.

Solution

First, when we encounter a problem and identify several keywords like ‘non-decreasing order array,’ ‘O(log n),’ and ‘position,’ we should immediately think of binary search.

We can solve this problem using a binary search, with code similar to LeetCode #35 Search Insert Position Solution & Explanation. We just need a little adjustment.

We need to use two while loops: the first one to find the starting position, and the second one to determine the ending position.

C# Solution

public class Solution {
    public int[] SearchRange(int[] nums, int target) {
        int[]res = new int[2]{-1,-1};

        int left = 0;
        int right = nums.Length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                res[0] = mid;
                right = mid-1;
            } 
            else if (nums[mid] < target) {
                left = mid + 1;
            } 
            else {
                right = mid - 1;
            }
        }

        left = 0;
        right = nums.Length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                res[1] = mid;
                left = mid + 1;
            } 
            else if (nums[mid] < target) {
                left = mid + 1;
            } 
            else {
                right = mid - 1;
            }
        }
        
        return res;

    }
}

Time Complexity : O(log n)

  • res[0] = mid: It updates the starting position (res[0]) to the current index mid, indicating a potential occurrence of the target.
  • right = mid – 1: It adjusts the search space to the left, aiming to find the earliest occurrence of the target by updating the right pointer to mid – 1.

While finding the ending position, the code follows a similar logic, adjusting the search space to the right.

Java Solution

Solution1

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[]res = new int[]{-1,-1};

        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                res[0] = mid;
                right = mid - 1;
            } 
            else if (nums[mid] < target) {
                left = mid + 1;
            } 
            else {
                right = mid - 1;
            }
        }

        left = 0;
        right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                res[1] = mid;
                left = mid + 1;
            } 
            else if (nums[mid] < target) {
                left = mid + 1;
            } 
            else {
                right = mid - 1;
            }
        }
        return res;
    }
}

Runtime : 0ms, 0ms, 0ms

Time Complexity : O(log n)

Python3 Solution

Solution1

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        res = [-1,-1]
        left = 0
        right = len(nums) - 1

        while left <= right:
            mid = left + (right - left) // 2

            if nums[mid] == target:
                res[0] = mid
                right = mid - 1
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        left = 0
        right = len(nums) - 1

        while left <= right:
            mid = left + (right - left) // 2

            if nums[mid] == target:
                res[1] = mid
                left = mid + 1
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        return res

JavaScript Solution

Solution1

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function(nums, target) {
    let res = [-1,-1];
    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        let mid = Math.floor(left + (right - left) / 2);

        if (nums[mid] === target) {
            res[0] = mid;
            right = mid - 1;
        } 
        else if (nums[mid] < target) {
            left = mid + 1;
        } 
        else {
            right = mid - 1;
        }
    }

    left = 0;
    right = nums.length - 1;
    while (left <= right) {
        let mid = Math.floor(left + (right - left) / 2);

        if (nums[mid] === target) {
            res[1] = mid;
            left = mid + 1;
        } 
        else if (nums[mid] < target) {
            left = mid + 1;
        } 
        else {
            right = mid - 1;
        }
    }
    return res;
};

Conclusion

🧡If my solution helps, that is my honor!

🧡You can support me by sharing my posts or clicking ads, thanks you~~

✅If you got any problem about the explanation or you need other programming language solution, please feel free to let me know !!

The problem link : Find First and Last Position of Element in Sorted Array – LeetCode

See next problem : LeetCode #35 Search Insert Position Solution & Explanation (an easier version of this challenge!)

Some Random Posts

Tags

Related Posts

Leave a Reply

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