Show problems as
Classic problem #493HardArrayBinary SearchDivide and ConquerBinary Indexed TreeSegment TreeMerge SortOrdered SetTreap

Reverse Pairs

Real-world version: Steep Decline Pairs
Tracked in this browser only
Read Reverse Pairs on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A transmitter logs one signed power level per sample into levels, in the order the samples were taken. Levels are calibration offsets, so they may be negative, zero or positive.

An analyst wants to know how often the signal fell away sharply between two samples, no matter how far apart those samples sat. Sample i and sample j make a steep decline when i < j and levels[i] > 2 * levels[j], using ordinary signed arithmetic. The comparison is strict: a level that is exactly double the later one does not qualify.

Count the steep declines in the log and return that count. Note that a pair is judged only by its two levels and by which sample came first; the samples in between are irrelevant.

Examples

Example 1

Input
levels = [6, 1, 4, 2]
Output
2

The pair of samples holding 6 then 1 qualifies because 6 beats 2, and 6 then 2 qualifies because 6 beats 4. The pair holding 4 then 2 fails, since 4 is exactly double and not more.

Example 2

Input
levels = [-1, -5, 3]
Output
1

Only -1 followed later by -5 qualifies, because doubling -5 gives -10 and -1 sits above it.

Example 3

Input
levels = [10, 5]
Output
0

Doubling the later level gives exactly the earlier one, and the rule needs a strict excess, so nothing is counted.

Constraints

  • 1 <= levels.length <= 5 * 10^4
  • -2^31 <= levels[i] <= 2^31 - 1
  • The count is at most 10^10.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def steep_declines(levels: list[int]) -> int:
Java
public int steepDeclines(int[] levels)

More on the same topics