# Figure out why O(N^2) solution with HashMap gets TLE

• I first came up the O(N^2) solution with HashMap from 2Sum question as below.
Got TLE result occasionally and found other people have similar issue in discussion.
And most voted solution is also O(N^2).

Figured out the tricky part is at this line: if (numPos[numK] > j)
Even though numPos[numK] is an O(1) operation in theory, but it contains 2 operations if numK is not in numPos:

• lookup numK in numPos, O(1)
• insert numK in numPos with default value 0, O(1)
Insert operation may cause hash map rehash, which is a big penalty in time.

So the fix is also easy, run time dropped from 800ms down to 270ms, close to most voted solution 120ms in my submission.
auto iter = numPos.find(numK);
if (iter == numPos.end())
continue;

if (iter->second > j)
...

``````vector<vector<int>> threeSum1(vector<int>& nums) {
unordered_map<int, int> numPos;
numPos.reserve(10 * nums.size());
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++)
numPos[nums[i]] = i;

vector<vector<int>> result;
int endI = nums.size() - 2;
int endJ = nums.size() - 1;
for (int i = 0; i < endI; i++) {
if (i > 0 && nums[i] == nums[i - 1])
continue;

int numI = nums[i];
for (int j = i + 1; j < endJ; j++) {
if (j > 0 && nums[j] == nums[j - 1])
continue;

int numJ = nums[j];
int numK = -(numI + numJ);
if (numPos[numK] > j)
result.emplace_back(vector<int>({numI, numJ, numK}));
}
}
return result;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.