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 Take-home Project rounds at Amazon.

What role is this question designed for?

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

Compute delay times in priority array | Amazon Coding Question

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.

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

Expected Output: [1, 1, 1, 0]

Explanation: Strictly decreasing — each element's immediate right neighbor is smaller; last has none.

Input: ([7],)

Expected Output: [0]

Explanation: Single element has nothing to its right.

Input: ([],)

Expected Output: []

Explanation: Empty input returns an empty array.

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

Expected Output: [0, 0, 0, 0]

Explanation: All equal — equality is not 'strictly smaller', so every answer is 0.

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

Expected Output: [3, 2, 1, 0, 0]

Explanation: The first strictly smaller value (1 at index 3) is the target for the first three elements; the trailing 5 has nothing smaller to its right.

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

Expected Output: [1, 0, 0, 0]

Explanation: Negatives: -1's first smaller is -3 at distance 1; -3 has nothing smaller to its right; -2 and 0 likewise have no strictly smaller value to their 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.

Quick Overview

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