4Sum

You have to find all the unique quadruplets in the array that sum up to the given target. Here’s a step-by-step solution that you can follow:

Sort the Array: Sorting the array helps in efficiently finding the quadruplets.
Iterate Through the Array: Use nested loops to iterate through the array, keeping track of the first and second elements of the potential quadruplets.
Two Pointers: Use the two-pointer technique to find the other two elements that complete the quadruplet.
Avoid Duplicates: Since you need unique quadruplets, make sure to skip over duplicate numbers.

Here’s the code:

 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
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        n = len(nums)
        result = []

        for i in range(n - 3):
            if i > 0 and nums[i] == nums[i - 1]: # Avoid duplicates for the first element
                continue
            for j in range(i + 1, n - 2):
                if j > i + 1 and nums[j] == nums[j - 1]: # Avoid duplicates for the second element
                    continue
                left, right = j + 1, n - 1
                while left < right:
                    s = nums[i] + nums[j] + nums[left] + nums[right]
                    if s == target:
                        result.append([nums[i], nums[j], nums[left], nums[right]])
                        while left < right and nums[left] == nums[left + 1]: # Avoid duplicates
                            left += 1
                        while left < right and nums[right] == nums[right - 1]: # Avoid duplicates
                            right -= 1
                        left += 1
                        right -= 1
                    elif s < target:
                        left += 1
                    else:
                        right -= 1

        return result

This code ensures that duplicates are skipped, and it applies a two-pointer technique to find all unique quadruplets that sum up to the target. The sorting ensures that the time complexity is (O(n^3)), and it is applicable within the given constraints.

Identifying Problem Isomorphism

“4Sum” requires you to find all unique quadruplets in the array which gives the sum of the target.

An isomorphic problem to this is “3Sum”. This problem asks you to find all unique triplets in the array which gives the sum of zero.

The isomorphism in these problems lies in the underlying logic which is to find unique sets of numbers that add up to a certain target. Both problems utilize similar strategies, such as sorting the array and then using two pointers to explore potential combinations. Both problems require handling duplicates in the array.

“3Sum” is simpler due to dealing with one fewer element in each combination. “4Sum” builds upon the logic of “3Sum” by adding an extra layer of complexity.

10 Prerequisite LeetCode Problems

Before tackling the “4Sum” problem, solve these:

Two Sum (LeetCode 1): This problem helps you understand the basic concept of finding two numbers in an array that add up to a certain target.
Three Sum (LeetCode 15): After you understand “Two Sum”, “Three Sum” is a good next step, as it involves an additional layer of complexity. Once you understand “Three Sum”, “Four Sum” is a natural extension.
Two Sum II - Input array is sorted (LeetCode 167): This problem introduces the concept of using a two-pointer approach to solve “Two Sum” type problems when the input array is sorted.
3Sum Closest (LeetCode 16): This problem is a variant of the “Three Sum” problem, where instead of finding the numbers that add up to zero, you find the three numbers that their sum is closest to a given target.
Container With Most Water (LeetCode 11): This problem requires understanding of the two-pointer technique which will be useful in “Four Sum”.
Sort Colors (LeetCode 75): This problem helps you understand the Dutch national flag problem which is a good precursor for understanding how to solve problems with sorting and pointers.
3Sum Smaller (LeetCode 259): This problem is similar to 3Sum and 4Sum, but adds the complexity of counting the number of sums that are less than a target.
4Sum II (LeetCode 454): This problem introduces the concept of using hashmaps to store the sum of two arrays, which is then used to find four elements that add up to zero.
Subarray Sum Equals K (LeetCode 560): This problem introduces using cumulative sum and hashmap to find subarrays that sum to a target, a good practice of using hashmap and understanding the relationship between array elements.
Find All Anagrams in a String (LeetCode 438): This problem introduces the concept of a sliding window, which is a form of two pointers and is useful in many array/string problems.

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

0 <= a, b, c, d < n a, b, c, and d are distinct. nums[a] + nums[b] + nums[c] + nums[d] == target You may return the answer in any order.

Example 1:

Input: nums = [1,0,-1,0,-2,2], target = 0 Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]] Example 2:

Input: nums = [2,2,2,2,2], target = 8 Output: [[2,2,2,2]]

Constraints:

1 <= nums.length <= 200 -109 <= nums[i] <= 109 -109 <= target <= 109

Clarification Questions

What are the clarification questions we can ask about this problem?

Identifying Problem Isomorphism

Can you help me with finding the isomorphism for this problem?

Which problem does this problem map to the corresponding isomorphic problem on Leetcode ?

 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
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        res = []
        self.findNSum(nums, target, 4, [], res)
        return res

    def findNSum(self, nums, target, N, prefix, result):
        L = len(nums)
        if N == 2:
            l, r = 0, L-1
            while l < r:
                add = nums[l] + nums[r]
                if add == target:
                    result.append(prefix + [nums[l], nums[r]])
                    l += 1
                    r -= 1
                    while l<r and nums[l-1] == nums[l]:
                        l += 1
                    while l<r and nums[r+1] == nums[r]:
                        r -= 1
                elif add > target:
                    r -= 1
                else:
                    l += 1
        else:
            for i in range(L-N+1):
                if target < N*nums[i] or target > N*nums[-1]:
                    break
                if i == 0 or (i>0 and nums[i] != nums[i-1]):
                    self.findNSum(nums[i+1:], target-nums[i], N-1, prefix+[nums[i]], result)
        return

Visual Model of the Problem

The 4-sum problem is as follows: Given an array nums of n integers, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of the target.

Similar to the 3-sum problem, the 4-sum problem can be visualized by using a number line and additional pointer. Here’s an example:

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

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

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

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

Start by fixing the first two numbers -3 and -2. Then create two pointers, one at the beginning of the array just after -2 (pointer 1 at -1) and one at the end of the array (pointer 2 at 3).

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

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

Continue this process, adjusting the pointers based on the sum and moving to the next pair of fixed numbers 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 quadruplets, and how sorting the array allows us to effectively move our pointers to get closer to the target sum.

Language Agnostic Coding Drills

Breaking down the code, the following are the units of learning arranged in increasing order of difficulty:

Basic data types: Understanding of lists and integers.
Understanding functions: What they are, how to create them, and how to use them.
Understanding classes and objects: How to define a class and create instances of it.
Understanding recursion: Concept of a function calling itself.
Basic control structures: Understanding of loops (for, while) and conditionals (if-elif-else).
Sorting a list: How to sort a list in ascending or descending order.
List slicing: How to take a slice of a list from a certain index.
List comprehensions: Creating lists dynamically with conditions.
Understanding methods and self: Understanding of the ‘self’ keyword and how to create methods inside a class.
Understanding pointers or references: Concept of using pointers to refer to a certain element in a list.
Understanding complexity and optimization: Understanding the time and space complexity, concept of optimizing a solution by making use of conditions to skip unnecessary computations.
Deeper understanding of recursion: Passing different parameters in each recursive call and understanding the recursive call stack.

For each of these points, a corresponding drill or practice problem can be created to solidify understanding.

Targeted Drills in Python

Basic data types: Write a program that initializes a list with integer values and performs some basic operations such as addition, subtraction, multiplication, and division with these integer values.

1
2
3
# Initialize a list of integers
nums = [4, 5, 2, 9, 1]
# Write code here to perform basic operations

Understanding functions: Write a function sum_nums that takes a list of integers and returns their sum.

1
# Write function here

Understanding classes and objects: Define a class Calculator that can perform addition, subtraction, multiplication, and division.

1
# Write class here

Understanding recursion: Write a recursive function factorial to calculate the factorial of an integer.

1
# Write recursive function here

Basic control structures: Write a program that iterates over a list of numbers. It prints “Even” if the number is even, “Odd” if the number is odd, and “Zero” if the number is 0.

1
# Write control structures here

Sorting a list: Write a program that sorts a list of integers in ascending order.

1
# Write sorting code here

List slicing: Given a list of numbers, write a program that prints the first half and the second half of the list.

1
# Write list slicing code here

List comprehensions: Write a list comprehension that generates the squares of all numbers from 0 to 9.

1
# Write list comprehension here

Understanding methods and self: Modify the Calculator class to store a total value. Add methods to add, subtract, multiply, or divide the total by a given number.

1
# Write updated class here

Understanding pointers or references: Write a program that takes a list of numbers and finds two numbers that sum to a given target. Use two pointers to solve this problem.

1
# Write pointers/references code here

Understanding complexity and optimization: Given a sorted list of numbers, write a function that removes duplicates in-place and returns the new length of the list. Can you do it in O(1) extra space and O(n) time complexity?

1
# Write optimized code here

Deeper understanding of recursion: Write a function that computes the nth Fibonacci number recursively. Then optimize it using memoization to reduce the time complexity.

1
# Write recursive function with optimization here

Solution to Drills

Here’s the Python code for each of the learning units:

Basic data types:

1
2
3
4
5
nums = [4, 5, 2, 9, 1]
print(nums[0] + nums[1])  # Addition
print(nums[2] - nums[3])  # Subtraction
print(nums[4] * nums[0])  # Multiplication
print(nums[1] / nums[2])  # Division

Understanding functions:

1
2
3
4
5
def sum_nums(nums):
    return sum(nums)

numbers = [1, 2, 3, 4, 5]
print(sum_nums(numbers))  # Output: 15

Understanding classes and objects:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Calculator:
    def add(self, a, b):
        return a + b

    def subtract(self, a, b):
        return a - b

    def multiply(self, a, b):
        return a * b

    def divide(self, a, b):
        if b != 0:
            return a / b
        else:
            return 'Undefined'

calc = Calculator()
print(calc.add(5, 3))  # Output: 8

Understanding recursion:

1
2
3
4
5
6
7
def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

print(factorial(5))  # Output: 120

Basic control structures:

1
2
3
4
5
6
7
8
9
nums = [0, 1, 2, 3, 4, 5]

for num in nums:
    if num == 0:
        print("Zero")
    elif num % 2 == 0:
        print("Even")
    else:
        print("Odd")

Sorting a list:

1
2
3
nums = [4, 5, 2, 9, 1]
nums.sort()
print(nums)  # Output: [1, 2, 4, 5, 9]

List slicing:

1
2
3
4
5
6
7
8
nums = [1, 2, 3, 4, 5, 6]
mid = len(nums) // 2

first_half = nums[:mid]
second_half = nums[mid:]

print(first_half)  # Output: [1, 2, 3]
print(second_half)  # Output: [4, 5, 6]

List comprehensions:

1
2
squares = [i**2 for i in range(10)]
print(squares)  # Output: [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

Understanding methods and self:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Calculator:
    def __init__(self):
        self.total = 0

    def add(self, num):
        self.total += num

    def subtract(self, num):
        self.total -= num

    def multiply(self, num):
        self.total *= num

    def divide(self, num):
        if num != 0:
            self.total /= num

calc = Calculator()
calc.add(5)
calc.subtract(2)
calc.multiply(3)
print(calc.total)  # Output: 9

Understanding pointers or references:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def two_sum(nums, target):
    i, j = 0, len(nums) - 1
    while i < j:
        total = nums[i] + nums[j]
        if total == target:
            return [i, j]
        elif total < target:
            i += 1
        else:
            j -= 1
    return None

nums = [1, 2, 3, 4, 6]
target = 6
print(two_sum(nums, target))  # Output: [1, 3]

Understanding complexity and optimization:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def remove_duplicates(nums):
    if not nums:
        return 0
    i = 0
    for j in range(1, len(nums)):
        if nums[j] != nums[i]:
            i += 1
            nums[i] = nums[j]
    return i + 1

nums = [1, 1, 2]
print(remove_duplicates(nums))  # Output: 2

Deeper understanding of recursion:

1
2
3
4
5
6
7
8
9
def fib(n, memo = {}):
    if n in memo:
        return memo[n]
    if n <= 2:
        return 1
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

print(fib(6))  # Output: 8

Python Basics

Modulo Operator

The modulo operator (%) in Python is used to find the remainder of the division of two numbers. It can be applied on integers and floating point numbers as well.

Here’s how it works:

1
print(10 % 3)  # Output: 1

In the above example, 10 divided by 3 equals 3 with a remainder of 1. So, 10 % 3 returns 1, which is the remainder of the division.

The modulo operator is often used in programming for cases where you need to wrap values around within a certain range, such as calculating the index in a circular list, or to determine whether a number is even or odd (e.g., number % 2 will be 0 for even numbers and 1 for odd numbers).

List Comprehension

List comprehension in Python is a concise way to create lists. It is a syntactic construct which consists of a single expression followed by at least one for clause and zero or more for or if clauses.

Here is the basic syntax:

1
[expression for item in iterable]

This will return a new list resulting from evaluating the expression in the context of the for and if clauses.

For example, if you wanted to create a list of the squares of all numbers from 0 to 9, you could use a list comprehension like this:

1
2
3
squares = [x**2 for x in range(10)]
print(squares)
# Output: [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

List comprehensions can also contain conditions. For instance, you could create a list of squares of all even numbers from 0 to 9:

1
2
3
even_squares = [x**2 for x in range(10) if x % 2 == 0]
print(even_squares)
# Output: [0, 4, 16, 36, 64]

Here, x**2 is the expression evaluated for each item, x in range(10) is the for clause, and if x % 2 == 0 is the if clause. The if clause is an optional condition that filters items from the input iterable.

Note that list comprehensions can also be nested, but it can lead to code that is hard to read and it is generally recommended to avoid complex list comprehensions.

Is it similar to map method in Ruby?

Yes, Python’s list comprehension feature is somewhat similar to the map method in Ruby, as they are both used to apply an operation to each item of an iterable. However, there are some differences in how they work and how they are used.

In Python, list comprehensions are used to create a new list by applying an operation to each item of an existing list (or other iterable), and they can also include a condition to decide which items to include in the new list. The syntax is quite concise and it’s a very idiomatic way to transform lists in Python. For example, here’s how you’d create a new list with the squares of all numbers in an existing list:

1
2
numbers = [1, 2, 3, 4, 5]
squares = [x**2 for x in numbers]

In Ruby, the map method is used to create a new array by applying a block of code to each item of an existing array. You can use it to achieve similar results as with Python’s list comprehensions. Here’s an equivalent example in Ruby:

1
2
numbers = [1, 2, 3, 4, 5]
squares = numbers.map { |x| x**2 }

The map method is a higher-order function that takes a function (in this case a block of code) as an argument. This is a common pattern in functional programming languages. Ruby also has a select method for filtering items based on a condition, which can be used together with map to mimic the full functionality of Python’s list comprehensions.

However, the syntax and usage of Python’s list comprehensions and Ruby’s map method are quite different, so while they can achieve similar results, they’re not exactly equivalent.

What does list comprehension provide that map method in Ruby does not provide?

One key feature that Python’s list comprehension provides that Ruby’s map method does not directly offer is the ability to incorporate conditionals within the same expression. This makes it convenient to both transform and filter elements in one line of code.

For instance, if we wanted to square all the positive numbers in a list, we can do it in Python using list comprehension as follows:

1
2
numbers = [1, -2, 3, -4, 5]
squares = [x**2 for x in numbers if x > 0] # squares = [1, 9, 25]

In the above code, x**2 is the transformation, and if x > 0 is the filter. Both are included within the brackets of the list comprehension.

In Ruby, to achieve the same, you would typically need to use map in conjunction with select (or reject), like so:

1
2
numbers = [1, -2, 3, -4, 5]
squares = numbers.select { |x| x > 0 }.map { |x| x**2 } # squares = [1, 9, 25]

In this Ruby code, select { |x| x > 0 } is used to filter the array before map { |x| x**2 } is used to transform it.

So while both Python’s list comprehension and Ruby’s map allow for similar operations, Python’s list comprehension provides a more compact syntax when both filtering and transformation are needed.

The Behavior of self

Both Python and Ruby use the self keyword to refer to the instance of the current object. However, there are a few differences in how they are used in the two languages.

In Ruby, self is a reserved keyword that is automatically defined and implicitly used. It refers to the object on which the method was called, and you can use it to call other methods on the same object or access the object’s instance variables. Ruby always knows what self is at every point in your program.

Here’s an example of using self in Ruby:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Car
  attr_accessor :speed

  def initialize
    @speed = 0
  end

  def accelerate
    self.speed += 10  # `self` here refers to the instance of the Car object
  end
end

car = Car.new
car.accelerate
puts car.speed  # Outputs: 10

In Python, self is not a reserved keyword, but a convention for the first parameter of instance methods. Python uses self to refer to the instance of the object on which a method is being called, but it must be explicitly included as the first parameter in the method definition. This allows you to access the object’s attributes and other methods.

Here’s an equivalent example in Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Car:
  def __init__(self):
    self.speed = 0

  def accelerate(self):
    self.speed += 10  # `self` here refers to the instance of the Car object

car = Car()
car.accelerate()
print(car.speed)  # Outputs: 10

In summary, both Python and Ruby use self to refer to the instance of an object, but Python requires explicit reference as a method parameter, while Ruby implicitly knows what self refers to at any given time.

Python Basics

The colon

In Python, the colon (:) has several uses, mainly related to control flow and data structures. Here are a few examples:

Defining Blocks: In control flow statements and function or class definitions, a colon is used to indicate the start of a block of code. For example:

1
2
def say_hello():
    print("Hello!")

Here, the colon at the end of the first line indicates the start of the function’s body.

Slicing: In Python, a colon is used to slice sequences, such as lists or strings. For example:

1
2
my_list = [1, 2, 3, 4, 5]
print(my_list[1:4])  # Output: [2, 3, 4]

Here, the colon is used to specify a range of indices in the list.

Dictionaries: In a dictionary, a colon is used to separate keys from values. For example:

1
my_dict = {"key": "value"}

Here, the colon separates the key “key” from the value “value”.

Ternary Operator: Python’s ternary operator (also known as the conditional expression) uses a colon. For example:

1
2
x = 5
y = "Greater than 2" if x > 2 else "Not greater than 2"

Here, the colon separates the two possible values that y could be assigned, depending on the condition x > 2.

Type Hints: Python 3.5 introduced type hints, which use colons to indicate the expected type of a function’s arguments and the type of its return value. For example:

1
2
def greet(name: str) -> str:
    return "Hello, " + name

Here, the colon in (name: str) indicates that the name parameter should be a string, and the colon in ) -> str: indicates that the function should return a string.

Instead of using braces like other language, the colon is used for indicating a block of code?

Yes, that’s correct. In Python, indentation is used to indicate a block of code instead of braces {} as in many other programming languages like C++, Java, or JavaScript. The colon : is used to denote the start of a block.

For instance, consider a simple if statement:

1
2
if 5 > 2:
    print("Five is greater than two!")

In this example, the colon at the end of the if statement indicates the start of the code block that will be executed if the condition is true. The print statement, indented underneath the if statement, is part of that block.

This applies to all sorts of control structures in Python like if, for, while, as well as function and class definitions. This use of whitespace is one of Python’s distinguishing features, promoting code readability and consistency.

If indentation is used to indicate the block of code, then why do we need the colon?

The colon in Python is used as a way to introduce a block of code and signify that what follows will be indented and part of the current statement. It serves as a visual marker for where a compound statement begins.

Without the colon, Python wouldn’t be able to distinguish where a block begins because it doesn’t use braces {} like other languages do to denote blocks of code. The colon, therefore, plays a critical role in Python’s syntax and readability.

For example, in a Python if statement, the condition is followed by a colon. The lines after the colon, which are indented, are part of the code block that is executed if the condition is true.

1
2
if condition:
    # code block

Without the colon, the interpreter wouldn’t know where the if condition ends and where the block begins. The colon clearly signifies the start of this code block.