LeetCode 2774 - Array Upper Bound

LeetCode Problem 2774

Difficulty: 🟢 Easy
Topics: —

Solution

Problem Understanding

The problem asks us to enhance JavaScript arrays with a method called upperBound(). Given a sorted array of numbers and a target value, the method should return the last index where the target appears. If the target does not exist in the array, the method should return -1.

The key detail is that the array is sorted in ascending order and may contain duplicate values. Because duplicates are allowed, simply finding the first occurrence is not enough. We specifically need the rightmost, or last, occurrence of the target.

For example, in the array [3,4,6,6,6,6,7], the number 6 appears multiple times. The correct answer is 5, because index 5 is the final occurrence of 6.

The input consists of:

• A sorted ascending array nums
• A target integer target

The output is:

• The largest index where nums[index] == target
• -1 if the target does not exist

The constraints tell us several important things:

• The array length can be up to 10^4
• The array is already sorted
• Values can be negative
• Duplicate values are allowed

The follow up asks for an O(log n) solution, which strongly suggests binary search. Since the array is sorted, we can use binary search not just to determine whether the target exists, but also to locate the final occurrence efficiently.

Several edge cases are important:

• The target may not exist at all
• The array may contain only one element
• Every element may equal the target
• The target may appear multiple times consecutively
• The target may appear only once
• The target could be smaller than all elements or larger than all elements

A naive implementation can easily fail when duplicates exist, especially if it stops immediately after finding the target instead of continuing to search for the rightmost occurrence.

Approaches

Brute Force Approach

The simplest solution is to scan the array from left to right and keep updating the answer whenever we encounter the target.

For example:

• Start with answer = -1
• Iterate through the array
• If nums[i] == target, set answer = i
• After the loop finishes, return answer

This works because the final matching index encountered during traversal will naturally be the last occurrence.

Although this approach is straightforward and correct, it requires examining every element in the worst case. Since the follow up explicitly asks for O(log n) complexity, we need something faster.

Optimal Approach

The important observation is that the array is sorted.

Binary search normally finds whether an element exists in logarithmic time. However, we can slightly modify binary search to continue searching even after finding the target.

The idea is:

• If nums[mid] == target, record mid as a possible answer
• Continue searching to the right, because there may be another occurrence later in the array

This guarantees that we eventually find the rightmost occurrence.

Because each binary search step cuts the search space in half, the runtime becomes O(log n).

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Scans the entire array and keeps track of the latest match
Optimal	O(log n)	O(1)	Uses binary search to locate the last occurrence efficiently

Algorithm Walkthrough

1. Initialize two pointers, left and right, representing the current binary search range.
2. Initialize a variable called answer to -1. This variable stores the latest valid occurrence of the target.
3. While left <= right, compute the middle index:

mid = (left + right) // 2

4. Compare nums[mid] with the target.
5. If nums[mid] == target, store mid in answer because this is a valid occurrence. However, do not stop searching yet. Move left to mid + 1 to continue searching the right half for a later occurrence.
6. If nums[mid] < target, the target can only exist in the right half, so move left to mid + 1.
7. If nums[mid] > target, the target can only exist in the left half, so move right to mid - 1.
8. Continue until the search range becomes empty.
9. Return answer. If the target was never found, answer remains -1.

Why it works

The algorithm maintains the invariant that any valid occurrence of the target to the right of the current midpoint is still searchable. Whenever we find the target, we do not terminate immediately because a later occurrence may exist. By continuing the search on the right side, we guarantee that the final stored index is the largest valid index containing the target.

Python Solution

from typing import List

class Solution:
    def upperBound(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1
        answer = -1

        while left <= right:
            mid = (left + right) // 2

            if nums[mid] == target:
                answer = mid
                left = mid + 1
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        return answer

The implementation begins by initializing the binary search boundaries and the answer variable.

The while loop continues as long as there is a valid search range. Each iteration computes the midpoint and compares its value against the target.

When the midpoint equals the target, we store the midpoint as a candidate answer. However, instead of returning immediately, we continue searching the right half because duplicates may exist later in the array.

If the midpoint value is too small, the search shifts right. If the midpoint value is too large, the search shifts left.

At the end of the loop, answer contains the largest valid index where the target appears, or -1 if the target was never found.

Go Solution

package main

func upperBound(nums []int, target int) int {
	left := 0
	right := len(nums) - 1
	answer := -1

	for left <= right {
		mid := left + (right-left)/2

		if nums[mid] == target {
			answer = mid
			left = mid + 1
		} else if nums[mid] < target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}

	return answer
}

The Go implementation follows the same logic as the Python version. One small difference is the midpoint calculation:

mid := left + (right-left)/2

This form avoids potential integer overflow in languages where integers have fixed size limits. Although overflow is not an issue under these constraints, this is standard binary search practice in Go and many other systems languages.

Go slices are used instead of Python lists, but the indexing behavior is conceptually identical.

Worked Examples

Example 1

Input:

nums = [3,4,5]
target = 5

Step	left	right	mid	nums[mid]	answer	Action
1	0	2	1	4	-1	Move right
2	2	2	2	5	2	Record answer, move right
End	3	2	-	-	2	Stop

Final answer:

2

Example 2

Input:

nums = [1,4,5]
target = 2

Step	left	right	mid	nums[mid]	answer	Action
1	0	2	1	4	-1	Move left
2	0	0	0	1	-1	Move right
End	1	0	-	-	-1	Stop

Final answer:

-1

Example 3

Input:

nums = [3,4,6,6,6,6,7]
target = 6

Step	left	right	mid	nums[mid]	answer	Action
1	0	6	3	6	3	Record answer, move right
2	4	6	5	6	5	Record answer, move right
3	6	6	6	7	5	Move left
End	6	5	-	-	5	Stop

Final answer:

5

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log n)	Binary search halves the search range each iteration
Space	O(1)	Only a few variables are used

The runtime is logarithmic because each comparison removes half of the remaining search space. The algorithm does not allocate additional data structures proportional to input size, so the space usage remains constant.

Test Cases

solution = Solution()

assert solution.upperBound([3, 4, 5], 5) == 2  # target at end
assert solution.upperBound([1, 4, 5], 2) == -1  # target absent
assert solution.upperBound([3, 4, 6, 6, 6, 6, 7], 6) == 5  # multiple duplicates

assert solution.upperBound([1], 1) == 0  # single element present
assert solution.upperBound([1], 2) == -1  # single element absent

assert solution.upperBound([2, 2, 2, 2], 2) == 3  # all elements equal target
assert solution.upperBound([1, 2, 3, 4, 5], 1) == 0  # target at beginning
assert solution.upperBound([1, 2, 3, 4, 5], 5) == 4  # target at end

assert solution.upperBound([1, 2, 2, 2, 3], 2) == 3  # clustered duplicates
assert solution.upperBound([-5, -3, -3, 0, 2], -3) == 2  # negative numbers

assert solution.upperBound([1, 3, 5, 7], 0) == -1  # target smaller than all
assert solution.upperBound([1, 3, 5, 7], 10) == -1  # target larger than all

Test	Why
[3,4,5], target=5	Verifies target at last position
[1,4,5], target=2	Verifies missing target
[3,4,6,6,6,6,7], target=6	Verifies rightmost duplicate detection
[1], target=1	Smallest valid array with match
[1], target=2	Smallest valid array without match
[2,2,2,2], target=2	All elements identical
[1,2,3,4,5], target=1	Target at first position
[1,2,3,4,5], target=5	Target at last position
[1,2,2,2,3], target=2	Duplicate cluster in middle
[-5,-3,-3,0,2], target=-3	Handles negative values
[1,3,5,7], target=0	Target smaller than minimum
[1,3,5,7], target=10	Target larger than maximum

Edge Cases

One important edge case occurs when the target does not exist in the array. A careless implementation might accidentally return the closest value or terminate incorrectly. This solution avoids that issue by initializing answer to -1 and updating it only when an exact match is found.

Another important case is when every element equals the target. For example, [2,2,2,2] should return 3. A standard binary search that stops at the first match would fail here. This implementation continues searching to the right after each match, ensuring the final occurrence is found.

A third important edge case involves single element arrays. Arrays such as [1] can expose off by one mistakes in binary search boundaries. The condition while left <= right ensures that even a single remaining index is checked correctly.

A fourth subtle edge case is when the target appears at the very beginning or very end of the array. Incorrect pointer movement can skip these boundary positions. Because this implementation always narrows the search range carefully and includes both endpoints, boundary targets are handled correctly.