Compute rightmost-smaller delay times
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
Given an integer array priorities, define delay[i] as the distance to the rightmost index j > i such that priorities[j] < priorities[i]; if no such index exists, delay[i] = 0. Equal values do not count as smaller. For example, priorities = [8, 2, 11, 4, 9, 4, 7] yields delay = [6, 0, 4, 0, 2, 0, 0] because for 8 the first smaller when scanning from the right is 7 at index 6. Implement a function that computes the entire delay array in better than O(n^
2) time. State and justify the time and space complexity, and explain how your approach handles duplicates and edge cases (e.g., strictly decreasing or increasing arrays).
Quick Answer: This question evaluates proficiency in efficient array-processing algorithms, reasoning about time and space complexity, and correct handling of duplicates and edge cases when computing distances to rightmost smaller elements.
Given an integer array `priorities`, define `delay[i]` as the distance to the **rightmost** index `j > i` such that `priorities[j] < priorities[i]`. If no such index exists, `delay[i] = 0`. Equal values do **not** count as smaller.\n\nReturn the entire `delay` array. Aim for better than O(n^2) time.\n\n**Example**\n\nInput: `priorities = [8, 2, 11, 4, 9, 4, 7]`\nOutput: `[6, 0, 4, 0, 2, 0, 0]`\n\nExplanation: For `8` at index 0, scanning from the right the rightmost value smaller than 8 is `7` at index 6, so `delay[0] = 6 - 0 = 6`. For `11` at index 2 the rightmost smaller value is also `7` at index 6, so `delay[2] = 4`. For `9` at index 4 it is `7` at index 6, so `delay[4] = 2`. The value `2` has nothing smaller to its right, and each `4` only sees an equal `4` or larger values (or `7`, which is not smaller), so their delays are 0.
Constraints
- 0 <= n <= 10^5
- -10^9 <= priorities[i] <= 10^9
- The array may contain duplicate values; equal values are NOT counted as smaller.
- Must run in better than O(n^2) time.
Examples
Input: ([8, 2, 11, 4, 9, 4, 7],)
Expected Output: [6, 0, 4, 0, 2, 0, 0]
Explanation: The worked example: 8->7@6 (6), 11->7@6 (4), 9->7@6 (2); 2 and the 4's and final 7 have no strictly-smaller element to the right.
Input: ([],)
Expected Output: []
Explanation: Empty array returns an empty result.
Hints
- A naive scan-right per element is O(n^2). You need a structure that answers 'rightmost position with a value below a threshold' quickly.
- Build a segment tree over positions storing the minimum value in each segment.
- To find the rightmost qualifying index, descend the tree preferring the right child first; only enter a subtree whose stored minimum is < the query value. This yields the rightmost match in O(log n).
- Duplicates are handled by the strict '<' comparison: equal values never qualify. Strictly increasing arrays yield all zeros; strictly decreasing arrays yield delay[i] = n-1-i.