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 rightmost-smaller delay times | Amazon Coding Question

Q: Compute rightmost-smaller delay times

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.

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.

Input: ([5],)

Expected Output: [0]

Explanation: A single element has nothing to its right, so its delay is 0.

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

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

Explanation: Strictly decreasing: the rightmost smaller element is always the last index, so delay[i] = n-1-i.

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

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

Explanation: Strictly increasing: no element ever has a smaller element to its right.

Input: ([4, 4, 4, 4],)

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

Explanation: All equal: equal values are not 'smaller', so every delay is 0.

Input: ([-3, 1, 0, -4, 4, -5, 4, -3, -3, 0],)

Expected Output: [5, 8, 6, 2, 5, 0, 3, 0, 0, 0]

Explanation: Mix of negatives and duplicates; e.g. -3@0's rightmost strictly-smaller is -5@5 (distance 5), and 1@1's is 0@9 (distance 8).

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

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

Explanation: 3@0's rightmost smaller is 1@3 (distance 3); 2@2's rightmost smaller is 1@3 (distance 1); the trailing 3 and the 1's have no strictly-smaller element to their right.

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.

Quick Overview

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.