LeetCode 15 - 3Sum

Question:

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]

Output: [[-1,-1,2],[-1,0,1]]

Explanation:

nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.

nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.

nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.

The distinct triplets are [-1,0,1] and [-1,-1,2].

Notice that the order of the output and the order of the triplets does not matter.

Example 2:

Input: nums = [0,1,1]

Output: []

Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0]

Output: [[0,0,0]]

Explanation: The only possible triplet sums up to 0.

Answer:

The problem asks to find all unique triplets in the array that sum up to zero. One way to approach the problem is to sort the array and use two-pointer approach.

Approach:

First, sort the input array in non-decreasing order.
Iterate through the array with a pointer "i" from 0 to n-2, where n is the size of the array.
For each "i", initialize two pointers "lo" and "hi", where "lo" starts at i+1 and "hi" starts at n-1.
Calculate the sum of elements at i, lo, and hi. If the sum is equal to zero, add the triplet to the result vector.
If the sum is less than zero, increment "lo" to move towards higher values. If the sum is greater than zero, decrement "hi" to move towards lower values.
To avoid duplicates, if a value has already been considered, skip it in the future iterations.
Continue the above process until all possible triplets are considered.

Time complexity:

The time complexity of this approach is O(n^2), where n is the size of the input array. The sorting operation takes O(nlogn) time, and the nested while loop takes O(n^2) time in the worst case. Therefore, the overall time complexity is O(nlogn + n^2) = O(n^2).

Space complexity:

The space complexity is O(1), as we are not using any extra space except the output vector.

Code:

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        nums.sort()
        
        for i in range(len(nums) - 2):
            if i == 0 or nums[i] != nums[i-1]:
                lo, hi, sum = i+1, len(nums)-1, 0-nums[i]
                while lo < hi:
                    if nums[lo] + nums[hi] == sum:
                        res.append([nums[i], nums[lo], nums[hi]])
                        while lo < hi and nums[lo] == nums[lo+1]: lo+=1
                        while lo < hi and nums[hi] == nums[hi-1]: hi-=1
                        lo+=1
                        hi-=1
                    elif nums[lo] + nums[hi] < sum:
                        lo+=1
                    else:
                        hi-=1
        
        return res