Write code that enhances all arrays such that you can call the upperBound() method on any array and it will return the last index of a given target number. nums is a sorted ascending array of numbers that may contain duplicates. If the target number is not found in the array, return -1.
Example 1:
Input: nums = [3,4,5], target = 5 Output: 2 Explanation: Last index of target value is 2
Example 2:
Input: nums = [1,4,5], target = 2 Output: -1 Explanation: Because there is no digit 2 in the array, return -1.
Example 3:
Input: nums = [3,4,6,6,6,6,7], target = 6 Output: 5 Explanation: Last index of target value is 5
Constraints:
1 <= nums.length <= 104-104 <= nums[i], target <= 104nums is sorted in ascending order.Follow up: Can you write an algorithm with O(log n) runtime complexity?
Problem Overview: You receive a sorted array and a target value. The goal is to return the upper bound index: the first position where the element is strictly greater than the target. If no such element exists, the result should be the array length.
Approach 1: Linear Scan (O(n) time, O(1) space)
The most direct solution iterates through the array from left to right and returns the first index where arr[i] > target. If the loop finishes without finding such an element, return arr.length. This works because the array is sorted, so the first element greater than the target is automatically the correct upper bound. The approach is easy to implement but inefficient for large arrays because it may examine every element.
Approach 2: Binary Search (O(log n) time, O(1) space)
The optimal solution uses binary search. Maintain two pointers, left and right, representing the current search range. Compute mid and compare arr[mid] with the target. If arr[mid] > target, this index might be the upper bound, so move right = mid. Otherwise move left = mid + 1 because all values at or before mid cannot be the answer. The loop shrinks the range until left points to the first element greater than the target.
This pattern appears frequently in array search problems. The key insight is that binary search does not just find exact matches. By adjusting the comparison condition, you can locate boundaries such as the first value greater than a target (upper bound) or the first value greater than or equal to a target (lower bound).
Binary search is especially valuable when arrays contain millions of elements. Instead of scanning the entire array, each iteration cuts the search space in half. After about log2(n) steps, the correct index is found.
Recommended for interviews: Interviewers expect the binary search approach. The linear scan demonstrates you understand the definition of an upper bound, but the O(log n) binary search solution shows stronger algorithmic thinking and familiarity with classic binary search boundary patterns.
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Linear Scan | O(n) | O(1) | Small arrays or when simplicity matters more than performance |
| Binary Search Upper Bound | O(log n) | O(1) | Sorted arrays where fast lookups are required |
BS-2. Implement Lower Bound and Upper Bound | Search Insert Position | Floor and Ceil • take U forward • 443,441 views views
Watch 9 more video solutions →Practice Array Upper Bound with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor