Leetcode - 15. 3Sum | Ammar Ahmed

Medium

Dec 22, 2025

#binary-search

#two-pointers

15. 3Sum

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.

3 <= nums.length <= 3000
-105 <= nums[i] <= 105

Constraints:

Notes

Intuition

Building on the two-pointer approach from Two Sum II, we can fix one number and use two pointers on the remaining sorted array to find pairs that sum to its negation. Sorting enables efficient duplicate skipping.

Implementation

Sort the array first. For each number nums[i], set up left and right pointers on the subarray to its right. If l + r equals the target (negation of nums[i]), we found a triplet. If the sum is too large, move right inward; if too small, move left outward. Continue searching even after finding a triplet.

Edge-cases

Duplicates require careful handling. Skip duplicate values of nums[i] at the outer loop level. After finding a triplet, advance both l and r past any duplicates to avoid adding the same triplet multiple times.

Time: O(n²) — sorting is O(n log n), nested iteration is O(n²)
Space: O(1) — excluding the output array

Complexity

Solution

from typing import List

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums = sorted(nums)
        print(f"nums = {nums}")
        i = 0
        ans = []
        # To have at least 3 elements
        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            
            target = nums[i] * -1
            l, r = i + 1, len(nums) - 1
            while l < r:
                potential = nums[l] + nums[r]
                if potential == target:
                    ans.append([nums[i], nums[l], nums[r]])
                    while l < r and nums[l] == nums[l + 1]:
                        l += 1
                    while l < r and nums[r] == nums[r - 1]:
                        r += 1
                    l += 1
                    r -= 1
                elif potential < target:
                    l += 1
                else:
                    r -= 1
        return ans
        



if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()