Demo: Find the Range of Threes

In this lesson, we will explore another, slightly more challenging problem: Find The Range of Threes.

Problem Description

// Implement a function `findRange` that takes in an array of
// integers sorted in ascending order. The function should
// return an array containing the starting and ending
// positions of the number 3 within the array. If the number 3
// is not found, return [-1, -1].

// Example:
// Input: nums = [1, 2, 3, 3, 3, 3, 3, 4, 5]
// Output: [2, 6]

// Example:
// Input: nums = [1, 2, 5, 5, 6, 9, 10]
// Output: [-1, -1]

This problem is not as straightforward as the one in the previous assignment. Try solving it first without referring to the solution below.

The trick in this problem is that finding the value is not the end of the binary search. One might think that once the value is found, we can iterate left and right to find the leftmost and rightmost occurrences. However, what if the array was [3, 3, 3, 3, 3, 3]? In this case, the solution would be linear O(N), which defeats the purpose of using binary search.

There must be a more efficient solution, and indeed there is. Instead of performing just one binary search, we can perform two binary searches. To improve readability, we can split them into two separate helper functions: findLeftMostIndex and findRightMostIndex.

To find the leftmost index, we perform a regular binary search using the standard template. However, instead of returning the target value when found, we assign it to a variable leftMost and continue searching on the left side of the array. Similarly, for the rightmost index, we perform a binary search, assign the target value to rightMost when found, and continue searching on the right side of the array.

The solution to the problem is the return value of these two functions.

---

Walkthrough

Let's walk through the step-by-step solution to the problem given an array [1, 2, 3, 3, 3, 3, 3, 4, 5].

Part 1 - Finding the leftmost value

Step 1: We initialize the left pointer at index 0 and the right pointer at index nums.length - 1, or 8 in this case. These pointers represent the starting and ending indices of the search range.

Step 2: We enter the binary search loop. We calculate the mid index as (left + right) / 2, which gives us 4. The number at index 4 is 3, which is our target value. Instead of returning the target value immediately, we assign it to the variable leftMost and continue searching on the left side by reassigning right to mid - 1, which becomes 3.

Step 3: We calculate the mid index as (left + right) / 2, which gives us 1. The number at index 1 is 2, which is less than three. Therefore, we update the left pointer to mid + 1, which becomes 2.

Step 4: In the next step, we calculate the mid index again, which gives us 2. The number at index 2 is 3, our target value. We update the leftMost variable to 2 and continue searching on the left by reassigning right to mid - 1, which becomes 1.

Step 5: The left pointer is now greater than the right pointer, so we end the search and return the leftmost value, which is index 2.

---

Part 2 - Finding the rightmost value

Step 1: Just like when finding the leftmost value, we initialize the left pointer at index 0 and the right pointer at index nums.length - 1, 8.

Step 2: In the second step, we calculate the mid index as (left + right) / 2, which gives us 4. The number at index 4 is 3, our target value. We assign it to the variable rightMost and continue searching on the right side by updating the left pointer to mid + 1, which becomes 5.

Step 3: In the third step, we calculate mid once again, which gives us 6 rounded down. The number at index 6 is 3, our target value. We update the rightMost variable to 6 and continue searching on the right by reassigning left to mid + 1, which becomes 7.

Step 4: Finally, we calculate mid, which gives us 7 rounded down. The number at index 7 is 4, which is greater than three. We update the right pointer to mid - 1, which becomes 6.

Step 5: Since the right pointer is now less than the value of the left pointer, we stop the search and return the rightmost value, which is 6.

---

Solution Code

Finally, here's the code solution for the problem:

function findRangeOfThrees(nums) {
  return [findLeftMostIndex(nums), findRightMostIndex(nums)];
}

function findLeftMostIndex(nums) {
  let left = 0;
  let right = nums.length - 1;
  let leftMost = -1;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (nums[mid] === 3) {
      leftMost = mid;
      right = mid - 1;
    } else if (nums[mid] < 3) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return leftMost;
}

function findRightMostIndex(nums) {
  let left = 0;
  let right = nums.length - 1;
  let rightMost = -1;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (nums[mid] === 3) {
      rightMost = mid;
      left = mid + 1;
    } else if (nums[mid] < 3) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return rightMost;
}

console.log(findRangeOfThrees([1, 2, 3, 3, 3, 3, 3, 4, 5])); // [2, 6]
console.log(findRangeOfThrees([1, 2, 5, 5, 6, 9, 10]));      // [-1, -1]
console.log(findRangeOfThrees([]));                          // [-1, -1]

Time Complexity

The time complexity of this solution is O(2logN) since we perform two binary searches. However, we can simplify it to O(logN) by eliminating the constants.

Through this example, we can see how binary search can be applied to solve more complex problems that require finding multiple occurrences or specific patterns within a sorted array. By carefully designing the search criteria and updating the search range, we can effectively navigate through the array and locate the desired elements.