LeetCode Problem Link

https://leetcode.com/problems/3sum

Intuition

  • the combination of 3 out of N elements simply require O(n^3) time complexity
  • but we can reduce one inner-loop with two-pointers
  • use visit map for skipping duplicate combinations 
          unordered_map<int, vector<int>> visit;
      for (size_t i=0; i<n-2; ++i) {
          size_t l=i+1;
          size_t r=n-1;
          while (l<r) {
              if (-nums[i]>nums[l]+nums[r]) {
                  ++l;
                  continue;
              }
              if (-nums[i]<nums[l]+nums[r]) {
                  --r;
                  continue;
              }
              auto vit = visit.find(nums[i]);
              if (vit == end(visit)) {
                  result.push_back({nums[i], nums[l], nums[r]});
                  visit.emplace(nums[i], vector<int>({nums[l]}));
              }
              else {
                  auto& vec = vit->second;
                  auto it = std::upper_bound(begin(vec), end(vec), nums[l]-1);    // Use the binary search
                  if (it == end(vec)) {
                      result.push_back({nums[i], nums[l], nums[r]});
                      vec.push_back(nums[l]);
                  }
              }
              ++l;
              --r;
          }
      }

Approach

  • the series is sorted, then we can use skipping the same values to remove the visit map 
          int prv_i = nums[n-1];
      for (size_t i=0; i<n-2; ++i) {
          if (nums[i] == prv_i) continue;
          size_t l=i+1;
          size_t r=n-1;
          int prv_r = nums[0];
          while (l<r) {
              if (-nums[i]>nums[l]+nums[r]) {
                  ++l;
                  continue;
              }
              if ((nums[r] == prv_r) || (-nums[i]<nums[l]+nums[r])) {
                  --r;
                  continue;
              }
              result.push_back({nums[i], nums[l], nums[r]});
              prv_r = nums[r];
              ++l;
              --r;
          }
          prv_i = nums[i];
      }
  • basically, using previous value decrease readability
  • let’s use inner-while-loop for skipping the same values

Complexity

  • Time complexity: \(O(n^2)\)

  • Space complexity: \(O(1)\)

Code

    vector<vector<int>> threeSum(vector<int>& nums) {
        const size_t n = size(nums);
        vector<vector<int>> result;
        if (n<3) return result;
        if (n==3 && (nums[0]+nums[1]+nums[2]) != 0) return result;
        std::sort(begin(nums), end(nums));
        for (size_t i=0; i<n-2; ++i) {
            if (nums[i]>0) break;
            size_t l=i+1;
            size_t r=n-1;
            while (l<r) {
                if (-nums[i]>nums[l]+nums[r]) {
                    ++l;
                    continue;
                }
                if (-nums[i]<nums[l]+nums[r]) {
                    --r;
                    continue;
                }
                result.push_back({nums[i], nums[l], nums[r]});
                while (l<r && nums[l] == nums[l+1]) {
                    ++l;
                }
                while (l<r && nums[r] == nums[r-1]) {
                    --r;
                }
                ++l;
                --r;
            }
            while (i<n-2 && nums[i] == nums[i+1]) {
                ++i;
            }
        }
        return result;
    }

GitHub

3sum