3Sum

You are given a list of integers called nums, and your task is to find all unique combinations of three numbers in the list that add up to 0. These combinations are referred to as “triplets.” You must return these triplets without any duplicates.

How to Approach the Problem

Sorting: First, sort the numbers in the list nums. Sorting will help to find the elements more efficiently and handle duplicates.
Iterating Through the List: Iterate through the sorted list and consider each number as the potential first element of the triplet.
Two Pointers: For each chosen number, use two pointers approach on the remaining part of the list. One pointer starts from the immediate right of the chosen number, and the other starts from the end of the list.
Finding Triplets: Move the two pointers towards each other and find the combinations that add up to the negative of the chosen number (since the triplet must sum up to 0).
Handling Duplicates: To avoid duplicates, if the chosen number is the same as the previous chosen number, skip it. Also, if the pointers find numbers that are the same as the previous ones, skip them.
Collecting Results: Add the found unique triplets to the result list.

Example

Using the example nums = [-1,0,1,2,-1,-4], the sorted list is [-4, -1, -1, 0, 1, 2].

First, choose -4, then use two pointers on [-1, -1, 0, 1, 2] to find the combination that sums up to 4. There’s no such combination, so move on.
Next, choose the first -1, then use two pointers on [-1, 0, 1, 2] to find the combination that sums up to 1. You’ll find [-1, 0, 1] and [-1, -1, 2].
Continue this process for the remaining elements.

Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = []
        for i in range(len(nums) - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            left, right = i + 1, len(nums) - 1
            while left < right:
                total = nums[i] + nums[left] + nums[right]
                if total == 0:
                    result.append([nums[i], nums[left], nums[right]])
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    left += 1
                    right -= 1
                elif total < 0:
                    left += 1
                else:
                    right -= 1
        return result

This code leverages the sorted nature of the list and two pointers technique to efficiently find the unique triplets that sum up to 0.

Identifying Problem Isomorphism

“3Sum” requires you to find all unique triplets in the array which gives the sum of zero.

An isomorphic problem to this is “Two Sum”. This problem asks you to find a pair of numbers that add up to a target sum.

The isomorphism is in the concept of finding numbers in an array that add up to a specific value. Both require a technique to navigate the array and select pairs or triplets that satisfy the condition.

“Two Sum” problem is simpler. Because it deals with pairs instead of triplets, reducing the potential combinations to check. “3Sum” problem builds upon the logic of “Two Sum” by adding an extra number to the combinations, increasing its complexity.

Q&A

What are the reasons for making these mistakes in the given code?

Problem Classification

This problem can be classified as follows:

Combinatorics: The problem involves finding all unique triplets, which indicates a combinatorial nature. Combinatorics is the study of counting, arrangement, and combination of objects.
Search Problem: The problem asks to search the entire array for certain combinations that sum to zero, suggesting an exhaustive search or enumeration strategy may be required.
Numeric Summation: The problem involves the computation of sums and comparison of these sums to a specific target value (zero), indicating arithmetic operations as part of the problem-solving process.
Duplicate Handling: The problem statement mentions finding unique triplets, which means special attention needs to be paid to handle potential duplicates in the solution set.

This classification provides an understanding of the types of concepts and strategies that may be relevant in solving this problem.

Visual Model of the Problem

The 3-sum problem is as follows: Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

To visualize the 3-sum problem, consider using a number line.

Here’s an example:

Suppose we have the array: nums = [-4, -1, 0, 2, 3]

First, sort the array to make it easier to traverse and to avoid duplicates. Your array would now look like: [-4, -1, 0, 2, 3]

Now, we can visualize the problem using a number line:

-4   -1   0    2    3
 |    |   |    |    |

To find a set of numbers that sum to zero, we start by fixing the first number, in this case -4. Then we create two pointers, one at the beginning of the array just after -4 (pointer 1 at -1) and one at the end of the array (pointer 2 at 3).

-4   -1   0    2    3
 |    |   |    |    |
 |<---+---|----+---->|

We sum the numbers at the positions of the pointers with the fixed number. If the sum is zero, we have found a triplet, if the sum is less than zero we move pointer 1 to the right (increase), if the sum is more than zero we move pointer 2 to the left (decrease).

Continue this process, adjusting the pointers based on the sum and moving to the next fixed number when the pointers meet. Make sure to avoid duplicates by skipping over the same numbers.

This visualization helps us understand how we are essentially shrinking our problem space (the area between the pointers) to find potential triplets, and how sorting the array allows us to effectively move our pointers to get closer to the target sum of zero.

Language Agnostic Coding Drills

Drill 1 - Understanding List Comprehensions and Conditional Statements:

Concept: Understand list comprehensions in Python, including the use of conditionals. Task: Given a list of integers, create separate lists for positive and negative numbers.

Drill 2 - Understanding Sets:

Concept: Understand the concept of a set in Python and how it differs from a list. Task: Given a list of integers, create a set from the list. Test membership of an element in the set.

Drill 3 - Combining Lists and Sets:

Concept: Understand the use of sets for membership tests in Python. Task: Given lists of positive and negative numbers, create sets from these lists. Test membership of an element in the sets.

Drill 4 - Pairing Elements:

Concept: Understand how to iterate over pairs of elements in a list. Task: Given a list of integers, print all unique pairs of integers.

Drill 5 - Tuple and Sorting:

Concept: Understand the concept of a tuple and the use of sorted() function in Python. Task: Given a list of integers, create a sorted tuple from the list.

Drill 6 - Putting it all together:

Concept: Understand how to combine all these concepts to solve the 3Sum problem. Task: Implement the complete 3Sum problem.

The tasks could be ordered in terms of complexity as follows:

Understanding List Comprehensions and Conditional Statements
Understanding Sets
Combining Lists and Sets
Pairing Elements
Tuple and Sorting
Putting it all together

Once these concepts are understood individually, the learner will be able to piece them together to solve the entire problem.

Targeted Drills in Python

Drill 1 - Understanding List Comprehensions and Conditional Statements:

Task: Given a list of integers, create separate lists for positive and negative numbers.

1
2
3
4
5
nums = [3, -1, 0, 2, -2]
positives = [num for num in nums if num > 0]
negatives = [num for num in nums if num < 0]
print(positives)  # Expected: [3, 2]
print(negatives)  # Expected: [-1, -2]

Drill 2 - Understanding Sets:

Task: Given a list of integers, create a set from the list. Test membership of an element in the set.

1
2
3
4
nums = [3, -1, 0, 2, -2]
num_set = set(nums)
print(3 in num_set)  # Expected: True
print(5 in num_set)  # Expected: False

Drill 3 - Combining Lists and Sets:

Task: Given lists of positive and negative numbers, create sets from these lists. Test membership of an element in the sets.

1
2
3
4
5
6
positives = [3, 2]
negatives = [-1, -2]
positive_set = set(positives)
negative_set = set(negatives)
print(3 in positive_set)  # Expected: True
print(-3 in negative_set)  # Expected: False

Drill 4 - Pairing Elements:

Task: Given a list of integers, print all unique pairs of integers.

1
2
3
4
nums = [3, -1, 0, 2, -2]
for i in range(len(nums)):
    for j in range(i + 1, len(nums)):
        print((nums[i], nums[j]))

Drill 5 - Tuple and Sorting:

Task: Given a list of integers, create a sorted tuple from the list.

1
2
3
4
5
nums = [3, -1, 0, 2, -2]
print(nums)
print(sorted(nums))
sorted_tuple = tuple(sorted(nums))
print(sorted_tuple)

Drill 6 - Putting it all together:

Task: Implement the complete 3Sum problem.

This task would involve putting all the concepts learned in the previous drills together to solve the problem. Given that it’s a complex problem, this might require some additional learning and practice.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def threeSum(self, nums: List[int]) -> List[List[int]]:
	res = set()

	n, p, z = [], [], []
	for num in nums:
		if num > 0:
			p.append(num)
		elif num < 0: 
			n.append(num)
		else:
			z.append(num)

	N, P = set(n), set(p)

	if z:
		for num in P:
			if -1*num in N:
				res.add((-1*num, 0, num))

	if len(z) >= 3:
		res.add((0,0,0))

	for i in range(len(n)):
		for j in range(i+1,len(n)):
			target = -1*(n[i]+n[j])
			if target in P:
				res.add(tuple(sorted([n[i],n[j],target])))

	for i in range(len(p)):
		for j in range(i+1,len(p)):
			target = -1*(p[i]+p[j])
			if target in N:
				res.add(tuple(sorted([p[i],p[j],target])))

	return res

Python Basics

Tuple

A tuple in Python is an ordered, immutable sequence of elements. Each element inside a tuple can be of any data type (int, float, list, string, etc.) and can be accessed via its index.

Here is an example of a tuple:

1
my_tuple = (1, "Hello", 3.4)

In this tuple, 1 is an integer, "Hello" is a string, and 3.4 is a floating-point number.

You can access elements of a tuple in the same way as you access elements of a list:

1
2
3
print(my_tuple[0])  # Outputs: 1
print(my_tuple[1])  # Outputs: "Hello"
print(my_tuple[2])  # Outputs: 3.4

One key characteristic of tuples in Python is that they are immutable, meaning you cannot change their elements after they are created. For example, trying to reassign a value at a certain index will raise an error:

1
my_tuple[1] = "World"  # Raises TypeError: 'tuple' object does not support item assignment

Tuples are often used in situations where a statement or a user-defined function can safely assume that the collection of values (i.e., the tuple of values used) will not change.

Parallel Assignment

Parallel assignment is a feature in Python that allows you to assign values to several variables at once in a single line of code.

This can make your code cleaner and more readable, and it can also be used to swap the values of variables without needing a temporary variable.

Here’s an example of parallel assignment:

1
a, b, c = 1, 2, 3

In this case, a will be assigned the value 1, b will be assigned the value 2, and c will be assigned the value 3.

Parallel assignment can also be used with data structures that are iterable, such as lists or tuples:

1
2
my_list = [1, 2, 3]
a, b, c = my_list  # a is 1, b is 2, c is 3

And here’s an example of how you can use parallel assignment to swap the values of two variables:

1
2
a, b = 1, 2
a, b = b, a  # a is now 2, b is now 1

In the above example, a is assigned the value of b, and b is assigned the value of a, effectively swapping their values. Without parallel assignment, you would need a third, temporary variable to hold one of the values during the swap.

Destructuring in JavasScript

Is it the same concept as destructuring in JavaScript?

Yes, parallel assignment in Python is similar to the concept of destructuring in JavaScript.

Both parallel assignment in Python and destructuring in JavaScript allow you to assign values from arrays or properties from objects to new variables in a single statement.

Here’s a comparison of parallel assignment in Python and destructuring in JavaScript:

Python:

1
2
3
4
5
# Parallel Assignment
x, y, z = [1, 2, 3]
print(x)  # Output: 1
print(y)  # Output: 2
print(z)  # Output: 3

JavaScript:

1
2
3
4
5
// Destructuring Assignment
let [x, y, z] = [1, 2, 3];
console.log(x);  // Output: 1
console.log(y);  // Output: 2
console.log(z);  // Output: 3

In both cases, x, y, and z are being assigned the values 1, 2, and 3, respectively, in a single line of code. So yes, while the terminologies are different, the underlying concept is quite similar.

Complement

The “complement” refers to a number that, when added to the sum of the pair of negative numbers, results in zero. It’s essentially the positive equivalent of the sum of the two negative numbers.

For example, if you have a pair of negative numbers (-3, -1), their sum is -4. The complement of this sum is the number 4 because -4 (the sum of the pair) + 4 (the complement) equals zero. So, the statement is asking to check if this positive complement (4 in this case) exists in the set of positive numbers.

To make it more general, if you have a pair of negative numbers (a, b) where both a and b are negative, the complement is the number - (a + b), which is a positive number.

My Notes

title: Three Sum tags: nested-for-loops nested-triple-loop nested-double-loop check-triples check-pairs

Write a program Three Sum which counts the number of triples in an array of N integers that sum to 0.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
def three_sum(a)
  n = a.size
  count = 0
  
  for i in (0..n-3)
    for j in (i+1..n-2)
      for k in (j+1..n-1)
        if a[i] + a[j] + a[k] == 0
          count += 1
        end
      end
    end
  end
  
  count
end

a = [-1, 0, 1, 2, -1, -4]
p three_sum(a)

The time complexity of this program is O(N3). The space complexity is O(1). The result can return the triplets that sum to 0.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
def three_sum(a)
  n = a.size
  result = []
  
  for i in (0..n-3)
    for j in (i+1..n-2)
      for k in (j+1..n-1)
        if a[i] + a[j] + a[k] == 0
          result << [a[i], a[j], a[k]]
        end
      end
    end
  end
  
  result
end

a = [-1, 0, 1, 2, -1, -4]
p three_sum(a)

The problem can be generalized by specifying the required sum as a parameter. Sorting the array first can reduce the overall time complexity. Sorting takes O(n log n) time.

Then iterate over each pair in the array in a nested loop and calculate the remaining sum (sum - (a + b)). Binary search is used to find the remaining sum in the array. If we find it, the three numbers in the solution are the pair (a, b) and (sum - (a+b)).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
def find_fast(a, key)
  low = 0
  high = a.length - 1

  while low <= high
    mid = low + ((high - low) / 2).floor

    if a[mid] == key
      return mid
    end
    if key < a[mid]
      high = mid - 1
    else
      low = mid + 1
    end
  end
  
  return -1
end

def find_sum_of_three(a, required_sum)
  a.sort!

  for i in (0..n-3)
    for j in (i+1..n-2)
      # Looking for required_sum = a[i] + a[j] + a[k]
      remaining_sum = required_sum - a[i] - a[j]
      k = find_fast(a, remaining_sum)

      if (k > 0 and k != i and k != j)
        return true
      end
    end
  end
  
  return false
end

The time complexity of this solution is O(n log n) + O(N2). The space complexity is O(1).

The third way to solve this problem has O(N2) time complexity.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
def find_sum_of_two(a, val, start_index)
  i = start_index
  j = a.length - 1
  
  while i < j
    sum = a[i] + a[j]

    if sum == val
      return true
    end

    if sum < val
      i += 1
    else
      j -= 1
    end
  end
  
  return false
end

def find_sum_of_three(a, required_sum)
  a.sort!

  for i in (0..a.length-3)
    remaining_sum = required_sum - arr[i]
    
    if find_sum_of_two(a, remaining_sum, i + 1)
      return true
    end
  end
  
  return false
end

arr = [3, 7, 1, 2, 8, 4, 5]
puts "Original Array: #{arr}"
puts "Sum 20 exists #{find_sum_of_three(arr, 20)}" 
puts "Sum 10 exists #{find_sum_of_three(arr, 10)}"
puts "Sum 21 exists #{find_sum_of_three(arr, 21)}"

3Sum

How to Approach the Problem

Example

Implementation

Identifying Problem Isomorphism

Q&A

Similar Problems

Problem Classification

Visual Model of the Problem

Language Agnostic Coding Drills

Drill 1 - Understanding List Comprehensions and Conditional Statements:

Drill 2 - Understanding Sets:

Drill 3 - Combining Lists and Sets:

Drill 4 - Pairing Elements:

Drill 5 - Tuple and Sorting:

Drill 6 - Putting it all together:

Targeted Drills in Python

Drill 1 - Understanding List Comprehensions and Conditional Statements:

Drill 2 - Understanding Sets:

Drill 3 - Combining Lists and Sets:

Drill 4 - Pairing Elements:

Drill 5 - Tuple and Sorting:

Drill 6 - Putting it all together:

Python Basics

Tuple

Parallel Assignment

Destructuring in JavasScript

Complement

My Notes