Compute delay times in priority array
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
##### Question
Given an array of integers representing task priorities processed from right to left, return an array where each element is the distance (index difference) to the first smaller priority found to its right (or 0 if none exists). Design an algorithm faster than O(N^
2).
Quick Answer: This question evaluates algorithmic efficiency in array processing, specifically reasoning about nearest-smaller relationships and the use of auxiliary structures to achieve subquadratic performance.
You are given an array `priorities` of integers representing task priorities. Conceptually the tasks are scanned from right to left. For each index `i`, return the distance (the difference in indices) to the **first task to its right that has a strictly smaller priority**. If no such task exists to the right of `i`, the answer for that index is `0`.
Return an array `result` of the same length, where `result[i]` is this distance for index `i`.
Your algorithm must run faster than O(N^2).
Example:
- Input: `[5, 3, 8, 4, 2, 6]`
- Output: `[1, 3, 1, 1, 0, 0]`
Explanation:
- i=0 (5): first smaller to the right is 3 at index 1 -> distance 1.
- i=1 (3): first smaller is 2 at index 4 -> distance 3.
- i=2 (8): first smaller is 4 at index 3 -> distance 1.
- i=3 (4): first smaller is 2 at index 4 -> distance 1.
- i=4 (2): nothing smaller to the right -> 0.
- i=5 (6): nothing to the right -> 0.
Constraints
- 0 <= len(priorities) <= 10^5
- -10^9 <= priorities[i] <= 10^9
- "First smaller" means strictly smaller; equal priorities do not count.
- If no strictly smaller priority exists to the right, the result for that index is 0.
- Required time complexity is better than O(N^2).
Examples
Input: ([5, 3, 8, 4, 2, 6],)
Expected Output: [1, 3, 1, 1, 0, 0]
Explanation: Worked example: 5->3(d1), 3->2(d3), 8->4(d1), 4->2(d1), 2->none, 6->none.
Input: ([1, 2, 3, 4],)
Expected Output: [0, 0, 0, 0]
Explanation: Strictly increasing — no element ever has a smaller element to its right.
Hints
- A brute force scan to the right for every index is O(N^2). Think about what work you can reuse across indices.
- Process the array from right to left and maintain a monotonic stack of indices whose priorities are strictly increasing from bottom to top.
- Before recording the answer for index i, pop every stacked index whose priority is >= priorities[i] — those can never be the 'first smaller' for any element further left either. The top of the stack after popping (if any) is the first strictly smaller element to the right.