Is Array Upper Bound easy or hard?

Array Upper Bound is considered an easy problem because the logic is short once you understand binary search boundaries. The main challenge is remembering the exact pointer updates that ensure the algorithm returns the first value strictly greater than the target.

Array Upper Bound Python/Java solution

In Python or Java, the same binary search logic applies: maintain left and right pointers, compute mid, and adjust the search range depending on whether arr[mid] is greater than the target. Many standard libraries also provide built-in helpers such as bisect_right in Python that directly return the upper bound index.

How to solve Array Upper Bound in O(log n)?

Use binary search with two pointers, left and right. If arr[mid] is greater than the target, move the right pointer to mid; otherwise move left to mid + 1. When the loop finishes, the left pointer represents the first index where the value is greater than the target.

What is the best approach for Array Upper Bound?

Binary search is the best approach. Because the array is sorted, you can repeatedly halve the search range until you locate the first element greater than the target. This runs in O(log n) time and O(1) space, which is significantly faster than scanning the entire array.

Is Array Upper Bound asked at Google/Amazon/Meta?

Binary search boundary problems like upper bound and lower bound frequently appear in interviews at companies such as Google, Amazon, and Meta. They test whether candidates understand how to modify binary search to locate range boundaries rather than exact matches.

What data structure is used in Array Upper Bound?

The problem operates on a sorted array. The algorithm relies on binary search over the array indices, using constant extra space and simple pointer movement.

What is the time complexity of Array Upper Bound?

The optimal binary search solution runs in O(log n) time with O(1) extra space. A simpler linear scan approach takes O(n) time because it may need to check every element in the array.

2774. Array Upper Bound - Practice Online

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 <= 10⁴
-10⁴ <= nums[i], target <= 10⁴
nums is sorted in ascending order.

Follow up: Can you write an algorithm with O(log n) runtime complexity?