Skip to content

2774. Array Upper Bound πŸ”’

DifficultyEasy

Description

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?

Solutions

Thinking

Find the last index of \(\textit{target}\) in a sorted array. A right-to-left scan is correct, but a logarithmic bound is available.

Binary-search the first index greater than \(\textit{target}\); the previous index is the rightmost hit if it equals \(\textit{target}\), otherwise the value is absent.

The array is sorted in non-decreasing order. Binary search for the first index greater than \(\textit{target}\), then check whether the previous element equals \(\textit{target}\). If it does, that index is the last occurrence; otherwise return \(-1\).

The time complexity is \(O(\log n)\), and the space complexity is \(O(1)\), where \(n\) is the length of the array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
declare global {
    interface Array<T> {
        upperBound(target: number): number;
    }
}

Array.prototype.upperBound = function (target: number) {
    let left = 0;
    let right = this.length;
    while (left < right) {
        const mid = (left + right) >> 1;
        if (this[mid] > target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left > 0 && this[left - 1] == target ? left - 1 : -1;
};

// [3,4,5].upperBound(5); // 2
// [1,4,5].upperBound(2); // -1
// [3,4,6,6,6,6,7].upperBound(6) // 5

Solution 2: Linear Scan

Thinking

Binary search buys a logarithm at the cost of endpoint logic. \(\textit{lastIndexOf}\) scans once from the right and is shorter, though linear in the worst case.

Call \(\textit{lastIndexOf}\) to scan from right to left and return the last index of the target, or \(-1\) if it does not exist.

The time complexity is \(O(n)\), and the space complexity is \(O(1)\), where \(n\) is the length of the array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
declare global {
    interface Array<T> {
        upperBound(target: number): number;
    }
}

Array.prototype.upperBound = function (target: number) {
    return this.lastIndexOf(target);
};

// [3,4,5].upperBound(5); // 2
// [1,4,5].upperBound(2); // -1
// [3,4,6,6,6,6,7].upperBound(6) // 5

Comments