Design faster delay-time computation
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
You are given an array of integers representing task priorities. Tasks execute from right to left. For each index i, define its delay time as j - i where j is the largest index > i such that priorities[j] < priorities[i] (i.e., the rightmost strictly smaller element to the right); if no such j exists, the delay time is 0. Return the delay time array for all indices. Example: for [8,2,11,4,9,4,7], the result is [6,0,4,0,2,0,0] (for 8 at index 0, the first smaller when scanning from the far right is 7 at index 6, so delay time is
6). Design an algorithm faster than O(n^
2); describe your data structures, analyze time and space complexity, and implement the solution. Handle duplicates and large inputs.
Quick Answer: This question evaluates a candidate's ability to design efficient array algorithms and appropriate data structures for nearest-smaller-element queries, assessing performance, correctness with duplicates, and scalability to large inputs.
You are given an array of integers `priorities` representing task priorities. Tasks execute conceptually from right to left. For each index `i`, define its **delay time** as `j - i`, where `j` is the **largest** index `j > i` such that `priorities[j] < priorities[i]` (i.e., the *rightmost* strictly-smaller element to the right of `i`). If no such `j` exists, the delay time is `0`. Return the array of delay times for every index.
Example: for `[8, 2, 11, 4, 9, 4, 7]` the answer is `[6, 0, 4, 0, 2, 0, 0]`. For the `8` at index 0, scanning from the far right the first element strictly smaller than 8 is `7` at index 6, so its delay time is `6 - 0 = 6`.
Design an algorithm faster than O(n^2). Describe your data structures, analyze time and space complexity, and handle duplicates and large inputs.
**Approach (O(n log n)):** Coordinate-compress the values to dense ranks. Build a segment tree indexed by rank that stores, for each rank bucket, the maximum array index inserted so far. Process the array from right to left; before inserting index `i`, query the tree over all ranks strictly less than `rank(priorities[i])` for the maximum stored index — that is the rightmost smaller element to the right. The delay time is `(that index) - i` (or 0 if the query returns nothing). Then insert `(rank(priorities[i]) -> i)` and continue.
Constraints
- 1 <= n <= 2 * 10^5 (large inputs must be handled; O(n^2) brute force times out)
- -10^9 <= priorities[i] <= 10^9
- Duplicate values are allowed; equal values do NOT count as 'strictly smaller'
- The delay time is based on the LARGEST (rightmost) qualifying index, not the nearest
Examples
Input: ([8, 2, 11, 4, 9, 4, 7],)
Expected Output: [6, 0, 4, 0, 2, 0, 0]
Explanation: For 8 (i=0), rightmost value < 8 to the right is 7 at index 6 -> 6. For 11 (i=2), rightmost smaller is 7 at index 6 -> 4. For 9 (i=4), rightmost smaller is 7 at index 6 -> 2. Others have no smaller element to their right.
Input: ([],)
Expected Output: []
Explanation: Empty input returns an empty result.
Hints
- Brute force is O(n^2): for each i scan all the way to the end for the rightmost smaller value. To beat it, avoid re-scanning by processing indices right-to-left and reusing a data structure keyed by value.
- Coordinate-compress values to dense ranks so you can index a segment tree by rank instead of by raw value (values can be up to 10^9 and negative).
- Maintain a segment tree over ranks where each leaf holds the maximum array index inserted so far for that rank. Processing right-to-left guarantees the tree only contains indices greater than the current i.
- For index i, query the tree over the range of ranks [0, rank(priorities[i]) - 1] for the maximum stored index. That maximum index is the rightmost strictly-smaller element to the right; subtract i to get the delay (0 if the query is empty).