Smaller Values to the Right

Hard

An analyst is looking at a series of daily price changes values and, for each day, wants to know how many later days had a smaller change. Return an array of the same length whose entry i is the number of indices j > i with values[j] < values[i] (strictly smaller). Checking every pair takes O(n²); aim for something faster.

Example 1

values=[3, 7, 1, 7, 2] → [2, 2, 0, 1, 0]

To the right of 3 the smaller values are 1 and 2; the first 7 also has 1 and 2 (the other 7 is not smaller); nothing smaller follows 1; the second 7 is followed only by 2; the last element has nothing to its right.

Example 2

values=[4, 4, 4] → [0, 0, 0]

Equal values do not count as smaller, so every count is zero.

Example 3

values=[-5] → [0]

Constraints

1 ≤ len(values) ≤ 10⁵
-10⁴ ≤ values[i] ≤ 10⁴

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Binary Indexed Tree Segment Tree Array Binary Search Divide and Conquer Ordered Set Merge Sort

Similar problems

Window Sums Within a Band Hard Pairs With a Steep Drop Hard Cost of Filling a Sorted Shelf Hard Triples Both Rankings Agree On Hard Pairs Within a Shifted Gap Hard

Input

values=[3, 7, 1, 7, 2]

Expected

[2, 2, 0, 1, 0]

Run checks the first 3 tests in your browser. Submit checks all 138 tests on the server, hidden ones included.