LeetCode #15: 3Sum

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

To solve this problem, we can use a combination of two-pointer technique and a hashmap. We first sort the input array in non-descending order, and then for each element in the array, we use two pointers to find the remaining two elements such that their sum equals to the negation of the current element. We can use a hashmap to store the previous element and avoid duplicates.

Steps to solve the problem in python3:

1. Create a function called “threeSum” that takes an array of integers nums as input.
2. Sort the input array in non-descending order using the sort() method.
3. Create an empty list called “result” to store the unique triplets that sum up to zero.
4. For each element in the array, use two pointers to find the remaining two elements such that their sum equals to the negation of the current element.
5. To avoid duplicates, use a hashmap to store the previous element.
6. If the three elements sum up to zero and are not in the “result” list, append them to the “result” list.
7. Return the “result” list.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = []
        for i in range(len(nums) - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            left, right = i + 1, len(nums) - 1
            while left < right:
                curr_sum = nums[i] + nums[left] + nums[right]
                if curr_sum == 0:
                    result.append([nums[i], nums[left], nums[right]])
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    left += 1
                    right -= 1
                elif curr_sum < 0:
                    left += 1
                else:
                    right -= 1
        return result

Time and Space Complexity:

The time complexity of this solution is O(n^2), where n is the length of the input array. This is because we have two nested loops and a hashmap lookup, each taking O(n) time.

The space complexity of this solution is O(n), as we are using a hashmap to store the previous element.