cswork / libraryOpen practice workspace

Coding questions · Amazon

Compute delay times in priority array

This question evaluates algorithmic efficiency in array processing, specifically reasoning about nearest-smaller relationships and the use of auxiliary structures to achieve subquadratic performance.

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

Compute Delay Times in Priority Array

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

Hints

  1. A brute force scan to the right for every index is O(N^2). Think about what work you can reuse across indices.
  2. Process the array from right to left and maintain a monotonic stack of indices whose priorities are strictly increasing from bottom to top.
  3. 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.