454. 4Sum II | My practice | Amazon OA | August 27, 2021

 Aug. 27, 2021

Plan to spend 10 minutes to read solution using Leetcode premium version. I will solve the problem and share my discussion post here. 

Here is the link related to Amazon OA discussion. 

The goal | Reduce time complexity from brute force O(N^4) to O(N^2)

Complexity Analysis

• Time Complexity: $\mathcal{O}(n^2)$. We have 2 nested loops to count sums, and another 2 nested loops to find complements.

• Space Complexity: $\mathcal{O}(n^2)$ for the hashmap. There could be up to $\mathcal{O}(n^2)$ distinct a + b keys.