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


  • 0
    J

    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;
    }

Log in to reply
 

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