Solution 1: Three-Pointer Approach

This problem assesses the your ability to work with arrays, implement a problem involving multiple indices, and find unique combinations that satisfy a given condition.

Below is a Python implementation of the three_sum function to find all unique triplets in the array that give the sum of zero:

from typing import List

def three_sum(nums: List[int]) -> List[List[int]]:
    """
    Find all unique triplets in the array that give the sum of zero.

    Parameters:
    - nums: List of integers.

    Returns:
    - List[List[int]]: List of unique triplets.
    """
    result = []
    nums.sort()  # Sort the array to efficiently handle duplicates

    for i in range(len(nums) - 2):
        # Skip duplicates to avoid duplicate triplets
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        target = -nums[i]
        left, right = i + 1, len(nums) - 1

        while left < right:
            current_sum = nums[left] + nums[right]

            if current_sum == target:
                # Found a triplet that sums to zero
                result.append([nums[i], nums[left], nums[right]])

                # Skip duplicates to find unique triplets
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1

                # Move pointers to explore other possible triplets
                left += 1
                right -= 1
            elif current_sum < target:
                # Adjust pointers based on the current sum
                left += 1
            else:
                right -= 1

    return result

# Example usage:
nums1 = [-1, 0, 1, 2, -1, -4]
result1 = three_sum(nums1)
print(result1)  # Output: [[-1, 0, 1], [-1, -1, 2]]

nums2 = [0, 0, 0, 0]
result2 = three_sum(nums2)
print(result2)  # Output: [[0, 0, 0]]

This solution uses a three-pointer approach to find unique triplets by iterating through the array and adjusting pointers based on the current sum.

Time Complexity:

The time complexity of the provided solution for the Three Sum problem is O(n^2), where n is the length of the input array nums. Let’s break down the key components contributing to this time complexity:

  1. Sorting the Array:
    • The solution starts by sorting the input array (nums.sort()). The time complexity of the sorting operation is O(n * log(n)), where n is the length of the array.
  2. Three-Pointer Approach:
    • After sorting, the solution uses a three-pointer approach to find unique triplets.
    • The outer loop (for i in range(len(nums) - 2)) iterates through each element of the array, and the inner while loop (while left < right) adjusts the left and right pointers based on the current sum.
    • In the worst case, the inner while loop can have a total of O(n) iterations because the left and right pointers traverse the entire array.
    • Therefore, the overall time complexity of the three-pointer approach is O(n^2).

Space Complexity:

The space complexity is O(1) since no additional space is used.

Solution 2: Three Nested Loops

While the three-pointer approach approach are commonly used for solving the Three Sum problem, you may prefer the simplicity of using a straightforward nested loop approach. This solution has a time complexity of O(n^3) and is less efficient than the three-pointer approach, but it is conceptually simpler:

from typing import List

def three_sum(nums: List[int]) -> List[List[int]]:
    result = []

    # Sort the array
    nums.sort()

    # Iterate through all possible triplets
    for i in range(len(nums) - 2):
        # Skip duplicates for the first element
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        for j in range(i + 1, len(nums) - 1):
            # Skip duplicates for the second element
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue

            for k in range(j + 1, len(nums)):
                # Skip duplicates for the third element
                if k > j + 1 and nums[k] == nums[k - 1]:
                    continue

                # Check if the triplet sums to zero
                if nums[i] + nums[j] + nums[k] == 0:
                    result.append([nums[i], nums[j], nums[k]])

    return result

# Example usage:
nums1 = [-1, 0, 1, 2, -1, -4]
result1 = three_sum(nums1)
print(result1)  # Output: [[-1, -1, 2], [-1, 0, 1]]

nums2 = [0, 0, 0, 0]
result2 = three_sum(nums2)
print(result2)  # Output: [[0, 0, 0]]

This solution involves three nested loops to iterate through all possible triplets in the array. While it is simpler conceptually, it may be less efficient for large input arrays due to its cubic time complexity. The three-pointer approach remains recommended for better performance.