Leetcode #2774: Array Upper Bound

In this guide, we solve Leetcode #2774 Array Upper Bound in Python and focus on the core idea that makes the solution efficient.

You will see the intuition, the step-by-step method, and a clean Python implementation you can use in interviews.

Leetcode

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.

Quick Facts

Difficulty: Easy
Premium: Yes
Tags: JavaScript

Intuition

Because the array is sorted in ascending order, we can use binary search to jump to the answer.

The key is to find the first index where the value is greater than target (the upper bound). The last occurrence of target is one position before that.

Approach

Run a binary search for the first element greater than target.

If that position is pos, then the candidate answer is pos - 1. Validate it against the array bounds and the target value.

Steps:

Binary search for the first index with nums[mid] > target.
Set idx = pos - 1.
If idx is in range and nums[idx] == target, return idx; otherwise return -1.

Example

Input: nums = [3,4,5], target = 5
Output: 2
Explanation: Last index of target value is 2

Python Solution

class Solution:
    def upperBound(self, nums: List[int], target: int) -> int:
        lo, hi = 0, len(nums)
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] <= target:
                lo = mid + 1
            else:
                hi = mid
        idx = lo - 1
        return idx if idx >= 0 and nums[idx] == target else -1

Complexity

The time complexity is $O(\log n)$ , and the space complexity is $O(1)$ .

Edge Cases and Pitfalls

Watch for boundary values, empty inputs, and duplicate values where applicable. If the problem involves ordering or constraints, confirm the invariant is preserved at every step.

Summary

This Python solution focuses on the essential structure of the problem and keeps the implementation interview-friendly while meeting the constraints.

Approach

Run a binary search for the first element greater than target.

If that position is pos, then the candidate answer is pos - 1. Validate it against the array bounds and the target value.

Steps:

Binary search for the first index with nums[mid] > target.

Set idx = pos - 1.

If idx is in range and nums[idx] == target, return idx; otherwise return -1.

Python Solution

class Solution:
    def upperBound(self, nums: List[int], target: int) -> int:
        lo, hi = 0, len(nums)
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] <= target:
                lo = mid + 1
            else:
                hi = mid
        idx = lo - 1
        return idx if idx >= 0 and nums[idx] == target else -1

Leetcode #2774: Array Upper Bound

Problem Statement

Quick Facts

Intuition

Approach

Example

Python Solution

Complexity

Edge Cases and Pitfalls

Summary

Ace your next coding interview

Leetcode #2774: Array Upper Bound

Problem Statement

Quick Facts

Intuition

Approach

Example

Python Solution

Complexity

Edge Cases and Pitfalls

Summary

Ace your next coding interview