O(n^2) c++ runtime less than 100ms (beats 99.04% of solutions) with explaination


  • 0
    J

    A lot of the solutions would have two while loops after sorting: one iterating on the outside and another doing the twoSum in O(n) in the inside. They would do a check for adjacent indices to make sure duplicates do not get stored. Here is an approach that does not explicitly call sort and as well condenses the array to a smaller array of only unique elements. This would run much faster when there is lots of duplicate in the array.

    First using a map, count the frequency of each number. The map will also serve to sort the numbers because it is ordered and it will find all the unique numbers. Example [3, 0, 0, 0, 2] would become keys [0, 2, 3] with values [3, 1, 1].

    Then iterate through these unique keys in order. An observation is that when you reach nums[i] >= 0 there is no need to iterate further because three positive numbers cannot add up to zero. Once you select a unique nums[i], you can do the classic twoSum O(n) search to find matching pairs. Note that this would result you having all your triplets that equal zero and have no repeating numbers.

    To handle the repeating numbers, the frequency comes into play.

    If the frequency of the number is greater than or equal to one, then all the triplets with non repeating number is correct. However, you could possibly have one nums[i] which is negative followed by two identical nums[j] which are positive. You can find nums[j] by looking at your frequency map. This occurs when nums[i] is an even number:

    // (-0.5*nums_i) + (-0.5*nums_i) + nums_i = 0
    if(nums_i % 2 == 0) {
        int half_nums_i = target/2;
        if(freq.find(half_nums_i) != freq.end() && freq[half_nums_i] >= 2) {
            res.push_back(vector<int>{half_nums_i, half_nums_i, nums_i});
        }
    }
    

    If frequency is greater than or equal to two, you have the case where you could have two nums[i] which is negative followed by one positive nums[j]. This is seen here:

     // nums_i + nums_i + (-2*nums_i) = 0
    if(freq[nums_i] >= 2) {
        int two_nums_i = 2*target;
        if(freq.find(two_nums_i) != freq.end()) {
            res.push_back(vector<int>{nums_i, nums_i, two_nums_i});
        }
    }
    

    The last case is when the number is zero and the frequency of at least three. This means that you have 0 + 0 + 0 = 0 so just that add that to your result.

    The full solutions is below

    class Solution {
    public:
        vector<vector<int>> threeSum(vector<int>& nums) {
            vector<vector<int>> res;
            map<int, int> freq;
     
            // Get the frequency of each number
            int N = nums.size();
            for(int i = 0; i < N; i++) {
                if(freq.find(nums[i]) == freq.end()) freq[nums[i]] = 1;
                else freq[nums[i]]++;
            }
     
            // Store the unique numbers in a sorted order
            int count = freq.size();
            vector<int> uniq(count);
     
            int index = 0;
            for (map<int,int>::iterator it = freq.begin(); it != freq.end(); ++it, ++index) {
                uniq[index] = it -> first;
            }
     
            for(int i = 0; i < count; i++) {
                int nums_i = uniq[i];
                int target = -nums_i;
     
                int j = i + 1;
                int k = count - 1;
     
                // No positive integer besides zero can sum to zero so check if 3 zeros exist then break
                if(nums_i >= 0) {
                    if(nums_i == 0 && freq[nums_i] >= 3) res.push_back(vector<int>{0, 0, 0});
                    break;
                }
     
                // nums_i + nums_i + (-2*nums_i) = 0
                if(freq[nums_i] >= 2) {
                    int two_nums_i = 2*target;
                    if(freq.find(two_nums_i) != freq.end()) {
                        res.push_back(vector<int>{nums_i, nums_i, two_nums_i});
                    }
                }
     
                // (-0.5*nums_i) + (-0.5*nums_i) + nums_i = 0
                if(nums_i % 2 == 0) {
                    int half_nums_i = target/2;
                    if(freq.find(half_nums_i) != freq.end() && freq[half_nums_i] >= 2) {
                        res.push_back(vector<int>{half_nums_i, half_nums_i, nums_i});
                    }
                }
               
                // Generic O(n) sweep of two sum for unique elements
                while(j < k) {
                    int sum = uniq[j] + uniq[k];
                    if(sum == target) {
                        res.push_back(vector<int>{uniq[i], uniq[j], uniq[k]});
                        j++;
                        k--;
                    } else if(sum < target) {
                        j++;
                    } else {
                        k--;
                    }
                }
            }
     
            return res;
        }
    };
    

Log in to reply
 

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