Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i, j, and k are distinct indices, and nums[i] + nums[j] + nums[k] == 0. Important Constraint: The solution set must not contain duplicate triplets. Example: Input: nums = [-1, 0, 1, 2, -1, -4] Output: [-1, -1, 2], [-1, 0, 1] Explanation: (-1) + 0 + 1 = 0 (-1) + 2 + (-1) = 0 Notice [0, 1, -1] is the same triplet as [-1, 0, 1], so we only include it once.

Brainstorming

So the idea is we have to move greedily i.e we make sure we satisfy the first constraint that is the 3 numbers should add up to the target and the second constraint that we should avoid creating duplicate triplets.

The core strategy we have whenever we have to deal with removing duplicates is to always sort the array , unless and until there is some added constraints on sorting or if some issue may arise because of it.

Why sorting? it brings all the duplicate elements together

lets take the example in the problem [-1, 0, 1, 2, -1, -4] , sorted this would be [-4, -1,-1,0,1,2] if you notice -1 are grouped together hence while iterating over a for loop we can just skip an element if its similar to the previous element

This solves the duplicate triplets issue by skipping it, now coming to the original problem. We need to make sure 3 numbers in this sorted array if they sum up to target they should be appended to the list. The good thing is since its a sorted array all the elements are increasing order , we can use it to our advantage. A 2 pointer search space minimization technique can work here , with a 3rd pointer iterating over this whole array element by element, they will work together like this

1. For each element
   1. If its similar to the previous element just skip everything and move to the next element
   2. create a search space witth boundary starting from the next element of it all the way till the end
   3. caculate a current sum that is a total of element + left boundary element + right boundary element
   4. if its equal to target then add it as a triplet
   5. if its greater than target that means the right most element is big hence we should reduce the search space from right
   6. if its less than the target that means the left most element is too small hence we should reduce the search space from the left

nums = [1,2,5,3,9,4,3]

target = 9 

nums.sort()

result = []

for i in range(len(nums) -1): # we need to make sure that we don't get index out of bounds
	if nums[i] != nums[i+1]: # check and make sure the current element is not same as the next element
		left = i + 1
		right = len(nums) -1
		while left < right: # boundary condition
			current_sum = nums[i] + nums[left] + nums[right]
			if current_sum == target:
				result.append([nums[i], nums[left], nums[right]])
					while nums[i] != nums[i+1] and left < right:
						left = +1
			elif current_sum < target:
				left +=1
			else:
				right -=1
				 

This is perfectly fine lets try with some cases target = 9 [1,2,5,3,9,4,3]

sorted

nums = [1,2,3,3,4,5,9]

for i in range(nums): 1. i = 0 nums[0] = 1 1. check for duplicate 1 != 2 hence we can proceed 1. left 2 (nums[1]) right 9 (nums[5]) 1. left < 5 1. sum = 1 + 2 + 9 > 9 hence reduce from right, nums[4] (5) 1. sum = 1 + 2 + 5 < 9 hence reduce from left nums[2] (3) 2. sum = 1 + 3 + 5 == 9 add triplet 1. now we should move the left pointer but we have duplicate at nums[3] (3) hence we should add a check and skip it as well 2. skip nums[3] go to nums[4] (4) 3. sum = 1 + 4 + 5 > 9 hence reduce from right nums[3] 3 1. while breaks left (4) is not less than right(3) 2. i = 1 nums[1] = 2 3.

This is a great attempt, and you are thinking about all the right components: sorting, the outer loop, the two-pointer inner loop, and duplicate handling. This is exactly the thought process of a developer working through a complex problem.

Let’s debug your implementation together. It has the correct high-level structure, but there are a few logical bugs in the details, particularly around the duplicate checks.

Here is your code again for reference:

nums = [1,2,5,3,9,4,3]
target = 9 
nums.sort() # Becomes [1, 2, 3, 3, 4, 5, 9]
result = []

for i in range(len(nums) - 1):
  if nums[i] != nums[i+1]: # Bug 1: Duplicate check logic
    left = i + 1
    right = len(nums) - 1
    while left < right: 
      current_sum = nums[i] + nums[left] + nums[right]
      if current_sum == target:
          result.append([nums[i], nums[left], nums[right]])
          # Bug 2: Incorrect duplicate check for 'left'
          while nums[i] != nums[i+1] and left < right:
            left +=1
      elif current_sum < target:
          left +=1
      else:
          right -=1

Let’s break down the issues.

Bug #1: The Outer Loop Duplicate Check

Your Code: if nums[i] != nums[i+1]:

The Problem: This checks the current element against the next one. Let’s trace this with a relevant part of our sorted array: ..., 3, 3, 4, ...

• When i points to the first 3, nums[i] is 3 and nums[i+1] is also 3. Your condition 3 != 3 is false. This means your code will skip the first 3, which is wrong! We need to process the first occurrence of any number.
• When i points to the second 3, nums[i] is 3 and nums[i+1] is 4. Your condition 3 != 4 is true. Your code will now run the two-pointer logic for the second 3.

This is the opposite of what we want. We want to process the first 3 and skip the second 3.

The Fix (Hint): Instead of comparing nums[i] to the next element, you should compare it to the previous element. The rule should be: “If I am the same as the guy before me, then I’m a duplicate starter, so just skip me.” This ensures you only run the main logic for the first occurrence of each number.

• The check should look like: if i > 0 and nums[i] == nums[i-1]: continue

Bug #2: The Inner Loop Duplicate Check (after finding a match)

Your Code: while nums[i] != nums[i+1] and left < right: left += 1

The Problem: The condition here, nums[i] != nums[i+1], has nothing to do with the left pointer. We’ve found a valid triplet [nums[i], nums[left], nums[right]]. Now we need to skip any duplicates of nums[left] to avoid finding the same triplet again.

Let’s say nums = [-2, 0, 0, 2, 2] and our triplet is [-2, 0, 2].

• We found this with i=0, left=1, right=4. The triplet is [-2, 0, 2].
• We must now advance left. It becomes 2.
• The new nums[left] is also 0. If we don’t do anything special, our next check will be [-2, 0, 2], which is a duplicate triplet.

The Fix (Hint): After you find a match and increment left once, you need a new while loop that checks if the new nums[left] is the same as the previous value of left. The condition should be while left < right and nums[left] == nums[left - 1]:.

Bug #3: Loop Range

Your Code: for i in range(len(nums) - 1):

The Problem: We need to leave room for at least two other numbers for the left and right pointers. If i goes all the way to len(nums) - 2, then left will be len(nums) - 1 and right will be len(nums) - 1. The loop while left < right will not run. This is correct. But if i is len(nums) - 1, the code will crash.

• The Fix: The loop for i only needs to go up to len(nums) - 3, so the range should be range(len(nums) - 2).

Putting It All Together (Corrected Structure)

Here is how the logic looks with the fixes incorporated. This isn’t the final code, but the corrected pseudocode structure for you to implement.

nums = [1,2,5,3,9,4,3]
target = 9 
result = []
nums.sort()

for i in range(len(nums) -2):
	if nums[i] != nums[i-1] # we need to check with the previous value
		left = i +1
		right = len(nums) -1
		while i > 0 and left < right:
			curr_sum = nums[i] + nums[left] + nums[right]
			if curr_sum == target
				result.append([nums[i], nums[left], nums[right]])
				# increment left pointer so that we don't recomupute a new triplet
				left +=1
				while left < right and nums[left] == nums[left -1]:
					left +=1
			elif curr_sum < target:
				left +=1
			else:
				right -=1