Skip to main content
Talentd

Array Upper Bound - Solution & Explanation

EasyPremiumFree on FleetCode3 min read
Practice this problem

Problem Statement

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 <= 104
  • nums is sorted in ascending order.

 

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

Approach Overview

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.

Solution

Code

TypeScript

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Linear ScanO(n)O(1)Small arrays or when simplicity matters more than performance
Binary Search Upper BoundO(log n)O(1)Sorted arrays where fast lookups are required

Video Solution

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 →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Array Upper Bound with our built-in code editor and test cases.

Practice on FleetCode
Previous

Array Prototype Last

Next

Group By