Problem Description

This problem asks you to extend JavaScript's Array prototype with a custom method called upperBound(). The method should work on sorted arrays of numbers (in ascending order) and find the last occurrence of a given target number.

The key requirements are:

1. Input: The array is sorted in ascending order and may contain duplicate values. The method takes a target number as its parameter.

2. Output:

   • If the target exists in the array, return the index of its last occurrence
   • If the target doesn't exist in the array, return -1

3. Implementation: The method should be added to all arrays through prototype extension, allowing you to call it directly on any array instance like [3,4,5].upperBound(5).

Examples:

• [3,4,5].upperBound(5) returns 2 (the last index where 5 appears)
• [1,4,5].upperBound(2) returns -1 (2 is not in the array)
• [3,4,6,6,6,6,7].upperBound(6) returns 5 (the last index where 6 appears, even though 6 appears multiple times)

The solution uses a binary search approach to efficiently find the position just after the last occurrence of the target, then checks if the element at the previous position equals the target to determine the result.

Intuition

Since we need to find the last occurrence of a target in a sorted array, we can think about this problem as finding the first element that is greater than our target. Once we find that position, the element just before it (if it exists and equals the target) would be our answer.

The key insight is that in a sorted array with duplicates, all occurrences of a number are grouped together. So if we can find where the next larger number starts, we can step back one position to find the last occurrence of our target.

Consider the array [3,4,6,6,6,6,7] and target 6:

• Instead of searching for the last 6 directly, we search for the position where elements become greater than 6
• Binary search will lead us to index 6 (where 7 is located)
• Step back one position to index 5, and we find the last 6

This approach naturally handles the case where the target doesn't exist. If we find the position where elements become greater than the target, but the previous element isn't equal to the target, then the target was never in the array.

The binary search modification is subtle but important:

• When this[mid] > target, we move right = mid (this position might be our answer for "first greater")
• When this[mid] <= target, we move left = mid + 1 (we need to go further right to find something greater)

This ensures we always converge to the first position where an element is greater than the target. The final check this[left - 1] == target confirms whether the target actually exists in the array.

Solution Approach

The implementation extends the Array prototype to add the upperBound method using a modified binary search algorithm.

Step-by-step implementation:

1. Initialize binary search boundaries:

   let left = 0;
   let right = this.length;

   We set right to the array length (not length - 1) to handle the case where all elements are less than or equal to the target.

2. Binary search loop:

   while (left < right) {
       const mid = (left + right) >> 1;
       if (this[mid] > target) {
           right = mid;
       } else {
           left = mid + 1;
       }
   }

   • Calculate mid using bit shift >> 1 (equivalent to Math.floor((left + right) / 2))
   • If this[mid] > target: Move right to mid because we found an element greater than target
   • If this[mid] <= target: Move left to mid + 1 to continue searching for the first element greater than target

3. Determine the result:

   return left > 0 && this[left - 1] == target ? left - 1 : -1;

   After the loop, left points to the first position where an element is greater than the target (or the array's end if no such element exists).

   • Check if left > 0 to ensure we don't access an invalid index
   • Check if this[left - 1] == target to verify the target exists
   • If both conditions are true, return left - 1 (the last occurrence index)
   • Otherwise, return -1

Time Complexity: O(log n) where n is the array length, due to binary search.

Space Complexity: O(1) as we only use a constant amount of extra space.

The beauty of this approach is that it leverages the sorted nature of the array to find the boundary between elements that are <= target and elements that are > target, making it efficient even for arrays with many duplicates.

Example Walkthrough

Let's trace through the algorithm with array [2, 5, 5, 5, 8, 9] and target 5.

Goal: Find the last occurrence of 5 (which should be index 3).

Initial State:

• Array: [2, 5, 5, 5, 8, 9]
• left = 0, right = 6 (array length)
• Target: 5

Iteration 1:

• mid = (0 + 6) >> 1 = 3
• this[3] = 5, which equals target
• Since 5 <= 5, set left = mid + 1 = 4
• New range: left = 4, right = 6

Iteration 2:

• mid = (4 + 6) >> 1 = 5
• this[5] = 9, which is greater than target
• Since 9 > 5, set right = mid = 5
• New range: left = 4, right = 5

Iteration 3:

• mid = (4 + 5) >> 1 = 4
• this[4] = 8, which is greater than target
• Since 8 > 5, set right = mid = 4
• New range: left = 4, right = 4

Loop ends (left == right)

Final Check:

• left = 4 (pointing to first element greater than 5)
• Check: left > 0 ✓ and this[left - 1] = this[3] = 5 equals target ✓
• Return left - 1 = 3

The algorithm correctly identifies index 3 as the last occurrence of 5.

Edge Case Example: Array [1, 3, 7] with target 5

• Binary search converges to left = 2 (position where 7 > 5)
• Check: this[left - 1] = this[1] = 3 ≠ 5
• Return -1 (target not found)

Solution Implementation

Time and Space Complexity

Time Complexity: O(log n) where n is the length of the array. The algorithm uses binary search to find the position. In each iteration, the search space is halved by comparing the middle element with the target. The while loop runs at most log₂(n) times since we divide the search space by 2 in each iteration.

Space Complexity: O(1) - The algorithm only uses a constant amount of extra space for the variables left, right, and mid. No additional data structures are created that scale with the input size. The modification is done to the Array prototype itself, but this doesn't count toward the space complexity of the algorithm execution.

Common Pitfalls

1. Off-by-One Error in Binary Search Boundary

Pitfall: A common mistake is initializing right = len(arr) - 1 instead of right = len(arr). This can cause the algorithm to fail when all elements in the array are less than or equal to the target.

Example of the issue:

# Incorrect implementation
def upperBound_wrong(arr, target):
    left = 0
    right = len(arr) - 1  # WRONG: should be len(arr)
  
    while left < right:
        mid = (left + right) // 2
        if arr[mid] > target:
            right = mid
        else:
            left = mid + 1
  
    return left - 1 if left > 0 and arr[left - 1] == target else -1

# This fails for: upperBound_wrong([1, 2, 3], 3)
# Returns -1 instead of 2

Solution: Always initialize right = len(arr) to properly handle the case where the target is greater than or equal to all elements.

2. Integer Overflow in Mid Calculation

Pitfall: In languages with fixed-size integers, calculating mid = (left + right) // 2 can cause integer overflow when left and right are very large.

Solution: Use mid = left + (right - left) // 2 to avoid overflow:

def upperBound_safe(arr, target):
    left = 0
    right = len(arr)
  
    while left < right:
        # Overflow-safe mid calculation
        mid = left + (right - left) // 2
      
        if arr[mid] > target:
            right = mid
        else:
            left = mid + 1
  
    return left - 1 if left > 0 and arr[left - 1] == target else -1

3. Incorrect Loop Condition

Pitfall: Using left <= right instead of left < right can cause infinite loops or incorrect results.

Example of the issue:

# Incorrect loop condition
def upperBound_infinite(arr, target):
    left = 0
    right = len(arr)
  
    while left <= right:  # WRONG: can cause infinite loop
        mid = (left + right) // 2
        if arr[mid] > target:
            right = mid  # When left == right == mid, this creates infinite loop
        else:
            left = mid + 1
  
    return left - 1 if left > 0 and arr[left - 1] == target else -1

Solution: Always use left < right as the loop condition when right is initialized to len(arr).

4. Forgetting to Check Array Bounds

Pitfall: Not checking if left > 0 before accessing arr[left - 1] can cause an IndexError when the target is smaller than all elements.

Example of the issue:

# Missing bounds check
def upperBound_no_check(arr, target):
    left = 0
    right = len(arr)
  
    while left < right:
        mid = (left + right) // 2
        if arr[mid] > target:
            right = mid
        else:
            left = mid + 1
  
    # WRONG: Missing left > 0 check
    return left - 1 if arr[left - 1] == target else -1
    # This crashes when target < arr[0], as left becomes 0

Solution: Always verify left > 0 before accessing arr[left - 1] to prevent index out of bounds errors.