Find First And Last Position Of Element In Sorted Array [Python]

In the world of programming and problem-solving, there are numerous challenges that require a deep understanding of algorithms and data structures.

One such challenge is the Find First And Last Position Of Element In Sorted Array problem, which is presented as LeetCode Problem 34. In this blog post, we will explore this problem, provide a Python solution, analyze the time and space complexity, and offer a detailed explanation of the solution.

So, let’s dive into it!

Problem Overview

Question Link: LeetCode Problem 34

The problem statement goes as follows:

Given an array of integers nums sorted in non-decreasing order, your task is to find the starting and ending position of a given target value.

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

Additionally, there’s a crucial constraint: you must design an algorithm with O(log n) runtime complexity.

This constraint implies that a brute-force approach won’t suffice, and you need a more efficient solution.

Example 1:

Let’s illustrate the problem with an example:

Input:
nums = [5, 7, 7, 8, 8, 10]
target = 8

Output:

[3, 4]

In this case, the target value is 8, and it appears twice in the array.

The starting index is 3, and the ending index is 4.

Example 2:

Input:

nums = [5, 7, 7, 8, 8, 10]
target = 6

Output:

[-1, -1]

This time, the target value is 6, which is not present in the array.

Therefore, the function returns [-1, -1].

Constraints:

To further understand the problem, let’s look at the constraints provided:

• The length of the nums array can be as large as 10^5.
• The values within nums are integers ranging from -10^9 to 10^9.
• The array nums is always sorted in non-decreasing order.
• The target value can also be within the range of -10^9 to 10^9.

Now, let’s proceed to the efficient Python code solution for this problem.

Efficient Python Code Solution

We’ll tackle this problem using a modified binary search approach.

We need to find both the leftmost and rightmost positions of the target value.

The primary idea is to run binary search twice, considering a left bias in one search and a right bias in the other.

Here’s the Python code solution:

def searchRange(nums, target):
    left = binSearch(nums, target, True)
    right = binSearch(nums, target, False)
    return [left, right]

def binSearch(nums, target, leftBias):
    l, r = 0, len(nums) - 1
    i = -1

    while l <= r:
        m = (l + r) // 2

        if target > nums[m]:
            l = m + 1
        elif target &lt; nums[m]:
            r = m - 1
        else:
            i = m
            if leftBias:
                r = m - 1
            else:
                l = m + 1

    return i

This code consists of two main parts: the searchRange function, which orchestrates the left and right searches, and the binSearch function, which is a modified binary search.

In the searchRange function, we call the binSearch function twice, once with True to find the leftmost index and once with False to find the rightmost index.

The results are then combined and returned as [left, right].

The binSearch function performs the binary search.

It has three parameters: nums (the input array), target (the value we’re looking for), and leftBias, which determines whether we’re searching for the leftmost or rightmost occurrence.

In the binSearch, we initialize the left and right pointers.

We also maintain an i variable to store the index of the target value whenever we find it.

The while loop keeps executing until the left pointer is greater than or equal to the right pointer.

Within the loop, we compute the middle index and compare the target value to the element at that index.

Depending on the comparison, we either move the left or right pointer, or if we find the target value, we update i.

Crucially, we check the leftBias parameter to decide whether to continue searching to the left or right after finding a target value.

If leftBias is True, we search to the left, aiming for the leftmost occurrence.

If it’s False, we search to the right, seeking the rightmost occurrence.

This binary search algorithm, with its bias modification, allows us to efficiently find the desired indices with O(log n) complexity.

Time and Space Complexity

Now, let’s analyze the time and space complexity of our solution:

• Time Complexity: Our binary search operates in O(log n) time, and we call it twice, making it a total of O(2 * log n) or simply O(log n).

This satisfies the problem’s constraint for efficient runtime.

• Space Complexity: The space complexity is O(1) since we use a constant amount of extra space to store variables and results.

The space used is not dependent on the input size.

Reasoning Behind Our Approach

The reasoning behind our approach lies in the efficient utilization of binary search.

By running two binary searches, we effectively locate both the leftmost and rightmost occurrences of the target value in the sorted array.

The left bias and right bias conditionals allow us to adapt the search to our specific needs, ensuring a time complexity of O(log n).

Related Interview Questions By Company:

• Interleaving String LeetCode
• Range Sum Query 2D Immutable LeetCode
• Sort Colors LeetCode

Related Interview Questions By Difficulty:

• Split Array Largest Sum LeetCode
• Guess Number Higher Or Lower LeetCode
• Valid Perfect Square LeetCode

Related Interview Questions By Category:

• Reverse Linked List II LeetCode
• Permutations II LeetCode
• Find All Numbers Disappeared In An Array LeetCode

Conclusion

In this blog post, we tackled the Find First And Last Position Of Element In Sorted Array problem, which is presented as LeetCode Problem 34.

We provided an efficient Python solution that leverages binary search with bias modification to find the leftmost and rightmost indices of the target value.

We also analyzed the time and space complexity of our solution, demonstrating that it meets the problem’s requirement of O(log n) runtime complexity.

This problem showcases the power of binary search and how it can be adapted to various scenarios to efficiently solve complex challenges.

We hope this explanation has been helpful, especially for those new to algorithmic problem-solving.

If you have any questions, comments, or suggestions, please feel free to share them in the comments section below.

Happy coding and keep exploring the fascinating world of algorithms!