Problem
For each number, find the closest earlier position containing a strictly smaller number. Equal numbers do not qualify. Positions start at 1; use 0 when there is no smaller number to the left.
Implement nearest_smaller_value(numbers).
Input
numbers: Numbers in their original order.
Output
Return one earlier position (or 0) for every input value.
Constraints
0…200,000 integers, each between −1,000,000,000 and 1,000,000,000. Empty input returns an empty list.
Examples
Input:
numbers = [4, 2, 5, 3]
Expected output:
expected = [0, 0, 2, 2]Input:
std::vector<long long> numbers = {4, 2, 5, 3};
Expected output:
std::vector<long long> expected = {0, 0, 2, 2};Input:
long[] numbers = new long[] {4, 2, 5, 3};
Expected output:
long[] expected = new long[] {0, 0, 2, 2};Explanation
4 has no earlier value and 2 has no smaller earlier value. Both 5 and 3 find the value 2 at position 2.
Input:
numbers = [2, 2, 2]
Expected output:
expected = [0, 0, 0]Input:
std::vector<long long> numbers = {2, 2, 2};
Expected output:
std::vector<long long> expected = {0, 0, 0};Input:
long[] numbers = new long[] {2, 2, 2};
Expected output:
long[] expected = new long[] {0, 0, 0};Explanation
Earlier equal values are not strictly smaller. Every answer is 0.
How to approach it
Try on your own first, then open one hint at a time.
Hint 1
For each position, you need the closest earlier value that is strictly smaller, not smaller-or-equal.
Hint 2
Maintain a monotonic stack of candidate values with their positions while scanning left to right.
Hint 3
Pop equal or larger values, since they can never be the nearest smaller answer for later elements.
Expected complexity
O(n) time, O(n) extra space
References
This challenge is adapted for CodeUtility. Follow the statement and constraints above.