> For the complete documentation index, see [llms.txt](https://leetcode.realtemirov.uz/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://leetcode.realtemirov.uz/problems/15.-3sum.md).

# 15. 3Sum

🟧 Medium

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.

## Hint-1

> So, we essentially need to find three numbers x, y, and z such that they add up to the given value. If we fix one of the numbers say x, we are left with the two-sum problem at hand!

## Hint-2

> For the two-sum problem, if we fix one of the numbers, say x, we have to scan the entire array to find the next number y, which is value - x where value is the input parameter. Can we change our array somehow so that this search becomes faster?

## Hint-3

> The second train of thought for two-sum is, without changing the array, can we use additional space somehow? Like maybe a hash map to speed up the search?

## Constraints

* `3 <= nums.length <= 3000`
* `-10^5 <= nums[i] <= 10^5`

## Solution

My Solution

```go
func threeSum(nums []int) [][]int {
    sort.Ints(nums)
    res := [][]int{}

    for i, num := range nums {
        if i > 0 && num == nums[i-1] {
            continue
        }

        l,r := i+1, len(nums) - 1
        for l < r {
            threeSum := num + nums[l] + nums[r]
            if threeSum > 0 {
                r -=1
            } else if threeSum < 0 {
                l+=1
            } else {
                res = append(res, []int{num, nums[l], nums[r]})
                l+=1

                for nums[l] == nums[l-1] && l < r {
                    l+=1
                }
            }
        }
    }


    return res
}
```

## Optimal Solution

The optimal solution uses two key techniques:

1. Sorting for duplicate handling and efficient searching
2. Two-pointer technique for finding pairs that sum to target

Here's an optimized version with improved readability and performance:

```go
func threeSum(nums []int) [][]int {
    // Sort the array first for efficient duplicate handling
    sort.Ints(nums)
    result := make([][]int, 0)
    n := len(nums)
    
    // Fix the first number and use two pointers for the remaining sum
    for i := 0; i < n-2; i++ {
        // Skip duplicates for first number
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        
        // Early termination optimization
        if nums[i] > 0 {
            break // Since array is sorted, no three numbers can sum to 0
        }
        
        target := -nums[i]
        left := i + 1
        right := n - 1
        
        for left < right {
            currentSum := nums[left] + nums[right]
            
            if currentSum == target {
                result = append(result, []int{nums[i], nums[left], nums[right]})
                
                // Skip duplicates for second number
                for left < right && nums[left] == nums[left+1] {
                    left++
                }
                // Skip duplicates for third number
                for left < right && nums[right] == nums[right-1] {
                    right--
                }
                
                left++
                right--
            } else if currentSum < target {
                left++
            } else {
                right--
            }
        }
    }
    
    return result
}
```

### Approach Analysis

The solution employs three main techniques:

1. **Sorting**:
   * Makes duplicate handling efficient
   * Enables two-pointer technique
   * Allows for early termination
2. **Two-Pointer Technique**:
   * Uses sorted array property
   * Efficiently finds pairs summing to target
   * Reduces time complexity from O(n²) to O(n)
3. **Duplicate Handling**:
   * Skip duplicates for first number
   * Skip duplicates for second and third numbers
   * Ensures unique triplets

### Visualization of Both Approaches

```
Input array: [-1, 0, 1, 2, -1, -4]
After sorting: [-4, -1, -1, 0, 1, 2]

Step 1: First number = -4
[-4, -1, -1, 0, 1, 2]
 ^   L           R
Target sum = 4
Move L right as sum is too small

Step 2: First number = -1
[-4, -1, -1, 0, 1, 2]
     ^   L        R
Found triplet: [-1, -1, 2]

Step 3: Skip duplicate -1
[-4, -1, -1, 0, 1, 2]
         ^   L    R
Found triplet: [-1, 0, 1]

Final result: [[-1, -1, 2], [-1, 0, 1]]
```

### Complexity Analysis

**Time Complexity**:

* Sorting: O(n log n)
* Two pointers: O(n²)
* Overall: O(n²)

**Space Complexity**:

* Result array: O(k) where k is number of valid triplets
* Sorting space: O(log n) to O(n) depending on sort implementation
* Overall: O(k)

**Optimizations**:

* Early termination when first number > 0
* Skip duplicates to avoid redundant calculations
* Two-pointer technique instead of nested loops

### Why Solution Works

1. **Sorting Enables Efficiency**:
   * Makes duplicate detection simple
   * Allows two-pointer technique
   * Enables early termination
2. **Two-Pointer Logic**:
   * If sum too small, increase left pointer
   * If sum too large, decrease right pointer
   * Guarantees finding all valid pairs
3. **Duplicate Handling**:
   * Sorting puts duplicates adjacent
   * Skip duplicates for all three positions
   * Ensures unique triplets in result

### When to Use

This approach is ideal when:

1. Need to find all combinations summing to target
2. Duplicates need to be handled
3. Order of triplets doesn't matter
4. Input array can be modified

Common variations:

* 4Sum problem
* K-sum problem
* Two-pointer problems
* Combination sum problems

### Common Patterns & Applications

1. **Two-Pointer Pattern**:
   * Sorted array traversal
   * Meeting in middle
   * Opposite direction movement
2. **Sorting + Two Pointers**:
   * Finding combinations
   * Handling duplicates
   * Range-based problems
3. **Sum Problems**:
   * TwoSum variations
   * KSum problems
   * Target sum problems

### Interview Tips

1. **Key Discussion Points**:
   * Why sorting first?
   * How to handle duplicates?
   * Time/space complexity tradeoffs
   * Optimization techniques
2. **Common Follow-up Questions**:
   * How to handle 4Sum?
   * Can we do it without sorting?
   * How to optimize for specific input patterns?
   * How to handle negative targets?
3. **Edge Cases to Consider**:
   * Empty array
   * Array with < 3 elements
   * All zeros
   * All same numbers
   * No valid triplets
4. **Optimization Opportunities**:
   * Early termination
   * Duplicate skipping
   * Memory management
   * Input validation

![result](https://600345290-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FrSK2xH3txU3tYyDsT8mQ%2Fuploads%2Fgit-blob-1d5661bd4e4537ef27db1d0768eca4f923d43849%2F15.png?alt=media)

Leetcode: [link](https://leetcode.com/problems/3sum/description/)