Welcome to Subscribe On Youtube

2774. Array Upper Bound

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

Solution 1: Sliding Window + Bit Manipulation

This implementation uses sliding window, followed by bit manipulation. It traverses the relevant values and updates its state as each value is processed. After all required states have been considered, the maintained result is returned.

Solution 2

This implementation follows the required operations directly. After all required states have been considered, the maintained result is returned.

• TypeScript

• 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
  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
  
  

All Problems

All Solutions