Solving a Leetcode problem daily — Day 10 | Find first and last position in sorted array | by Subhradeep Saha | May, 2024 | Medium

Subhradeep Saha ・ May 11, 2024 ・

Medium

Here is the Leetcode problem link - https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/description/

Problem Statement

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 <= 10^5

• -10^9 <= nums[i] <= 10^9

• nums is a non-decreasing array.

• -10^9 <= target <= 10^9

High-Level Approach

Binary search to the rescue

The brute force solution entails iterating through each item in the input array to determine the first and last indices of the specified target.

However, since the input is in non-decreasing order, we can leverage binary search to take advantage of this characteristic and significantly reduce the time complexity to a logarithmic scale.

How are we finding the indices?

The first index corresponds to either the beginning of the array or the position where the previous number is different from the target. Likewise, the last index corresponds to either the end of the array or the position where the next number is different from the target.

In cases where the target is not present in the input array, both indices’ positions are returned as -1.

Code Implementation in C++

class Solution {
public:
  int findIdx(vector<int>& nums, int target, bool firstIdxSearch) {
    int l = 0, h = nums.size() - 1;
    while (l <= h) {
      int m = l + (h - l) / 2;
      if (nums[m] > target) {
        h = m - 1;
      } 
      else if (nums[m] < target) {
        l = m + 1;
      } 
      else {
        if (!firstIdxSearch) {
          // Find last occurrence
          if ((m == nums.size() - 1) || (nums[m + 1] != target)) {
            return m;
          }
          l = m + 1;
        } 
        else {
          // Find first occurrence
          if (!m || (nums[m - 1] != target)) {
            return m;
          }
          h = m - 1;
        }
      }
    }
    return -1;
  }
  vector<int> searchRange(vector<int>& nums, int target) {
      int firstIdx = findIdx(nums, target, true);
      if (firstIdx == -1) {
        return {-1, -1};
      }
      return {firstIdx, findIdx(nums, target, false)};
  }
};

Breakdown of the Code

findIdx Function: This util function takes three arguments:

• nums: The sorted array.

• target: The value to search for.

• firstIdxSearch: A boolean flag indicating whether to find the first or last occurrence of the target.

Binary Search Loop: The core logic resides within a while loop that continues as long as l (lower bound) is less than or equal to h (upper bound).

• Inside the loop, m (middle index) is calculated.

• The comparison between nums[m] and target determines the search direction:

=> If nums[m] > target, the target is in the lower half, so we update h to m-1.

=> If nums[m] < target, the target is in the upper half, so we update l to m+1.

=> If nums[m] == target, we've found a potential occurrence. The logic then diverges based on the firstIdx flag:

===> If firstIdxSearch is true (finding first occurrence), we check if this is truly the first by looking at nums[m-1] or is it at the beginning of the array. If not, we need to search in the left half (h = m-1).

===> Else, we check if this is the last by looking at nums[m+1] or is it at the end of the array. If not, we need to search in the right half (l = m+1).

Returning the Result:

• If the loop completes without finding the target (l becomes greater than h), the function returns -1.

• Otherwise, the function returns the index (m) of the found target occurrence, depending on whether it's the first or last based on the firstIdxSearch flag.

Dry Run with a Test Case

Let’s perform a dry run on the code using the example nums = [5,7,7,8,8,10] and target = 8:

Searching for First Occurrence (firstIdxSearch = true):

Iteration 1: l is set to 0, h is set to 5, and m is calculated as 2 (middle element):

Since nums[m] < target, we update l = m+1:

Iteration 2: Updated l = 3, h = 5 and m is calculated to be 4:

Now, nums[m] == target and nums[m-1] == target. So we update h as m — 1:

Iteration 3: Updated l = 3, h = 3 and m is calculated to be 3 as well:

Now, nums[m] == target and nums[m-1] != target, so we return m as the firstIdx.

Inside the main searchRange() function

After firstIdx is calculated to be not equal to -1, we proceed to again use the same findIdx() function to find the lastIdx of the target.

Searching for Last Occurrence (firstIdxSearch = false):

We call findIdx() again but now with the boolean firstIdxSearch set to false to find the last occurrence.

Iteration 1:l is set to 0, h is set to 5, and m is calculated as 2 (middle element):

Since nums[m] < target, we update l = m+1:

Iteration 2: Updated l = 3, h = 5 and m is calculated to be 4:

Now, nums[m] == target and nums[m+1] != target, so we return m as the lastIdx of the target.

Finally, we return {firstIdx = 3, lastIdx = 4} from the main function as the answer.

Complexity Analysis

• Time Complexity: O(log n). The findIdx() function divides the search space into half with every iteration leading to a logarithmic time complexity in terms of n(the size of the input array).

• Space Complexity: O(1). The code utilizes a constant amount of extra space for variables like l, h, and m, regardless of the array size (n).

Possible Improvements in the code

After the first findIdx() call, we obtain the index where the target is first found. Subsequently, for the second findIdx() call aimed at locating the last occurrence of the target, we can directly start the lower bound l as the output of the first findIdx() call instead of starting from 0. This is because we are certain that the target’s last occurrence cannot precede its first occurrence.

In the above example, when we call the findIdx() function to locate the last occurrence of the target (in this case, 8), we can optimize by using the output of the first call. This allows us to start processing directly from l = 3 (instead of l = 0) for the 2nd findIdx() function, thereby reducing the number of iterations required in the while loop.

Real-World Applications

• Log File Search and Analysis: ystem logs often contain timestamped records of events or errors. These logs can be sorted chronologically. When troubleshooting issues or analyzing system behavior within a specific timeframe (e.g., identifying errors that occurred between 10:00 AM and 11:00 AM), binary search can be used to efficiently locate the relevant log entries within the sorted time range.

• Financial Data Analysis and Trend Identification: Financial analysts might analyze historical stock prices which are often sorted chronologically. To identify periods where stock prices remained within a specific range (e.g., identifying days when a stock price stayed between $100 and $105), binary search can be applied to efficiently locate the relevant date ranges within the sorted price data.

Conclusion

This blog post delves into the problem of locating the initial and concluding positions of a target value within a sorted array. We explored the benefits of employing binary search for efficient searching, offer a comprehensive breakdown of the C++ code implementation, evaluated the time and space complexity, and investigated real-world applications of the given problem.

References

• https://developers.cloudflare.com/logs/

• https://www.quantconnect.com/learning/articles/introduction-to-financial-python

• Diagrams are made using Canva

• Cover Photo by Markus Winkler on Unsplash

What next?

If you’re intrigued by binary search algorithms, do check out my other posts where I delve into fascinating use cases that are solved using binary search.

• First Bad Version

• Sqrt(x)

Thank you for reading throughout! If you found this post insightful, please show your appreciation by liking this post and sharing it. Don’t forget to follow me for more engaging content like this. Your feedback is valuable, so please feel free to comment or reach out to me with any thoughts or suggestions.

Happy reading and happy coding!