Given an array nums of n integers, find all unique triplets in the array which gives the sum of zero.

Function Signature:

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.
    """
    # Your code here

Example:

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

# Input: nums = [0, 0, 0, 0]
# Output: [[0, 0, 0]]

Note:

  • The solution set must not contain duplicate triplets.

Instructions:

  • Write the three_sum function to solve the problem.
  • Implement your solution in Python.
  • Provide clear comments in your code.
  • Discuss the time and space complexity of your solution.

As always, we’ll share our solution to this problem tomorrow. Stay tuned 😊