Skip to main content

Leetcode 15: 3Sum


1. Problem Statement (Simple Explanation):


You are given an integer array nums.

You must find all unique triplets [nums[i], nums[j], nums[k]] such that:

  • i, j, k are distinct indices

  • nums[i] + nums[j] + nums[k] == 0

  • No duplicate triplets in the result (triplets with same values in any order count as the same).

The order of triplets in the result and the order inside each triplet does not matter.


2. Examples:


Example 1:

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

Output: [[-1,-1,2], [-1,0,1]]

Possible zero-sum triplets (using indices):

  • (-1) + 0 + 1 = 0

  • (-1) + (-1) + 2 = 0

After removing duplicates (same values in different index combos) we keep:

  • [-1,-1,2]

  • [-1, 0, 1]


Example 2:

Input: nums = [0,1,1]

Output: []

No three numbers sum to 0.


Example 3:

Input: nums = [0,0,0]

Output: [[0,0,0]]

Only one triplet, 0 + 0 + 0 = 0.


3. Approach 1 – Brute Force (O(n³), Not Practical):


Intuition:


  • Check all possible triplets (i, j, k) with i < j < k.

  • If sum is 0, add to a set to avoid duplicates.

This is too slow for n up to 3000:

  • Time: O(n3) about 2.7x109 combinations in worst case.

We only use this for explanation, not as final solution.


4. Approach 2 – Sorting + Two Pointers (Optimal, O(n²)):


This is the standard solution and should be your main explanation.


Key Ideas:


  1. Sort the array nums first.

  2. Fix one element nums[i] as the first element of the triplet.

  3. For each fixed i, find pairs (left, right) such that: 

    • nums[i] + nums[left] + nums[right] = 0

    • This becomes a 2Sum problem on the subarray (i+1 .. end) with target: 

target = -nums[i]

  • We can solve 2Sum in a sorted array using two pointers:

    1. left = i + 1

    2. right = n - 1

  • Move pointers based on comparison with target.

  1. To avoid duplicate triplets:

    • After sorting, skip duplicate values of nums[i].

    • After finding a valid triplet, skip duplicates for nums[left] and nums[right].


Algorithm (Step-by-Step):


  1. Sort nums in non-decreasing order.

  2. Initialize result as empty list.

  3. Loop i from 0 to n - 3:

    • If i > 0 and nums[i] == nums[i - 1], skip this i to avoid duplicate triplets starting with the same number.

    • Set:

      • left = i + 1

      • right = n - 1

    • While left < right:

      • sum = nums[i] + nums[left] + nums[right]

      • If sum == 0:

        • Add triplet [nums[i], nums[left], nums[right]] to result.

        • Move left forward while skipping duplicates of nums[left].

        • Move right backward while skipping duplicates of nums[right].

        • Then move both pointers: left++, right--.

      • Else if sum < 0:

        • Need a bigger sum → move left++.

      • Else (sum > 0):

        • Need a smaller sum → move right--.

  4. Return result.


Pseudo-code (Sort + Two Pointers):



Complexity:


  • Sorting: O(n*logn)

  • Outer loop i from 0 to n and inner two-pointer scan is O(n) each: O(n2)

Overall:

  • Time: O(n2)

  • Space: O(1) extra (ignoring output; sort can be done in-place).

This is optimal for this problem.


5. Java code:



6. C code:



7. C++ code:



8. Python code:



9. JavaScript code:





Comments

Post a Comment

Popular posts from this blog

Leetcode 1: Two Sum

  Leetcode Link: https://leetcode.com/problems/two-sum/ 1. Problem Statement (Simple Explanation) You are given: An array of integers nums An integer target You need to  return the indices of two numbers in the array  such that: Conditions: Each input has  exactly one solution . You  cannot use the same element twice . You can return the answer in  any order . 2. Examples Example 1 Input:                                    nums = [2, 7, 11, 15], target = 9 Output:                                 [0, 1] Explanation:                     nums[0]+nums[1]=2+7=9              So we return [0, 1]. Example 2 Input:           ...
Post a Comment
Read more

Leetcode 3: Longest Substring Without Repeating Characters

  Leetcode Link 1. Problem Statement (Simple Explanation) You are given a string s. You need to find the length of the longest substring of s that does not  contain any repeated characters. A substring is a contiguous sequence of characters in the string. You must return an integer length, not the substring itself. 2. Examples Example 1 Input: s = "abcabcbb" Output: 3 Explanation: Some substrings without repeating characters: "abc", "bca", "cab"The longest length is 3. Example 2 Input: s = "bbbbb" Output: 1 Explanation: All substrings that are valid are just "b". The longest length is 1. Example 3 Input:   s = "pwwkew" Output:   3 Explanation: Possible substrings without repetition: "pw", "wke", "kew". "wke" or "kew" have length 3. "pwke" is not valid because it’s not contiguous in the original string (p and k are separated by ww). Constraints...
Post a Comment
Read more

Leetcode 2: Add Two Numbers

Leetcode Link: https://leetcode.com/problems/add-two-numbers/ 1. Problem Statement (Simple Explanation) You are given  two non-empty linked lists , l1 and l2, that represent two non-negative integers. Each node contains a  single digit . The digits are stored in  reverse order  (i.e., the 1’s digit is at the head). You need to  add the two numbers  and return the  sum as a linked list , also in reverse order. You can assume: There are  no leading zeros , except when the number itself is 0. 2. Examples Example 1 Input:                l1 = [2,4,3]                l2 = [5,6,4]           Interpreting linked lists as numbers (reverse order): l1 represents 342 l2 represents 465 Output:                [7,0,8] Explanation:        ...
Post a Comment
Read more