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

Find First and Last Position of Element in Sorted Array

Problem 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.

 

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]

 

Constraints:

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109
• nums is a non-decreasing array.
• -109 <= target <= 109

Approach) Brute Force

Predictably there is a brute force option available to use. It requires only a single pass over the data but is slower than the aforementioned binary search approach.

Code:

var searchRange = function (nums, target) {
    let targetFirstOccurence = -1;

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === target && targetFirstOccurence === -1) {
            targetFirstOccurence = i;
        } else if (nums[i] > target) {
            if (targetFirstOccurence !== -1) {
                return [targetFirstOccurence, i - 1];
            } else {
                return [-1, -1];
            }
        }
    }

    return targetFirstOccurence === -1 ? [-1, -1] : [targetFirstOccurence, nums.length - 1];
};

Approach) Brute Force With IndexOf

Once again making use of JavaScript’s powerful indexOf() method, we can quickly ascertain the first occurrence of the target number, and then use a simple for loop from that point to find the last occurrence. Once again this solution is a little bit of a cheat, and once again it is slower than the binary search approach.

Code:

var searchRange = function (nums, target) {
    let targetFirstOccurence = nums.indexOf(target);

    if (targetFirstOccurence === -1) return [-1, -1];

    for (let i = targetFirstOccurence; i < nums.length; i++) {
        if (nums[i] > target) {
            return [targetFirstOccurence, i - 1];
        }
    }

    return [targetFirstOccurence, nums.length - 1];
};

Approach) Binary Search

Oftentimes the trick to finding anything in an ordered array quickly is to use a binary search. But what makes this problem a little different is that we aren’t just looking for the first occurrence of the target, but also the last. What this means is that we need to use two binary searches; one biased to the left, and one biased to the right.

Code:

var searchRange = function (nums, target) {
    let left = 0;
    let right = nums.length - 1;
    let output = [-1, -1];

    // Binary search for the target (left-biased)
    while (left < right) {
        let middle = Math.floor((left + right) / 2);

        if (nums[middle] < target) {
            left = middle + 1;
        } else {
            right = middle;
        }
    }

    // If the target was not found on the first pass
    if (nums[left] != target) {
        return output;
    }

    // Store the left-hand side
    output[0] = left;

    // Reset the right-hand side of the binary search (left-hand side remains as is)
    right = nums.length - 1;

    // Binary search for the target (right-biased)
    while (left < right) {
        let middle = Math.floor((left + right) / 2) + 1;
        if (nums[middle] <= target) {
            left = middle;
        } else {
            right = middle - 1;
        }
    }

    // Store the right-hand side
    output[1] = right;

    return output;
};

Note #1: It is possible to simplify this code by adding a parameter such as “bias direction” to a binary search function and then calling the same function to find each side, but as that damages readability I’ve gone with the more drawn-out approach.

Note #2: This approach could be altered to use a binary search to find the left-hand side, and then a for loop from that point to find the right-hand side. I would argue that said approach would more readable, but it would be less efficient, so I won’t include it here.

Conclusion

That’s all folks! In this post, we solved LeetCode problem #34. Find First and Last Position of the Element in Sorted Array

I hope you have enjoyed this post. Feel free to share your thoughts on this.

 

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!