Array Upper Bound - Practice Coding Problems

Array Upper Bound - Problem

JavaScript Easy

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.

The method should be added to Array.prototype so it can be called on any array.

Input & Output

Example 1 — Basic Case with Duplicates

$ Input: nums = [1,2,2,2,3], target = 2

› Output: 3

💡 Note: Target 2 appears at indices 1, 2, 3. The last occurrence is at index 3.

Example 2 — Single Occurrence

$ Input: nums = [1,3,5,7,9], target = 5

› Output: 2

💡 Note: Target 5 appears only once at index 2, so that's the last occurrence.

Example 3 — Target Not Found

$ Input: nums = [1,3,5,7,9], target = 4

› Output: -1

💡 Note: Target 4 is not present in the array, so return -1.

Constraints

1 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
nums is sorted in ascending order
-10⁴ ≤ target ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Sorted array with duplicates and target value

Process

Find the rightmost occurrence of target

Output

Index of last occurrence or -1 if not found

Key Takeaway

🎯 Key Insight: Use binary search to find upper bound, then check if target exists at that position minus one

Asked in

G Google 25 M Microsoft 20 a Amazon 18

Brief HTML summary: The key insight is to use binary search on sorted arrays for O(log n) performance. Best approach is binary search upper bound which finds the boundary efficiently. Time: O(log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Linear Search	O(n)	O(1)	Scan array from left to right, track last occurrence of target
Binary Search Upper Bound	O(log n)	O(1)	Use binary search to find the rightmost position where target can be inserted

Linear Search — Algorithm Steps

Step 1: Initialize result as -1
Step 2: Scan array left to right
Step 3: Update result whenever target is found

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set result = -1, start from index 0

Scan Array

Check each element, update result when target found

Last Update

Final result contains the rightmost occurrence

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize, int target) {
    int result = -1;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] == target) {
            result = i;
        }
    }
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    int target;
    scanf("%d", &target);
    printf("%d\n", solution(nums, numsSize, target));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array of length n

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables

✓ Linear Space

23.4K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Linear Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler