How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Amazon during technical interviews.

Implement binary search lower/upper bounds

Quick Overview

Implement lower_bound and upper_bound on a non-decreasing sorted array using iterative binary search in O(log n) time and O(1) space. This Amazon ML engineer screen tests precise boundary handling, loop-invariant reasoning, and edge cases like duplicates, empty arrays, and out-of-range targets.

Implement binary search lower/upper bounds

Company: Amazon

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

##### Question Given a non-decreasing sorted integer array `nums` of length `n` and a `target` value, implement two functions using binary search: 1. **`lower_bound(nums, target)`** — return the smallest index `i` such that `nums[i] >= target`. Return `n` (i.e. `len(nums)`) if no such index exists. 2. **`upper_bound(nums, target)`** — return the smallest index `i` such that `nums[i] > target`. Return `n` (i.e. `len(nums)`) if no such index exists. **Requirements:** - Provide **iterative** implementations. - Achieve **O(log n)** time and **O(1)** extra space. - Handle the following edge cases: empty array; all elements strictly less than `target`; all elements strictly greater than `target`; duplicate values; negative numbers; and targets that fall outside the array’s value range. - Include a few **test cases** that demonstrate correctness. - Briefly **argue correctness**, explaining your boundary conditions and loop invariants. Note that `upper_bound(nums, target) - lower_bound(nums, target)` gives the count of elements equal to `target`, and both functions return a valid insertion point that keeps the array sorted.

Quick Answer: Implement lower_bound and upper_bound on a non-decreasing sorted array using iterative binary search in O(log n) time and O(1) space. This Amazon ML engineer screen tests precise boundary handling, loop-invariant reasoning, and edge cases like duplicates, empty arrays, and out-of-range targets.

Binary Search: lower_bound

Given a non-decreasing sorted integer array `nums` of length `n` and a `target` value, implement `lower_bound(nums, target)` iteratively using binary search: return the smallest index `i` such that `nums[i] >= target`. If no such index exists, return `n` (i.e. `len(nums)`), which is the valid insertion point that keeps the array sorted. Requirements: - Iterative implementation (no recursion). - O(log n) time, O(1) extra space. - Correctly handle: empty array; all elements strictly less than `target`; all elements strictly greater than `target`; duplicate values; negative numbers; and targets that fall outside the array's value range. With duplicates of `target` present, `lower_bound` returns the index of the FIRST occurrence.

Constraints

0 <= len(nums) <= 10^5
nums is sorted in non-decreasing order
-10^9 <= nums[i], target <= 10^9
Must be iterative with O(1) extra space

Examples

Input: ([1, 2, 2, 2, 4, 5], 2)

Expected Output: 1

Explanation: First index whose value is >= 2 is index 1 (the first of the three 2s).

Input: ([1, 2, 2, 2, 4, 5], 3)

Expected Output: 4

Explanation: 3 is absent; first value >= 3 is the 4 at index 4 — a valid insertion point.

Input: ([1, 2, 2, 2, 4, 5], 0)

Expected Output: 0

Explanation: target below the whole range; index 0 already satisfies nums[0]=1 >= 0.

Input: ([1, 2, 2, 2, 4, 5], 9)

Expected Output: 6

Explanation: target above the whole range; no element >= 9, so return n = 6.

Input: ([], 5)

Expected Output: 0

Explanation: Empty array: lo == hi == 0, loop never runs, return 0 == len(nums).

Input: ([-5, -3, -3, 0, 4], -3)

Expected Output: 1

Explanation: Negatives with duplicates; first index whose value >= -3 is index 1.

Input: ([-5, -3, -3, 0, 4], -10)

Expected Output: 0

Explanation: target below range of negatives; index 0 satisfies -5 >= -10.

Input: ([-5, -3, -3, 0, 4], 10)

Expected Output: 5

Explanation: target above range; no element >= 10, return n = 5.

Input: ([7], 7)

Expected Output: 0

Explanation: Single element equal to target; index 0 satisfies 7 >= 7.

Input: ([7], 8)

Expected Output: 1

Explanation: Single element strictly less than target; return n = 1.

Hints

Use a half-open search interval [lo, hi) with lo = 0 and hi = len(nums). Initializing hi to n (not n-1) is what lets the answer legitimately equal n (the not-found / insert-at-end sentinel).
Loop while lo < hi. When nums[mid] < target, the answer must be strictly right, so set lo = mid + 1; otherwise nums[mid] >= target so mid is a candidate, set hi = mid (do not exclude mid).
Invariant: every index < lo fails the predicate (nums[i] < target) and every index >= hi satisfies it; the interval shrinks every step, so on exit lo == hi is the first index with nums[i] >= target.

Binary Search: upper_bound

Given a non-decreasing sorted integer array `nums` of length `n` and a `target` value, implement `upper_bound(nums, target)` iteratively using binary search: return the smallest index `i` such that `nums[i] > target` (strictly greater). If no such index exists, return `n` (i.e. `len(nums)`), which is the valid insertion point that keeps the array sorted. Requirements: - Iterative implementation (no recursion). - O(log n) time, O(1) extra space. - Correctly handle: empty array; all elements strictly less than `target`; all elements strictly greater than `target`; duplicate values; negative numbers; and targets that fall outside the array's value range. With duplicates of `target` present, `upper_bound` returns the index ONE PAST the last occurrence. Note `upper_bound(nums, target) - lower_bound(nums, target)` equals the count of elements equal to `target`. This implementation differs from lower_bound by exactly one comparison: `<=` instead of `<`.

Constraints

0 <= len(nums) <= 10^5
nums is sorted in non-decreasing order
-10^9 <= nums[i], target <= 10^9
Must be iterative with O(1) extra space

Examples

Input: ([1, 2, 2, 2, 4, 5], 2)

Expected Output: 4

Explanation: Three 2s at indices 1-3; first value strictly > 2 is the 4 at index 4 (one past the last 2).

Input: ([1, 2, 2, 2, 4, 5], 3)

Expected Output: 4

Explanation: 3 absent; first value > 3 is the 4 at index 4. Same as lower_bound(3) here since 3 is missing.

Input: ([1, 2, 2, 2, 4, 5], 0)

Expected Output: 0

Explanation: Every element > 0; first such index is 0.

Input: ([1, 2, 2, 2, 4, 5], 9)

Expected Output: 6

Explanation: No element > 9, so return n = 6.

Input: ([1, 2, 2, 2, 4, 5], 5)

Expected Output: 6

Explanation: 5 is the last element; nothing is strictly greater, so return n = 6 (one past the last 5).

Input: ([], 5)

Expected Output: 0

Explanation: Empty array: loop never runs, return 0 == len(nums).

Input: ([-5, -3, -3, 0, 4], -3)

Expected Output: 3

Explanation: Two -3s at indices 1-2; first value > -3 is the 0 at index 3 (one past the last -3).

Input: ([-5, -3, -3, 0, 4], -10)

Expected Output: 0

Explanation: Every element > -10; first such index is 0.

Input: ([-5, -3, -3, 0, 4], 10)

Expected Output: 5

Explanation: No element > 10, return n = 5.

Input: ([7], 7)

Expected Output: 1

Explanation: Single element equal to target; nothing strictly greater, return n = 1.

Input: ([7], 6)

Expected Output: 0

Explanation: Single element 7 > 6; first such index is 0.

Hints

Reuse the lower_bound skeleton with a half-open interval [lo, hi), lo = 0, hi = len(nums). The only change needed is the predicate.
Partition on the stricter predicate nums[i] > target. Elements equal to target must NOT count, so when nums[mid] <= target push lo = mid + 1; only when nums[mid] > target set hi = mid.
Because <= sends equal elements to the right, upper_bound lands one index past the last occurrence of target, while lower_bound lands on the first — their difference is the count of target.

Quick Overview

Implement binary search lower/upper bounds

Company: Amazon

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Binary Search: lower_bound

Constraints

0 <= len(nums) <= 10^5
nums is sorted in non-decreasing order
-10^9 <= nums[i], target <= 10^9
Must be iterative with O(1) extra space

Examples

Input: ([1, 2, 2, 2, 4, 5], 2)

Expected Output: 1

Explanation: First index whose value is >= 2 is index 1 (the first of the three 2s).

Input: ([1, 2, 2, 2, 4, 5], 3)

Expected Output: 4

Explanation: 3 is absent; first value >= 3 is the 4 at index 4 — a valid insertion point.

Input: ([1, 2, 2, 2, 4, 5], 0)

Expected Output: 0

Explanation: target below the whole range; index 0 already satisfies nums[0]=1 >= 0.

Input: ([1, 2, 2, 2, 4, 5], 9)

Expected Output: 6

Explanation: target above the whole range; no element >= 9, so return n = 6.

Input: ([], 5)

Expected Output: 0

Explanation: Empty array: lo == hi == 0, loop never runs, return 0 == len(nums).

Input: ([-5, -3, -3, 0, 4], -3)

Expected Output: 1

Explanation: Negatives with duplicates; first index whose value >= -3 is index 1.

Input: ([-5, -3, -3, 0, 4], -10)

Expected Output: 0

Explanation: target below range of negatives; index 0 satisfies -5 >= -10.

Input: ([-5, -3, -3, 0, 4], 10)

Expected Output: 5

Explanation: target above range; no element >= 10, return n = 5.

Input: ([7], 7)

Expected Output: 0

Explanation: Single element equal to target; index 0 satisfies 7 >= 7.

Input: ([7], 8)

Expected Output: 1

Explanation: Single element strictly less than target; return n = 1.

Hints

Use a half-open search interval [lo, hi) with lo = 0 and hi = len(nums). Initializing hi to n (not n-1) is what lets the answer legitimately equal n (the not-found / insert-at-end sentinel).
Loop while lo < hi. When nums[mid] < target, the answer must be strictly right, so set lo = mid + 1; otherwise nums[mid] >= target so mid is a candidate, set hi = mid (do not exclude mid).
Invariant: every index < lo fails the predicate (nums[i] < target) and every index >= hi satisfies it; the interval shrinks every step, so on exit lo == hi is the first index with nums[i] >= target.

Binary Search: upper_bound

Constraints

0 <= len(nums) <= 10^5
nums is sorted in non-decreasing order
-10^9 <= nums[i], target <= 10^9
Must be iterative with O(1) extra space

Examples

Input: ([1, 2, 2, 2, 4, 5], 2)

Expected Output: 4

Explanation: Three 2s at indices 1-3; first value strictly > 2 is the 4 at index 4 (one past the last 2).

Input: ([1, 2, 2, 2, 4, 5], 3)

Expected Output: 4

Explanation: 3 absent; first value > 3 is the 4 at index 4. Same as lower_bound(3) here since 3 is missing.

Input: ([1, 2, 2, 2, 4, 5], 0)

Expected Output: 0

Explanation: Every element > 0; first such index is 0.

Input: ([1, 2, 2, 2, 4, 5], 9)

Expected Output: 6

Explanation: No element > 9, so return n = 6.

Input: ([1, 2, 2, 2, 4, 5], 5)

Expected Output: 6

Explanation: 5 is the last element; nothing is strictly greater, so return n = 6 (one past the last 5).

Input: ([], 5)

Expected Output: 0

Explanation: Empty array: loop never runs, return 0 == len(nums).

Input: ([-5, -3, -3, 0, 4], -3)

Expected Output: 3

Explanation: Two -3s at indices 1-2; first value > -3 is the 0 at index 3 (one past the last -3).

Input: ([-5, -3, -3, 0, 4], -10)

Expected Output: 0

Explanation: Every element > -10; first such index is 0.

Input: ([-5, -3, -3, 0, 4], 10)

Expected Output: 5

Explanation: No element > 10, return n = 5.

Input: ([7], 7)

Expected Output: 1

Explanation: Single element equal to target; nothing strictly greater, return n = 1.

Input: ([7], 6)

Expected Output: 0

Explanation: Single element 7 > 6; first such index is 0.

Hints

Reuse the lower_bound skeleton with a half-open interval [lo, hi), lo = 0, hi = len(nums). The only change needed is the predicate.
Partition on the stricter predicate nums[i] > target. Elements equal to target must NOT count, so when nums[mid] <= target push lo = mid + 1; only when nums[mid] > target set hi = mid.
Because <= sends equal elements to the right, upper_bound lands one index past the last occurrence of target, while lower_bound lands on the first — their difference is the count of target.