PPractick

The problem

The same store's "filter up to ₹X" feature needs the first position whose price is strictly greater than X; everything before it is affordable. That position is the upper bound of X. Together with the lower bound, it answers many range questions at once, for example: how many items cost exactly X? That's upperBound − lowerBound. The only difference from lower bound is a single comparison, > instead of >=, which is precisely why the two are easy to mix up.

Example: [3, 5, 8, 9, 15, 19], X = 9 → 4 (the first price above 9 is 15, at index 4).

Function signature

int upperBound(const vector<int>& a, int x);  // smallest index i with a[i] > x, or n if none

Test cases

Input (a, x)	Output	Explanation
([1, 2, 2, 3], 2)	3	The first value after the 2s
([3, 5, 8, 9, 15, 19], 9)	4	15 is the first value > 9
([1, 2, 5, 6, 10], 10)	5	Nothing is greater: return n
([1, 2, 5, 6, 10], 0)	0	Everything is greater
([2, 2, 2], 2)	3
([], 4)	0

(Confirm: the array is sorted non-decreasingly; the result matches std::upper_bound.)

How interviewers phrase it

• "Find the upper bound of X in a sorted array" (Coding Ninjas).
• Hidden in: last occurrence (upper bound − 1), counting occurrences, "how many elements are ≤ X".

Clarifying questions to ask

1. Strictly greater than X?
2. What to return when nothing is greater: n?
3. Duplicates allowed?

Follow-ups to expect

1. "What's the one difference from lower bound?"
2. "How do you find the last occurrence of X?"
3. "How many elements equal X?"
4. "How many elements are ≤ X?"
5. "Complexity?"

Related questions

• Search X in sorted array Easy
• Lower Bound Easy
• Search insert position Easy
• Floor and Ceil in Sorted Array Easy
• Count Occurrences in a Sorted Array Easy
• Kth Missing Positive Number Easy

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in