2774. Array Upper Bound

Problem Description

The task is to extend all arrays in a programming environment to include a new method called upperBound(). This method should be applicable to any array, and when called, it returns the index of the last occurrence of a specified target number within a given array. The array referenced by nums is sorted in ascending order and it can consist of repeated numbers, indicative of duplicates being allowed.

1. The upperBound(target: number): number method must be defined for all arrays.
2. The array provided (nums) is sorted in ascending order.
3. The target is the number whose upper bound index we need to find.
4. The "upper bound index" is defined as the index of the last occurrence of the target in the array.
5. If the target number is not present in the array, the method is expected to return -1.

In simple terms, if you've got an array like [1,2,2,3] and you call upperBound(2) on it, you should get 2, which is the index of the last occurrence of the number 2. If you search for a number not present in the array, such as upperBound(4), it should return -1.

Intuition

The solution for the upperBound function utilizes a modified binary search algorithm. Since the array is sorted, binary search is an ideal choice for the task due to its efficiency in logarithmic time complexity (O(log n)).

Here is a breakdown of the intuition behind the solution approach:

1. Initialization: Set two pointers, left at the start of the array and right at the end (technically, just past the last element).

2. Binary Search Loop: Continue to narrow the search range by adjusting left and right.

   • Calculate the middle index mid by averaging left and right and shifting right (>>1 is equivalent to dividing by 2).
   • If the element at mid is greater than the target, move the right pointer to mid, as the target, if it exists, must be to the left of mid.
   • Otherwise, move the left pointer to mid + 1, since we're looking for the last occurrence of target.

3. Result: Once the loop ends, if left is greater than 0 and the element at left - 1 equals the target, then the upper bound is found, and the index left - 1 is returned.

   • If the target is not found, return -1.

In this way, the solution exploits the sorted nature of the array and efficiently finds the upper bound of a given target number, if present.

Solution Approach

The implementation of the upperBound method on the Array prototype in TypeScript follows a binary search approach to locate the last occurrence of the target number within an array. Binary search is a well-known algorithm for finding an item in a sorted list, and it works by repeatedly dividing the search interval in half.

Here's a step-by-step explanation of how the solution works:

1. Extending the Prototype: First, the Array prototype is extended by defining the upperBound function, allowing all arrays to use this new method.

2. Initialization:

   • left is initialized to 0, representing the start of the array.
   • right is initialized to the length of the array, which is an index one past the last element, as this is a common pattern in binary search implementations to facilitate the calculations.

3. Binary Search Loop:

   • The search continues until left < right, which means there is still a range to be checked.
   • In each iteration, the mid point of the current range is calculated using the bit shift operator >>, which is a quick way to perform integer division by 2 (i.e., (left + right) >> 1).

4. Midpoint Evaluation:

   • If the value at the mid index is greater than the target, the target cannot be to the right of mid, so right is updated to mid. This effectively discards the second half of the current range.
   • If the value at mid is less than or equal to the target, the target can be at mid or to the right of it, so left is updated to mid + 1. Since we're looking for the last occurrence, we can safely ignore mid (even if it matches the target) because there might be another occurrence of target further to the right.

5. Post-Loop Check:

   • After the loop finishes, left is the index where the target either just surpasses the last target number or where the target would be inserted to maintain the sorted order of the array.
   • There's a check to see if left is greater than 0 and if the element at left - 1 equals target, returning left - 1 as it represents the last occurrence of target.

6. Default Case:

   • If the number is not found, the method defaults to returning -1, indicating the absence of the target number.

This approach ensures that the upperBound function can operate efficiently, typically requiring O(log n) time to find the upper bound of the target in the array, where n is the number of elements in the array.

Example usage of the upperBound method could look like this:

1console.log([3,4,5].upperBound(5)); // Output: 2
2console.log([1,4,5].upperBound(2)); // Output: -1
3console.log([3,4,6,6,6,6,7].upperBound(6)); // Output: 5

This implementation assumes that the environment supports modifications to the Array prototype and that the arrays in question are sorted in ascending order.

Example Walkthrough

Let's go through the solution approach with a small example. Suppose we have an array nums and we want to find the upper bound index of the target number 2 in this array:

nums = [1, 2, 2, 3, 4].

1. First, since we want to extend all arrays with the upperBound method, we define this method in the Array prototype.

2. To start the binary search, we initialize two variables, left to 0 and right to nums.length (which is 5 in this case, as the array has elements from index 0 to 4).

3. Enter the binary search loop. Our target is 2, so we check the middle of the array between left and right. Since our current left is 0 and right is 5, the middle index mid is calculated as (0 + 5) >> 1, which is 2.

4. Now, we check the value at index 2, which is also 2. Since we are looking for the last occurrence and the middle value is equal to our target, we move the left pointer up, to mid + 1 to continue the search in the right half of the current range. After this, left is now 3, and right remains 5.

5. We iterate again, and now mid is (3 + 5) >> 1, which is 4. The element at index 4 is 4, which is greater than our target 2. Hence, we move the right pointer down to mid, making right now equal to 4.

6. The next iteration starts, but since left is still less than right, we calculate a new mid (3 + 4) >> 1, which is 3. The element at index 3 is 3, which is greater than our target 2, so again we move right to mid. The value of right is now 3.

7. At this point, left and right are equal, indicating that the search space is empty so the loop ends.

8. After the loop, we perform a final check. Since left is 3 and we are asked to return left - 1, we check if the element at index 2 is equal to 2, and it is. Therefore, the upper bound index is indeed 2.

9. If the target had been a number not present in the array, like 5, we would have eventually narrowed down to a point where left would equal right and the check of nums[left - 1] would not match the target, thus, the function would return -1.

This example illustrates how the upperBound method works on a simple array using binary search principles. It efficiently narrows down the search and accurately finds the last occurrence of the target number 2, or confirms the target's absence if it's not in the array.

Solution Implementation

Time and Space Complexity

The time complexity of the Array.prototype.upperBound function is O(log n), where n is the number of elements in the array. This is because the function uses a binary search approach, which repeatedly divides the array in half and thus has a logarithmic time complexity.

The space complexity of the function is O(1). It uses only a constant amount of additional space regardless of the size of the input array since all operations are performed in place and it only uses a fixed number of variables (left, right, and mid).