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 Onsite rounds at Snapchat.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Snapchat during technical interviews.

Implement binary search for boundary index

Company: Snapchat

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Given a sorted integer array nums (length n) and an integer target t, return the index of the first element in nums that is greater than or equal to t. If no such element exists, return -1. Provide both iterative and recursive implementations, handle duplicate values correctly, and analyze time and space complexity. Explain how you would adapt your solution to find the last element less than or equal to t.

Quick Answer: This question evaluates a candidate's ability to implement binary search for boundary indices, including correct handling of duplicates, providing iterative and recursive variants, and reasoning about time and space complexity.

Given a sorted (non-decreasing) integer array `nums` of length `n` and an integer target `t`, return the index of the first element in `nums` that is greater than or equal to `t` (the lower bound). If no such element exists, return `-1`. With duplicate values, you must return the index of the FIRST (leftmost) qualifying element, not just any matching index. The solution should run in O(log n) time. Examples: - `nums = [1, 3, 5, 7]`, `t = 4` -> `2` (the first element >= 4 is 5 at index 2) - `nums = [1, 2, 4, 4, 4, 8]`, `t = 4` -> `2` (leftmost 4) - `nums = [1, 2, 3]`, `t = 5` -> `-1` (no element >= 5) Follow-up (discuss, not coded): how would you adapt the same template to find the index of the LAST element less than or equal to `t`? (Search for the upper boundary instead: track the rightmost index whose value <= t.)

Constraints

0 <= n <= 10^5
nums is sorted in non-decreasing order
-10^9 <= nums[i], t <= 10^9
Return -1 when every element is strictly less than t (including the empty-array case)

Examples

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

Expected Output: 2

Explanation: 5 at index 2 is the first element >= 4.

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

Expected Output: 2

Explanation: Duplicates: the leftmost 4 sits at index 2.

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

Expected Output: -1

Explanation: No element is >= 5, so return -1.

Input: ([2, 4, 6], 2)

Expected Output: 0

Explanation: The first element 2 already satisfies >= 2.

Input: ([], 1)

Expected Output: -1

Explanation: Empty array has no qualifying element.

Input: ([5], 5)

Expected Output: 0

Explanation: Single element equal to target qualifies at index 0.

Input: ([5], 6)

Expected Output: -1

Explanation: Single element 5 < 6, so no element qualifies.

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

Expected Output: 1

Explanation: First element >= -4 is -3 at index 1; works with negatives.

Input: ([1, 1, 1, 1], 1)

Expected Output: 0

Explanation: All duplicates equal to target: leftmost index is 0.

Input: ([10, 20, 30], 0)

Expected Output: 0

Explanation: Target below all elements: the first element already qualifies.

Hints

Use a half-open search interval [lo, hi) where lo = 0 and hi = n. This lets you cleanly represent the 'insertion point' when no element qualifies.
On each step, if nums[mid] >= t the answer could be mid or to its left, so move hi = mid; otherwise move lo = mid + 1. Never discard a candidate by setting hi = mid - 1.
After the loop, lo is the count of elements < t. If lo == n, no element is >= t, so return -1; otherwise lo is the leftmost qualifying index.
For the follow-up (last element <= t), mirror the logic: find the first index whose value > t, then subtract one (and check it is in bounds).

Quick Overview

This question evaluates a candidate's ability to implement binary search for boundary indices, including correct handling of duplicates, providing iterative and recursive variants, and reasoning about time and space complexity.