Problem

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.

Examples

Example 1:

1
2
3

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

Example 2:

1
2
3

Input: nums = [1,4,5], target = 2
Output: -1
Explanation: Because there is no digit 2 in the array, return -1.

Example 3:

1
2
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^4
  • -10^4 <= nums[i], target <= 10^4
  • nums is sorted in ascending order.

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

Solution

Method 1 – Binary Search 1

Intuition

Since the array is sorted, we can use binary search to efficiently find the last occurrence of the target. Binary search helps us skip over large sections of the array, making the search much faster than a linear scan.

Approach

  1. Set two pointers, l (left) and r (right), to the start and end of the array.
  2. While l is less than or equal to r:
    • Find the middle index m.
    • If nums[m] is less than or equal to target, move l to m + 1 (search right side).
    • Otherwise, move r to m - 1 (search left side).
  3. After the loop, check if r is within bounds and nums[r] equals target.
  4. If so, return r (last index of target). Otherwise, return -1.
JavaScript
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

Array.prototype.upperBound = function(target) {
    let l = 0, r = this.length - 1, ans = -1;
    while (l <= r) {
        let m = Math.floor((l + r) / 2);
        if (this[m] <= target) {
            if (this[m] === target) ans = m;
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
    return ans;
};
TypeScript
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

declare global {
    interface Array<T> {
        upperBound(target: number): number;
    }
}

Array.prototype.upperBound = function(target: number): number {
    let l = 0, r = this.length - 1, ans = -1;
    while (l <= r) {
        let m = Math.floor((l + r) / 2);
        if (this[m] <= target) {
            if (this[m] === target) ans = m;
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
    return ans;
};
export {};

Complexity

  • ⏰ Time complexity: O(log n)
  • 🧺 Space complexity: O(1)