Reduce Runtime Complexity

HardPython00:00

Practice interviewer

In session

5 left

00:00

Your question is Reduce Runtime Complexity. Start with the requirements on the right.

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

You need to log in / sign up to run or submit.

Problem

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 solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output