3sum

Problem Statement:

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:

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.

Intuition:

We need triplets, use sort + two pointer.
It is the optimal option.

1. Sort the array.
2. Iterate over the array and the current element would be the first element (ith) of the triplet.
3. Use two pointer, on the remaining array (i+1, r)

Keep Good during interview

1. Avoid duplication of triplets while iterating
   • While selecting first element (ith), check for duplicacy as the array is sorted already (II)
   • When a triplet is found, land r would be incremented and decremented respectively. there only check for duplicacy (III)
2. If the first element is more than 0 that is positive, then no other triplets can be found (I)

NOTE: After moving l or r, skip duplicates by comparing with the element you just crossed.

Code:

My Solution (TC: O(n^2))

def solve(nums):
	nums.sort()
	ans = []
	for i in range(len(nums)):
		if nums[i] > 0:  # I
			break
		if i > 0 and nums[i-1] == nums[i]: # II
			continue
		l, r, target = i + 1, len(nums) - 1, -nums[i]
		while l < r:
			total = nums[l] + nums[r]
			if total == target:
				ans.append([nums[i], nums[l], nums[r]])
				l += 1
				r -= 1
				
				while l < r and nums[l-1] == nums[l]: # III
					l += 1
				while l < r and nums[r] == nums[r+1]: # III
					r -= 1
			
			elif total > target:
				r -= 1
			else:
				l += 1
		
	return ans  
				

#two-pointer