medium10 pts · first answer countshash-mapcounting

Counting four-list sums to zero

Given four lists A, B, C, D of length n, you count tuples with A[i] + B[j] + C[k] + D[l] = 0. What is the hash map approach and its cost?

A.Count all A+B sums, then look up -(C+D) for each pair: O(n²)B.Sort all four and use four pointers: O(n log n)C.Try every tuple with early exit: O(n³)D.Put all values in one Set: O(n)

Discussion 0

Join free to post in the discussion.

Counting four-list sums to zero

Discussion 0

Related questions