LeetCode 15. 3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

Example

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Solution

Hash Table

Time Complexity is $O(n^2)$.

// By Hash table:
// 1. Store all values in a hash table
// 2. Iterate all two-elements pair and 
//    try finding their complement(0 - sum of two elements) in the hash table
// Time Complexity:
//   - Store all values in a hash table: O(n)
//   - Iterate all two-elements pair: O(n^2)
//     - Find their complement in the hash table: O(1)
//     - Check if this triplet is counted (if complement is found)
//       - by red-black BST(std::set): O(log n^2)
//       - by hash table(std::unordered_map): O(1)
//   => Total: O(n) + O(n^2 * (1 + log n^2)) = O(n^2 (log n))
//          or O(n) + O(n^2 * (1 + 1)) = O(n^2)
vector<vector<int>> threeSum(vector<int>& nums) {
  vector<vector<int>> triplets;

  if (nums.size() < 3) {
    return triplets;
  }

  int target = 0;
  vector<int> values = removeRedundancy(nums, target);
  unordered_map<int, int> valueToIndex = getValueToLastIndex(values);
  triplets = getTriplets(values, valueToIndex, target);
  return triplets;
}

vector<int> removeRedundancy(vector<int>& nums, int target) {
  vector<int> trimmed;

  unordered_map<int, int> valueCount;
  for (int n : nums) {
    int count = valueCount.find(n) == valueCount.end() ? 0 : valueCount[n];
    if ((count == 2 && 3*n != target) || count > 2) {
      continue;
    }
    valueCount[n] = count + 1;
    trimmed.push_back(n);
  }

  return trimmed;
}

unordered_map<int, int> getValueToLastIndex(vector<int>& values) {
  unordered_map<int, int> valueToIndex;
  for (int i = 0 ; i < values.size() ; ++i) {
    valueToIndex[values[i]] = i;
  }
  return valueToIndex;
}

vector<vector<int>> getTriplets(vector<int>& values,
                                unordered_map<int, int>& valueToIndex,
                                int target) {
  vector<vector<int>> triplets;

  if (values.size() < 3) {
    return triplets;
  }

  // Use set to avoid duplicate triplet.
  set<vector<int>> triSet;
  for (int i = 0 ; i < values.size() ; ++i) {
    for (int j = i + 1 ; j < values.size() ; ++j) {
      int sum = values[i] + values[j];
      int complement = target - sum;
      if (valueToIndex.find(complement) == valueToIndex.end() ||
          valueToIndex[complement] == i ||
          valueToIndex[complement] == j) {
        continue;
      }
      vector<int> triplet({values[i], values[j], complement});
      sortTriplet(triplet);
      triSet.insert(triplet);
    }
  }

  // Put all triplet in set into vector so they can be unique.
  for (vector<int> triplet : triSet) {
    triplets.push_back(triplet);
  }

  return triplets;
}

// Bubble sort
void sortTriplet(vector<int>& t) {
  if (t[0] > t[1]) {
    swap(t[0], t[1]); // => t[1] > t[0]
  }
  if (t[1] > t[2]) {
    swap(t[1], t[2]); // => t[2] > t[1] and now t[2] > t[0]
  }
  if (t[0] > t[1]) {
    swap(t[0], t[1]); // => t[2] > t[1] > t[0]
  }
}

Two Pointers

// By leveraging the approach of LeetCode 167. Two Sum II - Input array is sorted:
// Find s + x + y = 0 => Find x + y = -s
// If s < x < y, then s <= 0. (s = 0 when x = y = 0)
//
// 1. Sort the array
// 2. Iterate all possible s in the array, and then search all (x, y) pairs
//
// Time Complexity:
//   - Sort the array: O(n log n)
//   - Iterate all possible s: O(n)
//     - Find (x, y) pairs in sorted array: O(n)
//   => Total: O(n log n) + O(n * n) = O(n^2)
vector<vector<int>> threeSum(vector<int>& nums) {
  vector<vector<int>> triplets;

  if (nums.size() < 3) {
    return triplets;
  }

  sort(nums.begin(), nums.end());

  for (int smallest = 0 ; smallest < nums.size() - 2 ; ++smallest) {
    // If smallest + x + y = 0 and smallest <= x <= y,
    // then smallest <= 0 (smallest = 0 when x = y = 0).
    if (nums[smallest] > 0) {
      break;
    }

    // Skip the duplicate smallest values.
    if (smallest > 0 && nums[smallest] == nums[smallest - 1]) {
      continue;
    }

    // Now we need to find (x, y) pais such that x + y = 0 - smallest
    // in a sorted array start from smallest + 1.
    // Thus, the problem is same as 167. Two Sum II : Input array is sorted.
    int target = 0 - nums[smallest];
    twoSum(nums, target, smallest + 1, triplets, nums[smallest]);
  }

  return triplets;
}

void twoSum(vector<int>& nums, int target, int start,
            vector<vector<int>>& tuples, int prefix) {
  assert(start > 0);
  assert(prefix <= nums[start]);

  // Do nothing if left elements are less than two.
  if (nums.size() - start < 2) {
    return;
  }

  int left = start;
  int right = nums.size() - 1;
  while (left < right) {
    int sum = nums[left] + nums[right];

    if (sum == target) {
      tuples.push_back({prefix, nums[left], nums[right]});
      ++left;
      --right;

      // Skip the duplicate left values.
      while (left < right && nums[left] == nums[left - 1]) {
        ++left;
      }

      // Skip the duplicate right values.
      while (left < right && nums[right] == nums[right + 1]) {
        --right;
      }

      continue;
    }

    sum < target ? ++left : --right;
  }
}

Improvement

// By leveraging the approach of LeetCode 167. Two Sum II - Input array is sorted:
// Find s + x + y = 0 => Find x + y = -s
// If s < x < y, then s <= 0. (s = 0 when x = y = 0)
//
// 1. Sort the array
// 2. Iterate all possible s in the array, and then search all (x, y) pairs
//
// Time Complexity:
//   - Sort the array: O(n log n)
//   - Iterate all possible s: O(n)
//     - Find (x, y) pairs in sorted array: O(n)
//   => Total: O(n log n) + O(n * n) = O(n^2)
vector<vector<int>> threeSum(vector<int>& nums) {
  vector<vector<int>> triplets;

  if (nums.size() < 3) {
    return triplets;
  }

  sort(nums.begin(), nums.end());

  int min = nums.front();
  int max = nums.back();

  // If min is larger than 0, or max is smaller than 0
  // or min is equal to 0 but max is larger than 0,
  // then there is no solution.
  if (min > 0 || max < 0 || (min == 0 && max > 0)) {
    return triplets;
  }

  for (int smallest = 0 ; smallest < nums.size() - 2 ; ++smallest) {
    // If smallest + x + y = 0 and smallest <= x <= y,
    // then smallest <= 0 (smallest = 0 when x = y = 0).
    if (nums[smallest] > 0) {
      break;
    }

    // Skip the duplicate smallest values.
    if (smallest > 0 && nums[smallest] == nums[smallest - 1]) {
      continue;
    }

    // Skip if smallest value is too small.
    if (nums[smallest] + 2 * max < 0) {
      continue;
    }

    // Now we need to find (x, y) pais such that x + y = 0 - smallest
    // in a sorted array start from smallest + 1.
    // Thus, the problem is same as 167. Two Sum II : Input array is sorted.
    int target = 0 - nums[smallest];
    twoSum(nums, target, smallest + 1, triplets, nums[smallest]);
  }

  return triplets;
}

void twoSum(vector<int>& nums, int target, int start,
            vector<vector<int>>& tuples, int prefix) {
  assert(start > 0);
  assert(prefix <= nums[start]);

  // Do nothing if left elements are less than two.
  if (nums.size() - start < 2) {
    return;
  }

  int left = start;
  int right = nums.size() - 1;
  while (left < right) {
    int sum = nums[left] + nums[right];

    if (sum == target) {
      tuples.push_back({prefix, nums[left], nums[right]});
      ++left;
      --right;

      // Skip the duplicate left values.
      while (left < right && nums[left] == nums[left - 1]) {
        ++left;
      }

      // Skip the duplicate right values.
      while (left < right && nums[right] == nums[right + 1]) {
        --right;
      }

      continue;
    }

    sum < target ? ++left : --right;
  }
}

or

vector<vector<int>> threeSum(vector<int>& nums) {
  vector<vector<int>> triplets;

  if (nums.size() < 3) {
    return triplets;
  }

  sort(nums.begin(), nums.end());

  int min = nums.front();
  int max = nums.back();

  // If min is larger than 0, or max is smaller than 0
  // or min is equal to 0 but max is larger than 0,
  // then there is no solution.
  if (min > 0 || max < 0 || (min == 0 && max > 0)) {
    return triplets;
  }

  for (int left = 0 ; left < nums.size() - 2 ; ++left) {
    // If left + middle + right = 0 and left <= middle <= righty,
    // then left <= 0 (left = 0 when middle = right = 0).
    if (nums[left] > 0) {
      break;
    }

    // Skip the duplicate left values.
    if (left > 0 && nums[left] == nums[left - 1]) {
      continue;
    }

    // Skip if left value is too small.
    if (nums[left] + 2 * max < 0) {
      continue;
    }

    // Now we need to find (middle, right) pais
    // such that middle + right = 0 - left
    // in a sorted array start from left + 1.
    // Thus, the problem is same as 167. Two Sum II : Input array is sorted.
    int target = 0 - nums[left];
    int middle = left + 1;
    int right = nums.size() - 1;
    while (middle < right) {
      int sum = nums[middle] + nums[right];

      if (sum == target) {
        triplets.push_back({nums[left], nums[middle], nums[right]});
        ++middle;
        --right;

        // Skip the duplicate middle values.
        while (middle < right && nums[middle] == nums[middle - 1]) {
          ++middle;
        }

        // Skip the duplicate right values.
        while (middle < right && nums[right] == nums[right + 1]) {
          --right;
        }

        continue;
      }

      sum < target ? ++middle : --right;
    }
  }

  return triplets;
}