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 Citadel.

What role is this question designed for?

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

Find the Index Range of a Target in a Sorted Array

Quick Overview

This question evaluates a candidate's grasp of binary search and its adaptation to locate boundary positions within a sorted array. It tests the ability to design an algorithm that meets a strict logarithmic time complexity requirement rather than a simpler linear scan. Such problems are common in coding interviews to assess precision with edge cases and search-space reasoning.

Company: Citadel

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Given a sorted (non-decreasing) array of integers `nums` and an integer target `K`, find the index range `[first, last]` where `K` appears in `nums`: - `first` is the index of the first occurrence of `K`. - `last` is the index of the last occurrence of `K`. Every element in `nums[first..last]` (inclusive) must equal `K`. If `K` does not appear in `nums`, return `[-1, -1]`. Your solution must run in `O(log n)` time, where `n = len(nums)`. ### Constraints - `0 <= len(nums) <= 10^5` - `nums` is sorted in non-decreasing order. - `-10^9 <= nums[i] <= 10^9` - `-10^9 <= K <= 10^9` ### Examples - `nums = [5, 7, 7, 8, 8, 8, 10]`, `K = 8` → `[3, 5]` - `nums = [5, 7, 7, 8, 8, 8, 10]`, `K = 6` → `[-1, -1]` - `nums = [2, 2, 2, 2]`, `K = 2` → `[0, 3]` - `nums = [1]`, `K = 1` → `[0, 0]` - `nums = []`, `K = 0` → `[-1, -1]`

Quick Answer: This question evaluates a candidate's grasp of binary search and its adaptation to locate boundary positions within a sorted array. It tests the ability to design an algorithm that meets a strict logarithmic time complexity requirement rather than a simpler linear scan. Such problems are common in coding interviews to assess precision with edge cases and search-space reasoning.

Given a sorted (non-decreasing) array of integers `nums` and an integer target `K`, find the index range `[first, last]` where `K` appears in `nums`: - `first` is the index of the first occurrence of `K`. - `last` is the index of the last occurrence of `K`. Every element in `nums[first..last]` (inclusive) must equal `K`. If `K` does not appear in `nums`, return `[-1, -1]`. Your solution must run in `O(log n)` time, where `n = len(nums)`. ### Constraints - `0 <= len(nums) <= 10^5` - `nums` is sorted in non-decreasing order. - `-10^9 <= nums[i] <= 10^9` - `-10^9 <= K <= 10^9` ### Examples - `nums = [5, 7, 7, 8, 8, 8, 10]`, `K = 8` -> `[3, 5]` - `nums = [5, 7, 7, 8, 8, 8, 10]`, `K = 6` -> `[-1, -1]` - `nums = [2, 2, 2, 2]`, `K = 2` -> `[0, 3]` - `nums = [1]`, `K = 1` -> `[0, 0]` - `nums = []`, `K = 0` -> `[-1, -1]`

Constraints

0 <= len(nums) <= 10^5
nums is sorted in non-decreasing order.
-10^9 <= nums[i] <= 10^9
-10^9 <= K <= 10^9
Solution must run in O(log n) time.

Examples

Input: ([5, 7, 7, 8, 8, 8, 10], 8)

Expected Output: [3, 5]

Explanation: 8 first appears at index 3 and last at index 5.

Input: ([5, 7, 7, 8, 8, 8, 10], 6)

Expected Output: [-1, -1]

Explanation: 6 does not appear in nums.

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

Expected Output: [0, 3]

Explanation: Every element equals 2, so the range spans the whole array.

Input: ([1], 1)

Expected Output: [0, 0]

Explanation: Single-element array where the element matches K.

Input: ([], 0)

Expected Output: [-1, -1]

Explanation: Empty array contains nothing.

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

Expected Output: [4, 4]

Explanation: K is the last element, appearing once.

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

Expected Output: [0, 0]

Explanation: K is the first element, appearing once.

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

Expected Output: [3, 5]

Explanation: Handles negative values; 0 occupies indices 3 through 5.

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

Expected Output: [-1, -1]

Explanation: K falls between existing values but is not present.

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

Expected Output: [-1, -1]

Explanation: K is larger than every element.

Hints

Two occurrences of the same value form a contiguous block in a sorted array, so you only need the leftmost and rightmost index.
Use a lower_bound-style binary search: the first index where nums[i] >= K gives `first`.
For integer values, the first index where nums[i] >= K + 1 is one past the last occurrence, so `last = lower_bound(K + 1) - 1`. This uses only ONE binary-search primitive.
If lower_bound(K) is out of range or points to a value != K, then K is absent and you return [-1, -1].

Quick Overview