Reduce Runtime Complexity | Dataford Interview Questions

MobiKwik's analytics pipeline needs to count pairs of distinct transaction amounts whose combined value lies within an inclusive range. A provided nested-loop implementation takes O(n²) time and does not scale for large batches.

Implement count_amount_pairs(amounts, low, high) to return the number of index pairs (i, j) such that i < j and low <= amounts[i] + amounts[j] <= high.

You must improve the runtime to O(n log n) or better. The returned count may be large, so Python's integer arithmetic should be used.

Formal Specification

Input: an integer array amounts, and integers low and high.
Output: an integer containing the number of valid index pairs.
Each array position represents a separate transaction. Equal amounts at different positions are counted as different transactions.
The input array may be modified by the algorithm.

Constraints

2 <= len(amounts) <= 200,000
-10^9 <= amounts[i] <= 10^9
-10^9 <= low <= high <= 10^9
Pairs are based on indices, so duplicate values at different positions are counted separately
The input array may be modified

Function Signature

def count_amount_pairs(amounts, low, high):

Your question is Reduce Runtime Complexity. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem