Two PointersMediumO(n²) time · O(1) space

Triplet Sum to Zero

Mahabharata — The Three Debts of Karma — Balancing Past, Present, and Future

त्रयाणां योगसंसिद्धिः शून्ये स्थिते समाप्यते। ऋणं च धनं च मध्यं च मिलित्वा शान्तिमाप्नुयुः॥

*The union of three achieves completion when settled at zero. Debt, credit, and balance—when combined—attain peace.*

The Story

In the court of Yama, the Lord of Death and Dharma, souls were judged not merely on deeds but on karmic balance. Each soul arrived with a ledger—positive numbers for virtuous acts, negative for sins, and the eternal question: could three lifetimes be found that balanced to zero?

"The cosmic equilibrium requires neutrality," Yama explained to Chitragupta, his record-keeper. "For a soul to achieve moksha through the fast path, we must find three incarnations whose karmic scores sum exactly to zero. The negative cancels the positive."

Chitragupta unrolled a soul's ledger. The karmic scores across twelve incarnations: [-4, -2, -1, 0, 1, 2, 3, 5, 8, 10, 12, 15]

"Already sorted by karmic weight," Yama noted. "From deepest sin to highest virtue. Now find me all unique triplets that sum to zero."

A young assistant, eager to prove himself, suggested: "My Lord, I shall check every possible combination of three lifetimes! First + second + third, first + second + fourth..."

"That would take n-choose-3 comparisons," Chitragupta interrupted. "For a soul with many incarnations, we'd be here until the next kalpa. There must be a wiser method."

Yama stroked his chin. "The ledger is sorted. This is not coincidence—it is dharma's gift to the efficient seeker."

He picked up a golden stylus. "Watch. I will fix the first element and reduce the problem to finding two elements that sum to its negation."

Yama pointed to the first entry: -4. "If the first number is -4, I need two numbers that sum to +4. This is now a two-sum problem on the remaining array!"

He placed two fingers on the remaining array: one at -2 (the next element after -4) and one at 15 (the last element).

"Sum = -2 + 15 = 13. Too high. Move right finger left."

Right finger moved to 12. Sum = -2 + 12 = 10. Still too high.

The process continued until: -2 + 5 = 3? No. -1 + 5 = 4? Yes!

"Found: [-4, -1, 5] sums to zero," Yama declared. "But we're not done with -4 yet. After finding a valid pair, we skip duplicates and continue."

The search continued with -4 fixed, finding all pairs that sum to 4. Then the outer loop moved to the next unique starting element: -2.

"If -4 has been fully explored, why check -2 now?" the assistant asked.

"Because triplets starting with -2 are different from those starting with -4," Yama explained. "We fix -2, seek pairs summing to +2. Different search, potentially different results."

For each fixed element, the two-pointer search on the remaining elements was O(n). With n elements to fix, total time was O(n²).

"But what about duplicates?" Chitragupta asked. "This soul lived two incarnations with karma score 0."

"We skip duplicate starting points," Yama said. "After fixing 0 and exploring all its triplets, we don't fix the second 0—it would only produce duplicate triplets. Similarly, after finding a valid pair, we skip to the next unique values on both pointers."

The final list of balancing triplets emerged: - [-4, -1, 5] - [-4, 1, 3] - [-2, 0, 2] - [-2, -1, 3] - [-1, 0, 1]

"Five paths to karmic balance," Yama pronounced. "Each unique, each valid. This soul has options for its liberation journey."

The assistant marveled. "O(n²) instead of O(n³)! And you found all unique triplets without a hash set!"

"The sorting does the heavy lifting," Yama smiled. "When elements are ordered, duplicates cluster together, and two pointers can dance through the remaining array efficiently. Never forget: for triplet problems, fix one element and reduce to pair problems. For pair problems in sorted arrays, use two pointers from the extremes."

This is the Two Pointer technique for finding triplets that sum to zero.

The Assistant's First Instinct

Check every possible triplet using three nested loops. O(n³) time, and additional complexity to track unique triplets.

java

public List<List<Integer>> threeSumBruteForce(int[] nums) {
    Set<List<Integer>> resultSet = new HashSet<>();
    int n = nums.length;
    
    // Check every triplet
    for (int i = 0; i < n - 2; i++) {
        for (int j = i + 1; j < n - 1; j++) {
            for (int k = j + 1; k < n; k++) {
                if (nums[i] + nums[j] + nums[k] == 0) {
                    List<Integer> triplet = Arrays.asList(
                        nums[i], nums[j], nums[k]
                    );
                    Collections.sort(triplet);  // For uniqueness
                    resultSet.add(triplet);
                }
            }
        }
    }
    
    return new ArrayList<>(resultSet);
}

Yama's Wisdom

Yama's insight: sort the array first. Then for each element `nums[i]`, use two pointers on `nums[i+1..n-1]` to find pairs summing to `-nums[i]`. Skip duplicates at each level to avoid duplicate triplets. The outer loop fixes one element. The inner two-pointer search finds all valid pairs. Duplicate skipping ensures each triplet is reported exactly once.

java

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(nums);  // Essential for two pointers + dedup
    
    for (int i = 0; i < nums.length - 2; i++) {
        // Skip duplicate starting elements
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        
        // Early termination: if smallest is positive, no sum can be zero
        if (nums[i] > 0) break;
        
        int target = -nums[i];  // We need pairs summing to this
        int left = i + 1;
        int right = nums.length - 1;
        
        while (left < right) {
            int sum = nums[left] + nums[right];
            
            if (sum == target) {
                result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                
                // Skip duplicate left values
                while (left < right && nums[left] == nums[left + 1]) left++;
                // Skip duplicate right values
                while (left < right && nums[right] == nums[right - 1]) right--;
                
                left++;
                right--;
            } else if (sum < target) {
                left++;   // Need larger sum
            } else {
                right--;  // Need smaller sum
            }
        }
    }
    
    return result;
}

// Test with karmic ledger
public static void main(String[] args) {
    int[] karma = {-1, 0, 1, 2, -1, -4};
    List<List<Integer>> triplets = new Solution().threeSum(karma);
    System.out.println(triplets);
    // Output: [[-1, -1, 2], [-1, 0, 1]]
}

Step-by-Step Walkthrough

Array: [-1, 0, 1, 2, -1, -4]
Sorted: [-4, -1, -1, 0, 1, 2]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
i=0: Fix nums[0]=-4, target=4
     [-4, -1, -1, 0, 1, 2]
      i    L            R
     
     L=1, R=5: -1+2=1 < 4 → L++
     L=2, R=5: -1+2=1 < 4 → L++
     L=3, R=5: 0+2=2 < 4 → L++
     L=4, R=5: 1+2=3 < 4 → L++
     L=5, R=5: L >= R, done with i=0
     
     No triplets starting with -4

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
i=1: Fix nums[1]=-1, target=1
     [-4, -1, -1, 0, 1, 2]
           i    L      R
     
     L=2, R=5: -1+2=1 == 1 ✅
     Found: [-1, -1, 2]
     Skip duplicates: L moves to 3, R moves to 4
     
     L=3, R=4: 0+1=1 == 1 ✅
     Found: [-1, 0, 1]
     L++, R-- → L=4, R=3 → done

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
i=2: nums[2]=-1 == nums[1]=-1 (duplicate)
     SKIP to avoid duplicate triplets

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
i=3: Fix nums[3]=0, target=0
     [-4, -1, -1, 0, 1, 2]
                  i  L  R
     
     L=4, R=5: 1+2=3 > 0 → R--
     L=4, R=4: L >= R, done
     
     No triplets starting with 0

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
i=4: nums[4]=1 > 0, early termination
     (Smallest remaining is positive, sum can't be 0)

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
✅ Result: [[-1, -1, 2], [-1, 0, 1]]

Deep Insight

**Why does this work?**

1. **Sorting enables two-pointer**: In a sorted array, if pair sum is too small, we can only increase it by moving the left pointer right. If too large, move right pointer left.

2. **Fixing one element reduces to 2Sum**: A 3Sum problem becomes n instances of 2Sum on progressively smaller arrays.

3. **Duplicate skipping ensures uniqueness**: By sorting, duplicates cluster. Skipping ensures: - No duplicate starting elements (outer loop skip) - No duplicate pairs for the same starting element (inner skip after finding a match)

**The correctness of duplicate skipping:** If `nums[i] == nums[i-1]`, any triplet starting with `nums[i]` was already found when we processed `nums[i-1]`, because the remaining elements `nums[i+1..n-1]` are a subset of `nums[i-1+1..n-1]`.

**Edge cases:** - Less than 3 elements: Return empty - All positives or all negatives: No zero sum possible - Multiple zeros: [0,0,0] is valid if ≥3 zeros exist

Complexity Analysis

Approach	Time	Space	Note
Brute Force	O(n³)	O(k) for result + O(k) for dedup set	Three nested loops, hash set for uniqueness
Optimal	O(n²)	O(1) excluding output	Sorting O(n log n) + n × O(n) two-pointer searches

Pattern Recognition

✅ Find triplets with a specific sum property
✅ Need all unique combinations (no duplicates)
✅ Array can be sorted without losing meaning
✅ "Three numbers" + "sum equals" pattern

**LeetCode Trigger Phrases:**
→ "find all unique triplets... sum is zero"
→ "three integers... add up to target"
→ "triplets (a, b, c)... a + b + c = 0"

Bhagavad Gita 16.21

त्रिविधं नरकस्येदं द्वारं नाशनमात्मनः। कामः क्रोधस्तथा लोभस्तस्मादेतत्त्रयं त्यजेत्॥

Threefold is the gate of this hell, destructive of the self: lust, anger, and greed. Therefore, one should abandon these three.

Connection: Just as three destructive forces must be identified and balanced to achieve liberation, the algorithm seeks three numbers that balance to zero. The negative karma (debts), the positive karma (credits), and the search for equilibrium—when these three meet at zero, the soul finds peace. The two-pointer method systematically finds these balancing triplets, just as the seeker must systematically address each of the three gates to hell.