Three Sum

Problem Statement

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that:

• i != j, i != k, and j != k
• nums[i] + nums[j] + nums[k] == 0

The solution set must not contain duplicate triplets.

Solve Here: 3Sum

Examples:

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

Edge Cases:

1. All positive or all negative numbers: If all numbers are positive or negative, there can’t be a triplet that sums to zero.
2. Multiple identical numbers: If there are multiple instances of the same number, care must be taken to avoid duplicate triplets in the output.

Solution Approach:

1. Two Pointers

• Description: First, sort the array, then iterate through each number and use two pointers (left and right) to find two other numbers that sum to zero. After finding a valid triplet, move both pointers inward while avoiding duplicates.
• Time Complexity: O(n²) – one loop to fix a number and a two-pointer loop to find the remaining two numbers
• Space Complexity: O(1) – only constant space aside from the input array and result

fun threeSum(nums: IntArray): List<List<Int>> {
    val result = mutableListOf<List<Int>>()
  
    nums.sort()
  
    for (i in nums.indices) {
        if (i > 0 && nums[i] == nums[i - 1]) continue
        var left = i + 1
        var right = nums.size - 1
  
        while (left < right) {
            when {
                nums[i] + nums[left] + nums[right] == 0 -> {
                    result.add(listOf(nums[i], nums[left], nums[right]))
                    left++
                    right--
                    while (left < right && nums[left] == nums[left - 1]) left++
                    while (left < right && nums[right] == nums[right + 1]) right--
                }
              
                nums[i] + nums[left] + nums[right] < 0 -> left++
              
                else -> right--
            }
        }
    }
  
    return result
}

Complexity Comparison:

Approach	Time Complexity	Space Complexity
Two Pointers	O(n²)	O(1)

Conclusion:

The Two Pointers approach is the efficient solution for this problem with a time complexity of O(n²). The sorting step simplifies the process of finding valid triplets and avoiding duplicates.