Introduction to Two Pointers

Introduction to Two Pointers

Intuition

As the name implies, a two-pointer pattern refers to an algorithm that utilizes two pointers. But what is a pointer? It's a variable that represents an index or position within a data structure, like an array or linked list. Many algorithms just use a single pointer to attain or keep track of a single element:

Introducing a second pointer opens a new world of possibilities. Most importantly, we can now make comparisons. With pointers at two different positions, we can compare the elements at those positions and make decisions based on the comparison:

In many cases, such comparisons are made using two nested for-loops, which takes O(n2)O(n^2)O(n2) time, where n denotes the length of the data structure. In the code snippet below, i and j are two pointers used to compare every two elements of an array:

for i in range(n):
    for j in range(i + 1, n):
        compare(nums[i], nums[j])

Often, this approach does not take advantage of predictable dynamics that might exist in a data structure. An example of a data structure with predictable dynamics is a sorted array: when we move a pointer in a sorted array, we can predict whether the value being moved to is greater or smaller. For example, moving a pointer to the right in an ascending array guarantees we're moving to a value greater than or equal to the current one:

As you can see, data structures with predictable dynamics let us move pointers in a logical way. Taking advantage of this predictability can lead to improved time and space complexity, which we will illustrate with real interview problems in this chapter.

Two-pointer Strategies

Two-pointer algorithms usually take only O(n)O(n)O(n) time by eliminating the need for nested for-loops. There are three main strategies for using two pointers.

Inward traversal This approach has pointers starting at opposite ends of the data structure and moving inward toward each other:

The pointers move toward the center, adjusting their positions based on comparisons, until a certain condition is met, or they meet/cross each other. This is ideal for problems where we need to compare elements from different ends of a data structure.

Unidirectional traversal In this approach, both pointers start at the same end of the data structure (usually the beginning) and move in the same direction:

These pointers generally serve two different but supplementary purposes. A common application of this is when we want one pointer to find information (usually the right pointer) and another to keep track of information (usually the left pointer).

Staged traversal In this approach, we traverse with one pointer, and when it lands on an element that meets a certain condition, we traverse with the second pointer:

Similar to unidirectional traversal, both pointers serve different purposes. Here, the first pointer is used to search for something, and once found, a second pointer finds additional information concerning the value at the first pointer.

We discuss all of these techniques in detail throughout the problems in this chapter.

When To Use Two Pointers?

A two-pointer algorithm usually requires a linear data structure, such as an array or linked list. Otherwise, an indication that a problem can be solved using the two-pointer algorithm, is when the input follows a predictable dynamic, such as a sorted array.

Predictable dynamics can take many forms. Take, for instance, a palindromic string. Its symmetrical pattern allows us to logically move two pointers toward the center. As you work through the problems in this chapter, you'll learn to recognize these predictable dynamics more easily.

Another potential indicator that a problem can be solved using two pointers is if the problem asks for a pair of values or a result that can be generated from two values.

Real-world Example

Garbage collection algorithms: In memory compaction – which is a key part of garbage collection – the goal is to free up contiguous memory space by eliminating gaps left by deallocated (aka dead) objects. A two-pointer technique helps achieve this efficiently: a 'scan' pointer traverses the heap to identify live objects, while a 'free' pointer keeps track of the next available space to where live objects should be relocated. As the 'scan' pointer moves, it skips over dead objects and shifts live objects to the position indicated by the 'free' pointer, compacting the memory by grouping all live objects together and freeing up continuous blocks of memory.

Chapter Outline

The two-pointer pattern is very versatile and, consequently, quite broad. As such, we want to cover more specialized variants of this algorithm in separate chapters, such as Fast and Slow Pointers and Sliding Windows.

Pair Sum - Sorted

Pair Sum - Sorted

Given an array of integers sorted in ascending order and a target value, return the indexes of any pair of numbers in the array that sum to the target. The order of the indexes in the result doesn't matter. If no pair is found, return an empty array.

Example 1:

Input: nums = [-5, -2, 3, 4, 6], target = 7
Output: [2, 3]

Explanation: nums[2] + nums[3] = 3 + 4 = 7

Example 2:

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

Explanation: other valid outputs could be [1, 0], [0, 2], [2, 0], [1, 2] or [2, 1].

Intuition

The brute force solution to this problem involves checking all possible pairs. This is done using two nested loops: an outer loop that traverses the array for the first element of the pair, and an inner loop that traverses the rest of the array to find the second element. Below is the code snippet for this approach:

from typing import List
  
def pair_sum_sorted_brute_force(nums: List[int], target: int) -> List[int]:
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

This approach has a time complexity of O(n2)O(n^2)O(n2), where nnn denotes the length of the array. This approach does not take into account that the input array is sorted. Could we use this fact to come up with a more efficient solution?

A two-pointer approach is worth considering here because a sorted array allows us to move the pointers in a logical way. Let's see how this works in the example below:

A good place to start is by looking at the smallest and largest values: the first and last elements, respectively. The sum of these two values is 1.

Since 1 is less than the target, we need to move one of our pointers to find a new pair with a larger sum.

• Left pointer: The left pointer will always point to a value less than or equal to the value at the right pointer because the array is sorted. Incrementing it would result in a sum greater than or equal to the current sum of 1.
• Right pointer: Decrementing the right pointer would result in a sum that’s less than or equal to 1.

Therefore, we should increment the left pointer to find a larger sum:

Again, the sum of the values at those two pointers (4) is too small. So, let's increment the left pointer:

Now, the sum (9) is too large. So, we should decrement the right pointer to find a pair of values with a smaller sum:

Finally, we found two numbers that yield a sum equal to the target. Let’s return their indexes:

Above, we’ve demonstrated a two-pointer algorithm using inward traversal. Let’s summarize this logic. For any pair of values at left and right:

• If their sum is less than the target, increment left, aiming to increase the sum towards the target value.
• If their sum is greater than the target, decrement right, aiming to decrease the sum towards the target value.
• If their sum is equal to the target value, return [left, right].

We can stop moving the left and right pointers when they meet, as this indicates no pair summing to the target was found.

Implementation

from typing import List
       
def pair_sum_sorted(nums: List[int], target: int) -> List[int]:
    left, right = 0, len(nums) - 1
    while left < right:
        sum = nums[left] + nums[right]
        # If the sum is smaller, increment the left pointer, aiming to increase the
        # sum towards the target value.
        if sum < target:
            left += 1
        # If the sum is larger, decrement the right pointer, aiming to decrease the
        # sum towards the target value.
        elif sum > target:
            right -= 1
        # If the target pair is found, return its indexes.
        else:
            return [left, right]
    return []

Complexity Analysis

Time complexity: The time complexity of pair_sum_sorted is O(n)O(n)O(n) because we perform approximately nnn iterations using the two-pointer technique in the worst case.

Space complexity: We only allocated a constant number of variables, so the space complexity is O(1)O(1)O(1).

Test Cases

In addition to the examples already discussed, here are some other test cases you can use. These extra test cases cover different contexts to ensure the code works well across a range of inputs. Testing is important because it helps identify mistakes in your code, ensures the solution works for uncommon inputs, and brings attention to cases you might have overlooked.

Interview Tip

Tip: Consider all information provided. When interviewers pose a problem, they sometimes provide only the minimum amount of information required for you to start solving it. Consequently, it’s crucial to thoroughly evaluate all that information to determine which details are essential for solving the problem efficiently. In this problem, the key to arriving at the optimal solution is recognizing that the input is sorted.

Triplet Sum

Triplet Sum

Given an array of integers, return all triplets [a, b, c] such that a + b + c = 0 . The solution must not contain duplicate triplets (e.g., [1, 2, 3] and [2, 3, 1] are considered duplicates). If no such triplets are found, return an empty array.

Each triplet can be arranged in any order, and the output can be returned in any order.

Example:

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

Intuition

A brute force solution involves checking every possible triplet in the array to see if they sum to zero. This can be done using three nested loops, iterating through each combination of three elements.

Duplicate triplets can be avoided by sorting each triplet, which ensures that identical triplets with different representations (e.g., [1, 3, 2] and [3, 2, 1]) are ordered consistently (e.g., [1, 2, 3]). Once sorted, we can add these triplets to a hash set. This way, if the same triplet is encountered again, the hash set will only keep one instance. Below is the code snippet for this approach:

from typing import List
   
def triplet_sum_brute_force(nums: List[int]) -> List[List[int]]:
    n = len(nums)
    # Use a hash set to ensure we don't add duplicate triplets.
    triplets = set()
    # Iterate through the indexes of all triplets.
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                if nums[i] + nums[j] + nums[k] == 0:
                    # Sort the triplet before including it in the hash set.
                    triplet = tuple(sorted([nums[i], nums[j], nums[k]]))
                    triplets.add(triplet)
    return [list(triplet) for triplet in triplets]

This solution is quite inefficient with a time complexity of O(n3)O(n^3)O(n3), where nnn denotes the length of the input array. How can we do better?

Let’s see if we can find at least one triplet that sums to 0. Notice that if we fix one of the numbers in a triplet, the problem can be reduced to finding the other two. This leads to the following observation:

For any triplet [a, b, c], if we fix 'a', we can focus on finding a pair [b, c] that sums to '-a' (a + b + c = 0 → b + c = -a).

Sound familiar? That's because the problem of finding a pair of numbers that sum to a target has already been addressed by Pair Sum - Sorted. However, we can only use that algorithm on a sorted array. So, the first thing we should do is sort the input. Consider the following example:

Now, starting at the first element, -2 (i.e., 'a'), we'll use the pair_sum_sorted method on the rest of the array to find a pair whose sum equals 2 (i.e., '-a'):

As you can see, when we called pair_sum_sorted, we did not find a pair with a sum of 2. This indicates that there are no triplets starting with -2 that add up to 0.

So, let's increment our main pointer, i, and try again.

This time, we found one pair that resulted in a valid triplet.

If we continue this process for the rest of the array, we find that [-1, -1, 2] is the only triplet whose sum is 0.

There’s an important difference between the pair_sum_sorted implementation in Pair Sum - Sorted and the one in this problem: for this problem, we don’t stop when we find one pair, we keep going until all target pairs are found.

Handling duplicate triplets Something we previously glossed over is how to avoid adding duplicate triplets. There are two cases in which this happens. Consider the example below:

Case 1: duplicate ‘a’ values‾\underline{\text{Case 1: duplicate ‘a’ values}}Case 1: duplicate ‘a’ values​

The first instance where duplicates may occur is when seeking pairs for triplets that start with the same ‘a’ value:

Since pair_sum_sorted would look for pairs that sum ‘-a’ in both instances, we’d naturally end up with the same pairs and, hence, the same triplets.

To avoid picking the same 'a' value, we keep increasing i (where num[i] represents the value 'a') until it reaches a different number from the previous one. We do this before we start looking for pairs using the pair_sum_sorted method. This logic works because the array is sorted, meaning equal numbers are next to each other. The code snippet for checking duplicate 'a' values looks like this:

# To prevent duplicate triplets, ensure 'a' is not a repeat of the previous element
# in the sorted array.
if i > 0 and nums[i] == nums[i - 1]:
    continue
... Find triplets ...

Case 2: duplicate ‘b’ values‾\underline{\text{Case 2: duplicate ‘b’ values}}Case 2: duplicate ‘b’ values​

As for the second case, consider what happens during pair_sum_sorted when we encounter a similar issue. For a fixed target value (‘-a’), pairs that start with the same number ‘b’ will always be the same:

The remedy for this is the same as before: ensure the current ‘b’ value isn’t the same as the previous value.

It’s important to note that we don’t need to explicitly handle duplicate 'c' values. The adjustments made to avoid duplicate 'a' and 'b' values ensure each pair [a, b] is unique. Since 'c' is determined by the equation c = -(a + b), each unique [a, b] pair will result in a unique 'c' value. Therefore, by just avoiding duplicates in 'a' and 'b', we automatically avoid duplicates in the [a, b, c] triplets.

Optimization An interesting observation is that triplets that sum to 0 cannot be formed using positive numbers alone. Therefore, we can stop trying to find triplets once we reach a positive ‘a’ value since this implies that ‘b’ and ‘c’ would also be positive.

Implementation

From the above intuition, we know we need to slightly modify the pair_sum_sorted function to avoid duplicate triplets. We also need to pass in a start value to indicate the beginning of the subarray on which we want to perform the pair-sum algorithm. Otherwise, the two-pointer logic remains nearly identical to that of Pair Sum - Sorted.

from typing import List
  
def triplet_sum(nums: List[int]) -> List[List[int]]:
    triplets = []
    nums.sort()
    for i in range(len(nums)):
        # Optimization: triplets consisting of only positive numbers will never sum
        # to 0.
        if nums[i] > 0:
            break
        # To avoid duplicate triplets, skip 'a' if it's the same as the previous
        # number.
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        # Find all pairs that sum to a target of '-a' ('-nums[i]').
        pairs = pair_sum_sorted_all_pairs(nums, i + 1, -nums[i])
        for pair in pairs:
            triplets.append([nums[i]] + pair)
    return triplets
  
def pair_sum_sorted_all_pairs(nums: List[int], start: int, target: int) -> List[int]:
    pairs = []
    left, right = start, len(nums) - 1
    while left < right:
        sum = nums[left] + nums[right]
        if sum == target:
            pairs.append([nums[left], nums[right]])
            left += 1 # To avoid duplicate '[b, c]' pairs, skip 'b' if it’s the same as the # previous number.
            while left < right and nums[left] == nums[left - 1]:
                left += 1
        elif sum < target:
            left += 1 
        else:
            right -= 1
    return pairs

Complexity Analysis

Time complexity: The time complexity of triplet_sum is O(n2)O(n^2)O(n2). Here’s why:

• We first sort the array, which takes O(nlog⁡(n))O(n\log(n))O(nlog(n)) time.
• Then, for each of the nnn elements in the array, we call pair_sum_sorted_all_pairs at most once, which runs in O(n)O(n)O(n) time.

Therefore, the overall time complexity is O(log⁡(n))+O(n2)=O(n2)O(\log(n))+O(n^2)=O(n^2)O(log(n))+O(n2)=O(n2).

Space complexity: The space complexity is O(n)O(n)O(n) due to the space taken up by Python’s sorting algorithm. It's important to note that this complexity does not include the output array triplets because we’re only concerned with the additional space used by the algorithm, not the space needed for the output itself.

If the interviewer asks what the space complexity would be if we included the output array, it would be O(n2)O(n^2)O(n2). This is because the pair_sum_sorted_all_pairs function, in the worst case, can add approximately nnn pairs to the output. Since this function is called approximately nnn times, the overall space complexity is O(n2)O(n^2)O(n2).

Test Cases

In addition to the examples already covered in this explanation, below are some others to consider when testing your code.

Is Palindrome Valid

Is Palindrome Valid

A palindrome is a sequence of characters that reads the same forward and backward.

Given a string, determine if it's a palindrome after removing all non-alphanumeric characters. A character is alphanumeric if it's either a letter or a number.

Example 1:

Input: s = 'a dog! a panic in a pagoda.'
Output: True

Example 2:

Input: s = 'abc123'
Output: False

Constraints:

• The string may include a combination of lowercase English letters, numbers, spaces, and punctuations.

Intuition

Identifying palindromes A string is a palindrome if it remains identical when read from left to right or right to left. In other words, if we reverse the string, it should still read the same, disregarding spaces and punctuation:

An important observation is that if a string is a palindrome, the first character would be the same as the last, the second character would be the same as the second-to-last, etc:

A palindrome of odd length is different because it has a middle character. In this case, the middle character can be ignored since it has no “mirror” character elsewhere in the string.

Palindromes provides an ideal scenario for using two pointers (left and right). By initially setting the pointers at the beginning and end of the string, we can compare the characters at these positions. Ignoring non-alphanumeric characters for the moment, the logic can be summarized as follows:

• If the alphanumeric characters at left and right are the same, move both pointers inward to process the next pair of characters.
• If not, the string is not a palindrome: return false.

If we successfully compare all character pairs without returning false, the string is a palindrome, and we should return true.

Processing non-alphanumeric characters Now, let's explore how to find palindromes that include non-alphanumeric characters.

Since non-alphanumeric characters don’t affect whether a string is a palindrome, we should skip them. This can be achieved with the following approach, which ensures the left and right pointers are adjusted to focus only on alphanumeric characters:

• Increment left until the character it points to is alphanumeric.
• Decrement right until the character it points to is alphanumeric.

With this in mind, let’s check if the string below is a palindrome using all the information we know so far:

As shown above, when the left and right pointers meet, it signals our exit condition. When these pointers meet, we've reached the middle character of the palindrome, at which point we can exit the loop since the middle character doesn’t need to be evaluated. However, we need to keep in mind that exiting when left equals right won't always be sufficient as an exit condition. For example, if the number of alphanumeric characters is even, the pointers won’t meet. This can be observed below:

Therefore, we need to ensure we exit the loop when left equals right, or when left passes right. In other words, the algorithm continues while left is less than right:

while left < right:

Implementation

In Python, we can use the inbuilt isalnum method to check if a character is alphanumeric.

def is_palindrome_valid(s: str) -> bool:
    left, right = 0, len(s) - 1
    while left < right:
        # Skip non-alphanumeric characters from the left.
        while left < right and not s[left].isalnum():
            left += 1
        # Skip non-alphanumeric characters from the right.
        while left < right and not s[right].isalnum():
            right -= 1
        # If the characters at the left and right pointers don’t match, the string is
        # not a palindrome.
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

Complexity Analysis

Time complexity: The time complexity of is_palindrome_valid is O(n)O(n)O(n), where nnn denotes the length of the string. This is because we perform approximately nnn iterations using the two-pointer technique.

Space complexity: We only allocated a constant number of variables, so the space complexity is O(1)O(1)O(1).

Test Cases

In addition to the examples discussed, below are more examples to consider when testing your code.

Interview Tips

Tip 1: Clarify problem constraints. It's common to not receive all the details of a problem from an interviewer. For example, you might only be asked to "check if a string is a palindrome." But before diving into a solution, it's important to clarify details with the interviewer, such as the presence of non-alphanumeric characters, their treatment, the role of numbers, the case sensitivity of letters, and other relevant details.

Tip 2: Confirm before using significant in-built functions. This problem is made easier by using in-built functions such as .isalnum (or equivalent). Before using an in-built function that simplifies the implementation, ask the interviewer if it's okay to use it, or if they would prefer you implement it yourself.

The interviewer will most likely allow the use of an in-built function, or ask you to implement it as an exercise for later in the interview. If you use an in-built function, make sure you understand its time and space complexity.

Remember that interviewers are looking for team players, and this shows them you're considerate of their preferences and can adapt your approach based on the requirements.

Largest Container

Largest Container

You are given an array of numbers, each representing the height of a vertical line on a graph. A container can be formed with any pair of these lines, along with the x-axis of the graph. Return the amount of water which the largest container can hold.

Example:

Input: heights = [2, 7, 8, 3, 7, 6]
Output: 24

Intuition

If we have two vertical lines, heights[i] and heights[j], the amount of water that can be contained between these two lines is min(heights[i], heights[j]) * (j - i), where j - i represents the width of the container. We take the minimum height because filling water above this height would result in overflow.

In other words, the area of the container depends on two things:

• The width of the rectangle.
• The height of the rectangle, as dictated by the shorter of the two lines.

The brute force approach to this problem involves checking all pairs of lines, and returning the largest area found between each pair:

from typing import List
    
def largest_container_brute_force(heights: List[int]) -> int:
   n = len(heights)
   max_water = 0
   # Find the maximum amount of water stored between all pairs of lines.
   for i in range(n):
       for j in range(i + 1, n):
           water = min(heights[i], heights[j]) * (j - i)
           max_water = max(max_water, water)
   return max_water

Searching through all possible pairs of values takes O(n2)O(n^2)O(n2) time, where nnn denotes the length of the array. Let's look for a more efficient solution.

We would like both the height and width to be as large as possible to have the largest container.

It’s not immediately obvious how to find the container with the largest height, as the heights of the lines in the array don’t follow a clear pattern. However, we do know the container with the maximum width: the one starting at index 0 and ending at index n - 1.

So, we could start by maximizing the width by setting a pointer at each end of the array. Then, we can gradually reduce the width by moving these two pointers inward, hoping to find a container with a larger height that potentially yields a larger area. This suggests we can use the two-pointer pattern to solve the problem.

Moving a pointer inward means shifting either the left pointer to the right, or the right pointer to the left, effectively narrowing the gap between them.

Consider the following example:

The widest container can store an area of water equal to 10. Since this is the largest container we’ve found so far, let’s set max_water to 10.

How should we proceed? Moving either pointer inward yields a container with a shorter width. This leaves height as the determining factor. In this case, the left line is shorter than the right line, which means that the left line limits the water's height. Therefore, to find a larger container, let's move the left pointer inward:

The current container can hold 24 units of water, the largest amount so far. So, let’s update max_water to 24. Here, the right line is shorter, limiting the water's height. To find a larger container, move the right pointer inward:

After this, we encounter a situation where the height of the left and right lines are equal. In this situation, which pointer should we move inward? Well, regardless of which one, the next container is guaranteed to store less water than the current one. Let’s try to understand why.

Moving either pointer inward yields a container of shorter width, leaving height as the determining factor. However, regardless of which pointer we move inward, the other pointer remains at the same line. So, even if a pointer is moved to a taller line, the other pointer will restrict the height of the water, as we take the minimum of the two lines.

Therefore, since we can’t increase height by moving just one pointer, we can just move both pointers inward:

Now, the right line is limiting the height of the water. So, we move the right pointer inward:

Finally, the left and right pointers meet. We can conclude our search here and return max_water:

Based on the decisions taken in the example, we can summarize the logic:

1. If the left line is smaller, move the left pointer inward.
2. If the right line is smaller, move the right pointer inward.
3. If both lines have the same height, move both pointers inward.

Implementation

from typing import List
  
def largest_container(heights: List[int]) -> int:
    max_water = 0
    left, right = 0, len(heights) - 1
    while (left < right):
        # Calculate the water contained between the current pair of lines.
        water = min(heights[left], heights[right]) * (right - left)
        max_water = max(max_water, water)
        # Move the pointers inward, always moving the pointer at the shorter line. If
        # both lines have the same height, move both pointers inward.
        if (heights[left] < heights[right]):
            left += 1
        elif (heights[left] > heights[right]):
            right -= 1
        else:
            left += 1
            right -= 1
    return max_water

Complexity Analysis

Time complexity: The time complexity of largest_container is O(n)O(n)O(n) because we perform approximately nnn iterations using the two-pointer technique.

Space complexity: We only allocated a constant number of variables, so the space complexity is O(1)O(1)O(1).

Test Cases

In addition to the examples discussed throughout this explanation, below are some other examples to consider when testing your code.

Shift Zeros to the End

Shift Zeros to the End

Given an array of integers, modify the array in place to move all zeros to the end while maintaining the relative order of non-zero elements.

Example:

Input: nums = [0, 1, 0, 3, 2]
Output: [1, 3, 2, 0, 0]

Intuition

This problem has three main requirements:

1. Move all zeros to the end of the array.
2. Maintain the relative order of the non-zero elements.
3. Perform the modification in place.

A naive approach to this problem is to build the output using a separate array (temp). We can add all non-zero elements from the left of nums to this temporary array and leave the rest of it as zeros. Then, we just set the input array equal to temp.

By identifying and moving the non-zero elements from the left side of the array first, we ensure their order is preserved when we add them to the output:

def shift_zeros_to_the_end_naive(nums: List[int]) -> None:
    temp = [0] * len(nums)
    i = 0
    # Add all non-zero elements to the left of 'temp'.
    for num in nums:
        if num != 0:
            temp[i] = num
            i += 1
    # Set 'nums' to 'temp'.
    for j in range(len(nums)):
        nums[j] = temp[j]

Unfortunately, this solution breaks the third requirement of modifying the input array in place.

However, there's still valuable insight to be gained from this approach. In particular, notice that this solution focuses on the non-zero elements instead of zeros. This means if we change our goal to move all non-zero elements to the left of the array, the zeros will consequently end up on the right. Therefore, we only need to focus on non-zero elements:

If there was a way to iterate over the above range of the array where the non-zero elements go, we could iteratively place each non-zero element in that range.

Two pointers We can use two pointers for this:

• A left pointer to iterate over the left of the array where the non-zero elements should be placed.
• A right pointer to find non-zero elements.

Consider the example below. Start by placing the left and right pointers at the start of the array. Before we move non-zero elements to the left, we need the right pointer to be pointing at a non-zero element. So, we ignore the zero at the first element and increment right:

Remember, we only use the left pointer to keep track of where non-zero elements should be placed. So, until we find a non-zero element, we shouldn’t move this pointer.

Now, the value at the right pointer is non-zero. Let’s discuss how to handle this case.

1. Swap the elements at left and right: First, we’d like to move the element at the right pointer to the left of the array. So, we swap it with the element at the left pointer.

2. Increment the pointers:

• After the swap is complete, we should increment the left pointer to position it where the next non-zero element should go.
• Let’s also increment the right pointer in search of the next non-zero element.

We can apply this logic to the rest of the array, incrementing the right pointer at each step to find the next non-zero element:

Once all swapping is done, all zeros will end up at the right end of the array as intended, without disturbing the order of the non-zero elements. The two-pointer strategy used in this problem is unidirectional traversal.

Implementation

You might have noticed that we always move the right pointer forward, regardless of whether it points to a zero or a non-zero. This allows us to use a for-loop to iterate the right pointer.

def shift_zeros_to_the_end(nums: List[int]) -> None:
    # The 'left' pointer is used to position non-zero elements.
    left = 0
    # Iterate through the array using a 'right' pointer to locate non-zero
    # elements.
    for right in range(len(nums)):
        if nums[right] != 0:
            if right != left:
                nums[left], nums[right] = nums[right], nums[left]
            # Increment 'left' since it now points to a position already occupied
            # by a non-zero element.
            left += 1

Complexity Analysis

Time complexity: The time complexity of shift_zeros_to_the_end is O(n)O(n)O(n), where nnn denotes the length of the array. This is because we iterate through the input array once.

Space complexity: The space complexity is O(1)O(1)O(1) because shifting is done in place.

Test Cases In addition to the examples discussed, below are more examples to consider when testing your code.

Next Lexicographical Sequence

Next Lexicographical Sequence

Given a string of lowercase English letters, rearrange the characters to form a new string representing the next immediate sequence in lexicographical (alphabetical) order. If the given string is already last in lexicographical order among all possible arrangements, return the arrangement that's first in lexicographical order.

Example 1:

Input: s = 'abcd'
Output: 'abdc'

Explanation: "abdc" is the next sequence in lexicographical order after rearranging "abcd".

Example 2:

Input: s = 'dcba'
Output: 'abcd'

Explanation: Since "dcba" is the last sequence in lexicographical order, we return the first sequence: "abcd".

Constraints:

• The string contains at least one character.

Intuition

Before devising a solution, let’s first make sure we understand what the next lexicographical sequence of a string is.

An important detail is that a string’s next lexicographical sequence is lexicographically larger than the original string. Consider the string “abc” and all its permutations in a lexicographically ordered sequence:

We can see the increasing order of the strings in the sequence when we translate each letter to its position in the alphabet:

From this, we also notice the next string in the sequence after “abc” is “acb”, which is the first string larger than the original string:

This gives us some indication of what we need to find. The next lexicographical string:

1. Incurs the smallest possible lexicographical increase from the original string.
2. Uses the same letters as the original string.

Identifying which characters to rearrange Since our goal is to make the smallest possible increase, we need to somehow rearrange the characters on the right side of the string.

To understand why, imagine trying to “increase” a string’s value. Increasing the rightmost letter causes the resulting string to be closer to the original string lexicographically than increasing the leftmost letter does:

Therefore, we should focus on rearranging characters on the right-hand side of the string first, if possible.

A key insight is that the last string in a lexicographical sequence (i.e., the largest permutation) will always follow a non-increasing order. We can see this with the string “abcc”, for example, with its largest possible permutation being “ccba”:

How does this help us? We know we need to rearrange the characters on the right of the string, but we don’t know how many to rearrange. From now on, let’s refer to the rightmost characters that should be rearranged as the suffix.

Take the string "abcedda" as an example. We traverse it from right to left with the goal of finding the shortest suffix that can be rearranged to form a larger permutation. The last 4 characters form a non-increasing suffix, and cannot be rearranged to make the string larger:

However, the next character, ‘c’, breaks the non-increasing sequence:

Let’s call this character the pivot:

If no pivot is found, it means the string is already the last lexicographical sequence. In this case, we need to obtain its first lexicographical permutation as the problem states. This can be done by reversing the string:

Rearranging characters Having identified the shortest suffix to rearrange, the next objective is to rearrange this suffix to make the smallest increase possible. We have to start the rearrangement at the pivot since the rest of the suffix is already arranged in its largest permutation.

To make the character at the pivot position larger, we’d need to swap the pivot with a character larger than it on the right.

In our example, which character should our pivot (‘c’) swap with? We want to swap it with a character larger than 'c,' but not too much larger because the increase should be as small as possible. Let’s figure out how we find such a character.

Since the substring after the pivot is lexicographically non-increasing, we can find the closest character larger than ‘c’ by traversing this suffix from right to left and stopping at the first character larger than it. In other words, we’re finding the rightmost successor to the pivot, which is ‘d’:

Now, we swap the pivot and the rightmost successor:

The character at the pivot has increased, so to get the next permutation, we should make the substring after the pivot as small as possible. After the swap shown above, we see that substring “edca” is not at its smallest permutation. So, we need to minimize the permutation of this substring.

An important observation is that after the previous swap, the substring after the pivot is still lexicographically non-increasing.

This means we can minimize this substring’s permutation by reversing it:

And just like that, we found the next lexicographical sequence! The two-pointer strategy used in this problem is staged traversal, where we first identify the pivot, and then identify the rightmost successor relative to it.

Many steps are involved in identifying the next lexicographical sequence. So, here’s a summary:

1. Locate the pivot.

• The pivot is the first character that breaks the non-increasing sequence from the right of the string.
• If no pivot is found, the string is already at its last lexicographical sequence, and the result is just the reverse of the string.

1. Find the rightmost successor to the pivot.
2. Swap the rightmost successor with the pivot to increase the lexicographical order of the suffix.
3. Reverse the suffix after the pivot to minimize its permutation.

Implementation

def next_lexicographical_sequence(s: str) -> str:
    letters = list(s)
    # Locate the pivot, which is the first character from the right that breaks
    # non-increasing order. Start searching from the second-to-last position.
    pivot = len(letters) - 2
    while pivot >= 0 and letters[pivot] >= letters[pivot + 1]:
        pivot -= 1
    # If pivot is not found, the string is already in its largest permutation. In
    # this case, reverse the string to obtain the smallest permutation.
    if pivot == -1:
        return ''.join(reversed(letters))
    # Find the rightmost successor to the pivot.
    rightmost_successor = len(letters) - 1
    while letters[rightmost_successor] <= letters[pivot]:
        rightmost_successor -= 1
    # Swap the rightmost successor with the pivot to increase the lexicographical
    # order of the suffix.
    letters[pivot], letters[rightmost_successor] = (letters[rightmost_successor], letters[pivot])
    # Reverse the suffix after the pivot to minimize its permutation.
    letters[pivot + 1:] = reversed(letters[pivot + 1:])
    return ''.join(letters)

Complexity Analysis

Time complexity: The time complexity of next_lexicographical_sequence is O(n)O(n)O(n), where nnn denotes the length of the input string. This is because we perform a maximum of two iterations across the string: one to find the pivot and another to find the rightmost character in the suffix that’s greater in value than the pivot. We also perform one reversal, which takes O(n)O(n)O(n) time.

Space complexity: The space complexity is O(n)O(n)O(n) due to the space taken up by the letters list. In Python, this additional space is used because strings are immutable, which necessitates storing the input string as a list.

Test Cases

In addition to the examples discussed, below are more examples to consider when testing your code.

Interview Tip

Tip: Be precise with your language. It’s crucial to be precise with your choice of words during an interview, especially for technical descriptions. For instance, in this problem, we use “non-increasing” instead of “decreasing,” as “decreasing” implies each term is strictly smaller than the previous one, which isn’t true in this case since adjacent characters can be equal.

Introduction to Hash Maps and Sets

Introduction to Hash Maps and Sets

Intuition

Picture working in a grocery store. A customer asks for the price of a fruit. If you just have a paper list of all the fruits, you would need to look through it to find the specific fruit, which can be time-consuming. However, by memorizing the list, you can know the prices of all fruits instantly, enabling you to promptly give the correct price to the customer. This is similar to how hash maps work, enabling quick access to information.

Hash maps A hash map – also known as a hash table or dictionary, depending on the language – is a data structure that pairs keys with values. Let's illustrate this using the example of fruits and their prices:

Having a mental map of fruit prices is conceptually similar to being able to instantly access fruit prices using a hash map, where the fruit name is the key, and its price is the value. When we look up a price using the fruit's name as the key, the hash map will immediately return its price:

Hash maps are incredibly efficient for lookups, insertions, and deletions, as they typically perform these operations in constant time: O(1)O(1)O(1). They are one of the most versatile, widely-used data structures in computer science, used for tasks such as counting the frequency of elements, caching data, and more.

Properties of hash maps:

• Data is stored in the form of key-value pairs.
• Hash maps don't store duplicates. Every key in a hash map is unique, ensuring each value can be distinctly identified and accessed.
• Hash maps are unordered data structures, meaning keys are not stored in any specific order.

Time complexity breakdown Below, n denotes the number of entries in the hash map.

In coding interviews, we generally consider hash map operations to have a fast average time complexity of O(1)O(1)O(1), as opposed to their worst-case complexities. This is based on the assumption that an efficient hash function minimizes collisions [HashCollision]. However, in the worst-case scenario where a poorly optimized hash function results in frequent collisions, the time complexity can deteriorate to O(n)O(n)O(n), necessitating a linear search through all entries.

Hash sets Hash sets are a simpler form of hash maps. Instead of storing key-value pairs, they store only the keys. Using the grocery store analogy, a hash set is like having a mental checklist of fruits without their prices. It's useful for quickly checking the presence or absence of an item, like checking whether a particular fruit is in stock.

When to use hash maps or sets Common use cases of hash maps include implementing dictionaries, counting frequencies, storing key-value pairs, and handling scenarios requiring quick lookups.

Common use cases of hash sets include storing unique elements, marking elements as used or visited, and checking for duplicates.

In the description of a problem, pay attention to keywords like "frequency", "unique", "map", "dictionary", or "fast lookup", because these often indicate that hash maps or sets could be useful.

Essential concepts for mastering hash maps and sets This chapter discusses the practical uses of hash maps and sets. For a more complete understanding of how they work and why they're so efficient, please explore topics that go beyond the scope of this chapter, such as:

• Hash functions: explore the intricacies of how keys are mapped to specific values in a hash table [1].
• Collision and collision-handling techniques: understand methods like chaining, or open addressing for resolving hash collisions [2].
• Load factors and rehashing: these make it easier to understand how hash tables grow and change size [3].

Real-world Example

Web browser cache: Hash maps and sets are used everywhere in real-world systems. A classic example of hash maps in action is in caching systems within web browsers. When you visit a website, your browser stores data such as images, HTML, and CSS files in a cache so it can load much faster on future visits.

Chapter Outline

This chapter includes problems involving the most popular use cases of hash maps and sets, aiming to improve your understanding and effectiveness in utilizing them.

Pair Sum - Unsorted

Pair Sum - Unsorted

Given an array of integers, return the indexes of any two numbers that add up to a target. The order of the indexes in the result doesn't matter. If no pair is found, return an empty array.

Example:

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

Explanation: nums[0] + nums[2] = -1 + 4 = 3

Constraints:

• The same index cannot be used twice in the result.

Intuition

A brute force approach is to iterate through every possible pair in the array to see if their sum is equal to the target. This is the same as the brute force solution described in the Pair Sum - Sorted problem, which has a time complexity of O(n2)O(n^2)O(n2), where nnn is the length of the array. We could also sort the array and then perform the two-pointer algorithm used in Pair Sum - Sorted, which would take O(nlog(n))O(nlog(n))O(nlog(n)) time due to sorting. Let’s see if we can find an even faster solution.

Complement We're asked to find a pair (x, y) such that x + y == target. In this equation, there are two unknowns: x and y. An important observation is that if we know one of these numbers, we can easily calculate what the other number should be.

For each number x in nums, we need to find another number y such that x + y = target, or in other words, y = target - x. We can call this number the complement of x.

Keep in mind, we need to return the indexes of the pair of numbers, not the pair itself. So, we’ll need a way to find a number's complement as well as its index.

One way we could do this is to loop through the array to find each number’s complement and corresponding index. But this takes O(n2)O(n^2)O(n2) time since we’d need to do a linear traversal to search for each number’s complement. Instead, we’d like an efficient way to determine the index of any number in the array without needing to search the array. Is there a data structure that can help with this?

Hash map A hash map works great because we can store and look up values in O(1)O(1)O(1) time. Each number and its index can be stored in the hash map as key-value pairs:

This allows us to retrieve the index of any number’s complement efficiently. Notice that duplicate numbers don’t need to be considered here since only one valid pair needs to be found.

The most intuitive way to incorporate a hash map is to:

1. In the first pass, populate the hash map with each number and its corresponding index.
2. In the second pass, scan through the array to check if each number's complement exists in the hash map. If it does, we can return the indexes of that number and its complement.

Below is the code snippet for this two-pass approach:

from typing import List
        
def pair_sum_unsorted_two_pass(nums: List[int], target: int) -> List[int]:
    num_map = {}
    # First pass: Populate the hash map with each number and its index.
    for i, num in enumerate(nums):
        num_map[num] = i
    # Second pass: Check for each number's complement in the hash map.
    for i, num in enumerate(nums):
        complement = target - num
        if complement in num_map and num_map[complement] != i:
            return [i, num_map[complement]]
    return []

This algorithm requires two passes. Is it possible to do this in only one? A one-pass solution implies that we would need to populate the hash map while searching for complements. Is this possible? Consider the example below:

Start at index 0. Its complement would be 3 - (-1) = 4. Does our hash map have 4 in it? No, it's empty at the moment. So, let's add -1 and its index to the hash map:

Next, let’s look at index 1. Its complement (0) does not exist in the hash map. So, just add 3 and its index to the hash map:

At index 2, we notice 4's complement (-1) exists in the hash map. This means we found a pair that sums to the target:

Now, we can return the indexes of the two values. Fetch the index of 4 from the input array and the index of its complement from the hash map:

Implementation

from typing import List
   
def pair_sum_unsorted(nums: List[int], target: int) -> List[int]:
    hashmap = {}
    for i, x in enumerate(nums):
        if target - x in hashmap:
            return [hashmap[target - x], i]
        hashmap[x] = i
    return []

Complexity Analysis

Time complexity: The time complexity of pair_sum_unsorted is O(n)O(n)O(n) because we iterate through each element in the nums array once and perform constant-time hash map operations during each iteration.

Space complexity: The space complexity is O(n)O(n)O(n) since the hash map can grow up to nnn in size.

Interview Tip

Tip: Iterate through solutions. Don’t always jump straight to the most optimal or clever solution, as this won't give the interviewer much insight into your problem-solving process. Consider multiple approaches, starting with the more straightforward ones, and gradually refine them. This way, you demonstrate your thought process and how you arrive at a more optimal solution.

Verify Sudoku Board

Verify Sudoku Board

Given a partially completed 9×9 Sudoku board, determine if the current state of the board adheres to the rules of the game:

• Each row and column must contain unique numbers between 1 and 9, or be empty (represented as 0).
• Each of the nine 3×3 subgrids that compose the grid must contain unique numbers between 1 and 9, or be empty.

Note: You are asked to determine whether the current state of the board is valid given these rules, not whether the board is solvable.

Example:

Output: False

Constraints:

• Assume each integer on the board falls in the range of [0, 9].

Intuition

Our primary objective is to check every row, column, and each of the nine 3x3 subgrids, for any duplicate numbers. Let's first discuss the mechanism for finding duplicate elements, then look into how we can apply this to rows, columns, and subgrids.

Checking for duplicates Let’s start by figuring out how to check for duplicates on a single row of the board:

A naive way to do this is to take each number in the row and search the row to see if that number appears again. Performing a linear search for each number would result in a time complexity of O(n2)O(n^2)O(n2) to check all numbers in one row, which is quite time consuming.

We can use a hash set to improve the time complexity. By using a hash set, we can keep track of which numbers were previously visited as we iterate through the row. When we encounter a new number, we can check if it's already in the set in O(1)O(1)O(1) time. If it is, then it's a duplicate:

If we had a hash set for each of the 9 rows, we could keep track of duplicates in each row separately. We can do this for columns and subgrids as well, with one hash set for each column, and one hash set for each subgrid. The challenge here is determining which hash sets correspond to each cell's row, column, and subgrid, so we know which hash sets to reference:

So, let’s discuss how we can identify a cell’s row, column, or subgrid.

Identifying rows and columns Identifying rows is straightforward because each row has an index. The same applies to columns. Therefore, we can create an array of 9 hash sets, one for each row, allowing us to access a row’s hash set directly by its index. Similarly, we can set up an array of hash sets for each column.

Identifying subgrids Subgrids pose an interesting challenge because we can’t immediately identify which subgrid a cell belongs to, unlike the straightforward index-based identification for rows and columns.

That said, as with rows and columns, there are still only 9 subgrids. If we visualize the subgrids, we can see them displayed in a 3x3 grid:

What we'd like is a way to index each of these subgrids as if indexing a 3x3 matrix. To do this, we require a method to convert the indexes ranging from 0 to 8 to the corresponding adjusted indexes from 0 to 2, as illustrated below:

Since we got these adjusted indexes from shrinking a 9x9 grid to a 3x3 grid – which is effectively dividing the number of rows and columns by 3 – we can get the new subgrid row and column indexes by dividing by 3 (using integer division), as well:

With these modified indexes, we can organize nine hash sets within a 3x3 table, one for each subgrid. Each cell in this table represents the corresponding subgrid in the above 3x3 representation. So, we can access the hash set of a subgrid at any cell by using our adjusted indexes (i.e., subgrid_sets[r // 3][c // 3]) (the // operator performs integer division).

One-pass Sudoku verification We now have everything needed for a one-pass solution. We can start by initializing hash sets, 9 for each row, 9 for each column, and 9 for each subgrid, using a 3x3 array.

As we iterate through each cell in the grid, we check if a previously encountered number already exists in the current row, column, or subgrid, by querying the appropriate hash sets:

• If the number is in any of these hash sets, return false.
• Otherwise, add it to the corresponding row, column, and subgrid hash sets.

This process helps us keep track of numbers in each row, column, and subgrid. If we successfully iterate through the board without encountering any duplicates, it indicates the Sudoku board is valid. Therefore, we can return true.

Implementation

from typing import List
  
def verify_sudoku_board(board: List[List[int]]) -> bool:
    # Create hash sets for each row, column, and subgrid to keep track of numbers
    # previously seen on any given row, column, or subgrid.
    row_sets = [set() for _ in range(9)]
    column_sets = [set() for _ in range(9)]
    subgrid_sets = [[set() for _ in range(3)] for _ in range(3)]
    for r in range(9):
        for c in range(9):
            num = board[r][c]
            if num == 0:
                continue
            # Check if 'num' has been seen in the current row, column, or subgrid.
            if num in row_sets[r]:
                return False
            if num in column_sets[c]:
                return False
            if num in subgrid_sets[r // 3][c // 3]:
                return False
            # If we passed the above checks, mark this value as seen by adding it to
            # its corresponding hash sets.
            row_sets[r].add(num)
            column_sets[c].add(num)
            subgrid_sets[r // 3][c // 3].add(num)
    return True

Complexity Analysis

In this problem, the length of the board is fixed at 9, effectively reducing all approaches to a time and space complexity of O(1)O(1)O(1). However, to better understand the efficiency of our algorithm in a broader context, let's use nnn to denote the board's length, allowing us to evaluate the algorithm's performance against arbitrary board sizes.

Time complexity: The time complexity of verify_sudoku_board is O(n2)O(n^2)O(n2) because we iterate through each cell in the board once, and perform constant-time hash set operations.

Space complexity: The space complexity is O(n2)O(n^2)O(n2) due to the row_sets, column_sets, and subgrid_sets arrays. Each array contains nnn hash sets, and each hash set is capable of growing to a size of nnn.

Zero Striping

Zero Striping

For each zero in an m x n matrix, set its entire row and column to zero in place.

Intuition - Hash Sets

A brute-force solution involves recording the positions of all 0s initially in the matrix and, for each of these 0s, iterating over their row and column to set them to zero. However, imagine an input array that's filled with many zeros. In the worst case, iterating over every row and column for each zero will take O(m⋅n(m+n))O(m\cdot n(m+n))O(m⋅n(m+n)), where m⋅nm \cdot nm⋅n denotes the number of 0s, and (m+nm+nm+n) represents the total number of cells in a row and column combined. This approach is quite inefficient, so let’s look for a better solution.

Imagine any cell in the matrix. After the matrix is transformed, this cell will either retain its original value, or become zero. Is there a way to tell if a cell is going to become zero?

The key observation is that if a cell is in a row or column containing a zero, that cell will become zero.

We could search a cell’s row and column to check if they contain a zero, meaning each search would take O(m+n)O(m+n)O(m+n) time. But it would be more efficient if we had a way to check this in constant time, and this is where hash sets would be useful. If we create two hash sets – one to track all the rows containing a zero and another to track all the columns containing a zero – we can determine if a specific cell's row or column contains a zero in O(1)O(1)O(1) time.

With these hash sets created, the next step is to populate them. As we iterate through the matrix, when encountering a cell containing zero, we:

• Add its row index to the row hash set (zero_rows).
• Add its column index to the column hash set (zero_cols).

Next, we identify the cells whose row or column indexes are present in the respective hash sets, and change their values to zero. Let’s look at how this works with a few examples:

This provides a general strategy:

1. In one pass of the matrix, identify each cell containing a zero and add its row and column indexes to the zero_rows and zero_cols hash sets, respectively.
2. In a second pass, set any cell to zero if its row index is in zero_rows or its column index is in zero_cols.

Implementation - Hash Sets

from typing import List
    
def zero_striping_hash_sets(matrix: List[List[int]]) -> None:
    if not matrix or not matrix[0]:
        return
    m, n = len(matrix), len(matrix[0])
    zero_rows, zero_cols = set(), set()
    # Pass 1: Traverse through the matrix to identify the rows and columns
    # containing zeros and store their indexes in the appropriate hash sets.
    for r in range(m):
        for c in range(n):
            if matrix[r][c] == 0:
                zero_rows.add(r)
                zero_cols.add(c)
    # Pass 2: Set any cell in the matrix to zero if its row index is in 'zero_rows'
    # or its column index is in 'zero_cols’.
    for r in range(m):
        for c in range(n):
            if r in zero_rows or c in zero_cols:
                matrix[r][c] = 0

Complexity Analysis

Time complexity: The time complexity of zero_striping_hash_sets is O(m⋅n)O(m\cdot n)O(m⋅n) because we perform two passes over the matrix and perform constant-time operations in each pass.

Space complexity: The space complexity is O(m+n)O(m+n)O(m+n) due to the growth of the hash sets used to track zeros: one hash set scales with the number of rows, and the other scales with the number of columns. In the worst case, every row and column has a zero.

Intuition - In-place Zero Tracking

The previous solution was time efficient mainly due to the use of hash sets. However, this came at the cost of extra space used to store the hash set values. Is there an alternate way to keep track of which rows and columns contain a zero?

A key observation is that if a row or column contains a zero, all the cells in that row or column will be eventually replaced by zero. Therefore, there's no need to preserve the values in these rows or columns.

A strategy we can try is to use the first row and column (row 0 and column 0) as markers to track which rows and columns contain zeros.

To understand how this would work, consider the example below. For rows, we can use the first column to mark the rows that contain a zero. Specifically, this means if any cell in a row is zero, we set the corresponding cell in the first column to zero. This zero in the first column serves as a marker to indicate the entire row should eventually be set to zeros.

Similarly to how we marked rows, we can mark columns containing zeros using the first row:

To set markers for the first row and first column, we can begin searching the rest of the matrix, excluding the first row and first column, for any zero-valued cells. Let’s refer to this part of the matrix as the ‘submatrix.’ When we find a zero, we set the corresponding cell in the first row and column to zero. Scanning every cell in the submatrix for zeros allows us to set markers in the first row and first column:

Now, we should start converting cells in the submatrix to zeros based on their corresponding markers. We can assess any cell in the submatrix by checking:

• Whether its corresponding marker in the first column is zero.
• Whether its corresponding marker in the first row is zero.

If either of these conditions are met, we should set that cell’s value to zero, as shown below:

To update this submatrix, we can iterate from the second row and column and update cell values based on the logic we just mentioned:

Handling zeros in the first row and column After completing the previous step, there’s just one issue to address. What if the first row or column originally had a zero, like in the example below?

Here, we can’t distinguish which zero in the first row was originally present, or resulted from being used as a marker. This means we won’t know if the first row should be zeroed:

The remedy for this is to flag whether a zero exists in the first row or first column before using them as markers.

Once we've filled the first row and column with markers, as shown in matrix X below, and set the appropriate cell values in the submatrix to zero, as shown in matrix Y, we then evaluate the first row and column separately. The first row was initially marked as containing a zero, so we convert all cells in the first row to zero (matrix Z). The first column was not flagged for having a zero initially, so it remains unaltered at this step:

In-place zero-marking strategy Let's summarize the above approach into the following steps:

1. Use a flag to indicate if the first row initially contains any zero.
2. Use a flag to indicate if the first column initially contains any zero.
3. Traverse the submatrix, setting zeros in the first row and column to serve as markers for rows and columns that contain zeros.
4. Apply zeros based on markers: iterate through the submatrix that starts from the second row and second column. For each cell, check if its corresponding marker in the first row or column is marked with a zero. If so, set that element to zero.
5. If the first row was initially marked as containing a zero, set all elements in the first row to zero.
6. If the first column was initially marked as having a zero, set all elements in the first column to zero.

Implementation - In-place Zero Tracking

from typing import List
   
def zero_striping(matrix: List[List[int]]) -> None:
   if not matrix or not matrix[0]:
       return
   m, n = len(matrix), len(matrix[0])
   # Check if the first row initially contains a zero.
   first_row_has_zero = False
   for c in range(n):
       if matrix[0][c] == 0:
           first_row_has_zero = True
           break
   # Check if the first column initially contains a zero.
   first_col_has_zero = False
   for r in range(m):
       if matrix[r][0] == 0:
           first_col_has_zero = True
           break
   # Use the first row and column as markers. If an element in the submatrix is zero,
   # mark its corresponding row and column in the first row and column as 0.
   for r in range(1, m):
       for c in range(1, n):
           if matrix[r][c] == 0:
               matrix[0][c] = 0
               matrix[r][0] = 0
   # Update the submatrix using the markers in the first row and column.
   for r in range(1, m):
       for c in range(1, n):
           if matrix[0][c] == 0 or matrix[r][0] == 0:
               matrix[r][c] = 0
   # If the first row had a zero initially, set all elements in the first row to
   # zero.
   if first_row_has_zero:
       for c in range(n):
           matrix[0][c] = 0
   # If the first column had a zero initially, set all elements in the first column
   # to zero.
   if first_col_has_zero:
       for r in range(m):
           matrix[r][0] = 0

Complexity Analysis

Time complexity: The time complexity of zero_striping is O(m⋅n)O(m\cdot n)O(m⋅n). Here’s why:

• Checking the first row for zeros takes O(m)O(m)O(m) time, and checking the first column takes O(n)O(n)O(n) time.
• Then, we perform two passes of the entire matrix, one to mark 0s and another to update the matrix based on those markers. Each pass takes O(m⋅n)O(m\cdot n)O(m⋅n) time.
• Finally, we iterate through the first row and first column up to once each, which takes O(m)O(m)O(m) and O(n)O(n)O(n) time, respectively.

Therefore, the overall time complexity is O(m)+O(n)+O(m⋅n)=O(m⋅n)O(m)+O(n)+O(m\cdot n)=O(m\cdot n)O(m)+O(n)+O(m⋅n)=O(m⋅n).

Space complexity: The space complexity is O(1)O(1)O(1) because we use the first row and column as markers to track which rows and columns contain zeros, instead of using auxiliary data structures.

Longest Chain of Consecutive Numbers

Longest Chain of Consecutive Numbers

Find the longest chain of consecutive numbers in an array. Two numbers are consecutive if they have a difference of 1.

Example:

Input: nums = [1, 6, 2, 5, 8, 7, 10, 3]
Output: 4

Explanation: The longest chain of consecutive numbers is 5, 6, 7, 8.

Intuition

A naive approach to this problem is to sort the array. When all numbers are arranged in ascending order, consecutive numbers will be placed next to each other. This allows us to iterate through the array to identify the longest sequence of consecutive numbers.

This approach requires sorting, which takes O(nlog⁡(n))O(n\log (n))O(nlog(n)) time, where nnn denotes the length of the array. Let’s see how we could do better.

It’s important to understand that every number in the array can represent the start of some consecutive chain. One approach is to treat each number as the start of a chain and search through the array to identify the rest of its chain.

To do this, we can leverage the fact that for any number num, its next consecutive number will be num + 1. This means we’ll always know which number to look for when trying to find the next number in a sequence. The code snippet for this approach is provided below:

from typing import List
     
def longest_chain_of_consecutive_numbers_brute_force(nums: List[int]) -> int:
    if not nums:
        return 0
    longest_chain = 0
    # Look for chains of consecutive numbers that start from each number.
    for num in nums:
        current_num = num
        current_chain = 1
        # Continue to find the next consecutive numbers in the chain.
        while (current_num + 1) in nums:
            current_num += 1
            current_chain += 1
        longest_chain = max(longest_chain, current_chain)
    return longest_chain

This brute force approach takes O(n3)O(n^3)O(n3) time because of the nested operations involved:

• The outer for-loop iterates through each element, which takes O(n)O(n)O(n) time.
• For each element, the inner while-loop can potentially run up to n iterations if there is a long consecutive sequence starting from the current number.
• For each, while-loop iteration, an O(n)O(n)O(n) check is performed to see if the next consecutive number exists in the array.

This is slower than the sorting approach, but we can make a couple of optimizations to improve the time complexity. Let’s discuss these.

Optimization - hash set To find the next number in a sequence, we perform a linear search through the array. However, by storing all the numbers in a hash set, we can instead query this hash set in constant time to check if a number exists.

This reduces the time complexity from O(n3)O(n^3)O(n3) to O(n2)O(n^2)O(n2).

Optimization - identifying the start of each chain In the brute force approach, we treat each number as the start of a chain. This becomes quite expensive because we perform a linear search for every number to find the rest of its chain:

The key observation here is that we don’t need to perform this search for every number in a chain. Instead, we only need to perform it for the smallest number in each chain since this number identifies the start of its chain:

We can determine if a number is the smallest number in its chain by checking the array doesn’t contain the number that precedes it (curr_num - 1). We can also use the hash set for this check.

This reduces the time complexity from O(n2)O(n^2)O(n2) to O(n)O(n)O(n), as now every chain is searched through only once. This is explained in more detail in the complexity analysis.

Implementation

from typing import List
        
def longest_chain_of_consecutive_numbers(nums: List[int]) -> int:
    if not nums:
        return 0
    num_set = set(nums)
    longest_chain = 0
    for num in num_set:
        # If the current number is the smallest number in its chain, search for
        # the length of its chain.
        if num - 1 not in num_set:
            current_num = num
            current_chain = 1
            # Continue to find the next consecutive numbers in the chain.
            while current_num + 1 in num_set:
                current_num += 1
                current_chain += 1
            longest_chain = max(longest_chain, current_chain)
    return longest_chain

Complexity Analysis

Time complexity: The time complexity of longest_chain_of_consecutive_numbers is O(n)O(n)O(n) because, although there are two loops, the inner loop is only executed when the current number is the start of a chain. This ensures that each chain is iterated through only once in the inner while-loop. Thus, the total number of iterations for both loops combined is O(n)O(n)O(n): the outer for-loop runs nnn times, and the inner while-loop runs a total of nnn times across all iterations, resulting in a combined time complexity of O(n+n)=O(n)O(n+n)=O(n)O(n+n)=O(n).

Space complexity: The space complexity is O(n)O(n)O(n) since the hash set stores each unique number from the array.

Geometric Sequence Triplets

Geometric Sequence Triplets

A geometric sequence triplet is a sequence of three numbers where each successive number is obtained by multiplying the preceding number by a constant called the common ratio.

Let's examine three triplets to understand how this works:

• (1, 2, 4): This is a geometric sequence with a ratio of 2‾\underline{\text{2}}2​ (i.e., [1, 1⋅2‾\underline{\text{2}}2​ = 2, 2⋅2‾\underline{\text{2}}2​ = 4]).
• (5, 15, 45): This is a geometric sequence with a ratio of 3‾\underline{\text{3}}3​ (i.e., [5, 5⋅3‾\underline{\text{3}}3​ = 15, 15⋅3‾\underline{\text{3}}3​ = 45]).
• (2, 3, 4): Not a geometric sequence.

Given an array of integers and a common ratio r, find all triplets of indexes (i, j, k) that follow a geometric sequence for i < j < k. It's possible to encounter duplicate triplets in the array.

Example:

Input: nums = [2, 1, 2, 4, 8, 8], `r` = 2
Output: 5

Explanation:

• Triplet [2, 4, 8] occurs at indexes (0, 3, 4), (0, 3, 5), (2, 3, 4), (2, 3, 5).
• Triplet [1, 2, 4] occurs at indexes (1, 2, 3).

Intuition

For a triplet to form a geometric sequence, it has to adhere to two main rules:

1. It consists of three values that follow a geometric sequence with a common ratio r.
2. The three values forming the triplet must appear in the same order within the array as they do in the geometric sequence. This means for a geometric triplet (nums[i], nums[j], nums[k]), the indexes must follow the order i < j < k.

How can we represent a geometric sequence so that it follows rule 1? Let’s say the first number is x. The second number is the first number multiplied by r (i.e., x⋅r), and the third is the second number multiplied by r (i.e., x⋅r⋅r = x⋅r^2). So, a triplet in a geometric sequence can be represented as (x, x⋅r, x⋅r^2).

A brute force approach is to iterate over every possible triplet in the array and check if any of these triplets follow a geometric progression. However, it would take three nested for-loops to search through all the triplets, resulting in a time complexity of O(n3)O(n^3)O(n3), where nnn denotes the length of the input array. Can we do better?

An important observation here is that if we know one value of a triplet, we can calculate what the other two values should be.

This is because all three values are related by the common ratio r. So, for any number x in the array, we just need to find the values x⋅r and x⋅r^2 to form a geometric triplet (x, x⋅r, x⋅r^2). However, we could run into issues when using this triplet representation. While it’s clear the values x⋅r and x⋅r^2 must be positioned to the right of x, we have to be careful since the order of these values matters: we don’t want to accidentally identify a triplet such as (x, x⋅r^2, x⋅r), which is invalid:

We can work around this issue by using the (x/r, x, x⋅r) triplet representation, which allows us to always maintain order by looking for x/r to the left of x and x⋅r to the right:

One way we can find the x/r and x⋅r values is by linearly searching through the left and right subarrays. This linear search would need to be done for each number in the array, resulting in an O(n2)O(n^2)O(n2) time complexity. While this is an improvement from the brute force solution, it would be great if we had a way to find those values faster.

Hash maps A hash map would be a great way to solve this problem, as it allows us to query specific values in constant time.

What we would need are two hash maps:

• A hash map that contains numbers to the left of each x (left_map).
• A hash map that contains numbers to the right of each x (right_map).

Hash maps allow us to query for both x/r in the left hash map and query for x⋅r in the right hash map in constant time on average. Note that a hash map would be preferred over a hash set because hash maps can also store the frequency of each value it stores. This is crucial since the array might contain duplicates, and we need to know the frequency of each value to accurately identify all possible triplets.

Finding all (x/r, x, x⋅r) triplets Our goal is to find all triplets that follow a geometric sequence, representing each number in the array as the middle (x) number of a triplet.

Before we find a triplet’s x/r value, we need to check if x is divisible by r. If it’s not, it’s impossible to form a triplet from the current value of x. Otherwise, we can proceed to look for the triplet.

For any element x, there could be multiple instances of x/r in left_map and multiple instances of x⋅r in right_map, implying that multiple triplets can be formed using x as the middle value. So, to get the total number of triplets that can be formed with x in the middle, multiply the frequencies of x⋅r and x/r:

This overall methodology can be summarized in the following steps:

Note that if either x/r or x⋅r are not found in their hash maps, their frequency is 0 by default.

Let’s implement this strategy using the example below:

To ensure the hash maps always contain the correct values, we’d need to incorporate a dynamic strategy that involves updating the hash maps as we go because the values in both hash maps will be different depending on the position of x in the array.

Since we're traversing the array from left to right, we should initially fill the right hash map with all values in the array. This is because, before the start of the iteration, every element is a potential candidate for x⋅r. Meanwhile, the left hash map is initially empty because there are no preceding elements to consider as potential x/r values:

Now let’s look for triplets. Start by representing the first value as the middle value (x) of a triplet.

First, let’s update right_map. We should remove the current value (2) from right_map since this 2 is not to the right of itself. There are two 2’s in right_map, so let’s reduce its frequency to 1:

Next, check if x/r is an integer. In this case, it is, so let’s find the number of triplets with x as the middle number by multiplying the frequencies of x/r and x⋅r, which we can get from the respective hash maps. Since left_map doesn’t contain x/r at this point, its frequency is 0:

Before moving on to the next value, let’s add the current number to the left_map because it now becomes a potential x/r value for future triplets in the array:

Repeating this process for the rest of the array allows us to find all geometric triplets with a ratio of r. To clarify, the hash maps in the upcoming diagrams represent their state at the current position of x in the array. This means that left_map includes values to the left of the current x, and the right_map includes values to the right of it.

Implementation

from typing import List
from collections import defaultdict
    
def geometric_sequence_triplets(nums: List[int], r: int) -> int:
    # Use 'defaultdict' to ensure the default value of 0 is returned when
    # accessing a key that doesn’t exist in the hash map. This effectively sets
    # the default frequency of all elements to 0.
    left_map = defaultdict(int)
    right_map = defaultdict(int)
    count = 0
    # Populate 'right_map' with the frequency of each element in the array.
    for x in nums:
        right_map[x] += 1
    # Search for geometric triplets that have x as the center.
    for x in nums:
        # Decrement the frequency of x in 'right_map' since x is now being
        # processed and is no longer to the right.
        right_map[x] -= 1
        if x % r == 0:
            count += left_map[x // r] * right_map[x * r]
        # Increment the frequency of x in 'left_map' since it'll be a part of the
        # left side of the array once we iterate to the next value of `x`.
        left_map[x] += 1
    return count

Complexity Analysis

Time complexity: The time complexity of geometric_sequence_triplets is O(n)O(n)O(n) because we iterate through the nums array and perform constant-time hash map operations at each iteration.

Space complexity: The space complexity is O(n)O(n)O(n) because the hash maps can grow up to nnn in size.

Introduction to Linked Lists

Introduction to Linked Lists

Intuition

A linked list is a data structure consisting of a sequence of nodes, where each node is linked to the next. A node in a linked list has two main components: the data it stores (val) and a reference to the next node (next) in the sequence:

We define a node using the ListNode class, as below:

class ListNode:
   def __init__(self, val: int, next: ListNode):
       self.val = val
       self.next = next

Singly linked list

The simplest form of a linked list is a singly linked list, where each node points to the next node in the linked list, and the last node points to nothing (null), indicating the end of the linked list. The start of the linked list is called the ‘head,’ which is generally the only node we initially have immediate access to:

To access the other nodes in a linked list, we would need to traverse it starting at the head.

Singly linked lists can be used to store a collection of data. One of their main benefits lies in their dynamic sizing capability, since they can grow or shrink in size flexibly, unlike arrays which are fixed in size. Additionally, singly linked lists excel in scenarios requiring frequent insertions and deletions, as these operations can be performed more efficiently than in arrays, which need to shift elements to perform insertion or deletion.

The efficiency of these operations comes at the cost of the inability to perform random access, as nodes can’t be accessed by indexes like in an array. This trade-off may be acceptable in many use cases where the benefits of dynamic sizing and the efficiency of insertion/deletion outweigh the main performance benefits of random access.

Doubly linked list A doubly linked list is an extended version of the linked list where each node contains two references: one to the next node (next), and one to the previous node (prev). In most implementations, doubly linked lists have immediate access to both the head node and the tail node.

A big advantage of doubly linked list is that it allows for bidirectional traversal. Additionally, deleting nodes in a doubly linked list is generally more straightforward because we have references to both the next and previous nodes:

Pointer Manipulation

Many linked list interview problems require traversing or restructuring a linked list. Understanding and being proficient at pointer manipulation is essential to solving these problems. A useful tip is to visualize pointers as arrows that point from one node to another, and observe how these arrows should be moved to reflect the structural change. For example, this is how we would visualize a node insertion:

Real-world Example

Music Playlist: Music player applications often use linked lists to implement playlists, particularly doubly linked lists, where each song node links to the next and previous songs. This structure enables efficient addition, removal, and reordering of songs because only the pointers between nodes need to be updated, rather than moving the song data in memory.

Chapter Outline

In this chapter, we explore problems involving both singly and doubly linked lists. We also explore the unique challenge of restructuring a multi-level linked list.

Linked List Reversal

Linked List Reversal

Reverse a singly linked list.

Example:

Intuition - Iterative

A naive strategy is to store the values of the linked list in an array and reconstruct the linked list by traversing the array in reverse order. However, this solution does not reverse the original linked list; it just creates a new one. Could we try performing the reversal in place?

Let’s think about the problem in terms of pointer manipulation. The key observation here is that if we "flip" the direction of the pointers, we're effectively reversing the linked list:

Now, we just need to figure out how to perform this pointer manipulation. Consider the example below:

To reverse the direction of all pointers, we iterate through the nodes one by one. In this process, we need access to the current node (curr_node) and the previous node (prev_node) to adjust the current node's next pointer to the previous node. Note that prev_node will initially point at null since the first node has no previous node:

To reverse the next pointer, we'll need a way to shift the curr_node and prev_node pointers one node over. To shift prev_node, we can set it to the position of curr_node. However, we can't move curr_node to node 2 because we lost our reference to node 2:

This suggests we should have preserved a reference to node 2 before reversing the curr_node. This can be done by creating a variable next_node and setting it to curr_node.next. Let’s assume we did this. Now, we can advance prev_node and curr_node forward by one:

Note, we don't need to shift next_node, as it can be set by curr_node.next in the next iteration.

We can summarize this logic in three steps. At each node in the linked list:

1. Save a reference to the next node (next_node = curr_node.next).
2. Change the current node’s next pointer to link to the previous node (curr_node.next = prev_node).
3. Move both prev_node and curr_node forward by one (prev_node = curr_node,curr_node = next_node).

Let's repeat these steps for the rest of the linked list:

We can stop the reversal when curr_node becomes null, indicating there are no more nodes to reverse.

The final step is to return the head of the reversed linked list, which is pointed to by prev_node once curr_node becomes null.

Implementation - Iterative

from ds import ListNode
   
def linked_list_reversal(head: ListNode) -> ListNode:
    curr_node, prev_node = head, None
    # Reverse the direction of each node's pointer until 'curr_node' is null.
    while curr_node:
        next_node = curr_node.next
        curr_node.next = prev_node
        prev_node = curr_node
curr_node = next_node # 'prev_node' will be pointing at the head of the reversed linked list.
return prev_node

Complexity Analysis

Time complexity: The time complexity of linked_list_reversal is O(n)O(n)O(n), where nnn denotes the length of the linked list. This is because we perform constant-time pointer manipulation at each node of the linked list.

Space complexity: The space complexity is O(1)O(1)O(1).

Intuition - Recursive

Sometimes, the interviewer may want the problem solved using recursion. Let’s see what a recursive solution to this problem would look like.

In a recursive solution, the problem is solved by solving smaller instances of the same problem. To solve these smaller subproblems, we would need to use the linked list reversal function (linked_list_reversal) in its own implementation. The process of solving smaller problems using recursive calls continues until the smallest version of the problem is solved.

The smallest version of this problem involves reversing a linked list of size 0 or 1. These are linked lists which are inherently the same as their reverse. So, these can be our base cases.

With this in mind, let's try crafting the logic of the recursive function using the example below:

Think about which subproblem we should solve. To reverse the entire linked list, we can use our linked_list_reversal function to reverse the sublist after the current node. This way, we only need to focus on reversing the pointer of the current node. Let’s see how this works.

As mentioned, let’s first recursively call linked_list_reversal on the sublist starting at head.next. Let’s assume this recursive call reverses this sublist and returns its head as intended.

When designing a recursive function, assume any recursive call to that function will behave as intended, even if the function hasn’t been fully implemented.

Next, we need the tail of the reversed sublist (node 2) to point to node 1. We can reference node 2 using head.next. So, all we need to do is set head.next.next to head as illustrated below:

The linked list is almost fully reversed now, but node 1 is still pointing to node 2. To remove this link, just set head.next to null. Then, we can return new_head, which is the head of the reversed linked list:

Implementation - Recursive

from ds import ListNode
   
def linked_list_reversal_recursive(head: ListNode) -> ListNode:
    # Base cases.
    if (not head) or (not head.next):
        return head
    # Recursively reverse the sublist starting at the next node.
    new_head = linked_list_reversal_recursive(head.next)
    # Connect the reversed sublist to the head node to fully reverse the entire linked list.
    head.next.next = head
    head.next = None
    return new_head

Complexity Analysis

Time complexity: The time complexity of linked_list_reversal_recursive is O(n)O(n)O(n) because it involves a single recursive traversal through the linked list, visiting each node exactly once.

Space complexity: The space complexity is O(n)O(n)O(n) due to the stack space taken up by the recursive call stack, which grows up to nnn levels deep because nnn recursive calls are made.

Interview Tip

Tip: Visualize pointer manipulations. Often, it can be tricky to figure out exactly what to do when dealing with linked list manipulation. Drawing pointers as arrows between nodes can be quite helpful. By observing how these arrows should be reoriented to represent changes in the linked list's structure, we can deduce the necessary pointer manipulation logic. This approach also helps identify which nodes we need references to when making these changes.

Remove the Kth Last Node From a Linked List

Remove the Kth Last Node From a Linked List

Return the head of a singly linked list after removing the kth node from the end of it.

Example:

Constraints:

• The linked list contains at least one node.

Intuition

We can divide this problem into two objectives:

1. Find the position of the kth last node.
2. Remove this node.

Let’s first understand how node removal works. Consider the example below, where we need to remove node b. To do this, we need access to the node preceding it (node a), so we can redirect the pointer of node a to skip over node b. This ensures node b is no longer reachable through linked list traversal:

This indicates we need to find the node directly before the kth last node in order to remove it.

A naive solution to this problem is to first obtain the length of the linked list (n) by traversing it. Then, use this length to determine the number of steps required to arrive at the node before the kth last node, which is just n - k - 1 steps. This solution involves two for-loops, but is there a cleaner way to approach this problem?

The challenge with navigating a singly linked list in a single for-loop is that as we traverse, it’s hard to tell how far we are from the final node. The only way we’d know this is when we reach the final node itself, since its next node is null. How can we make use of this information?

Consider using two pointers instead of one. Could we create a scenario where, by the time one pointer reaches the end of the linked list, another pointer is positioned before the kth last node? Let’s explore this logic using the following example:

We denote the first pointer as leader and the pointer that follows it as trailer. When the leader pointer reaches the last node of the linked list, we want the trailer pointer to end up at node 4 (the node right before the kth last node) to prepare for deletion. In other words, the leader should be k nodes in front of the trailer when the leader reaches the last node.

To achieve this, we can start by advancing the leader pointer through the linked list for k steps. When the leader pointer is k nodes ahead of the trailer, we can advance both pointers together until the leader reaches the last node. This process will be explained in more detail soon.

However, there’s an important edge case to consider first: what if the head itself is the node we need to remove? In this case, there’s no node before the head, so we cannot perform the removal, as mentioned earlier. To circumvent this, we can create a dummy node, place it before the head node, and start our traversal from there.

Let’s now try incorporating our strategy into the example.

First, advance the leader pointer k (2) times so it’s k nodes ahead of the trailer pointer:

With the leader k nodes ahead, we can move both the trailer and leader pointers until the leader reaches the last node:

With the trailer pointer at the ideal position, we can remove node 7:

After this removal, we just return dummy.next, which points at the head of the modified linked list.

Implementation

from ds import ListNode
    
def remove_kth_last_node(head: ListNode, k: int) -> ListNode:
    # A dummy node to ensure there's a node before 'head' in case we need to remove
    # the head node.
    dummy = ListNode(-1)
    dummy.next = head
    trailer = leader = dummy
    # Advance 'leader' k steps ahead.
    for _ in range(k):
        leader = leader.next
        # If k is larger than the length of the linked list, no node needs to be
        # removed.
        if not leader:
            return head
    # Move 'leader' to the end of the linked list, keeping 'trailer' k nodes behind.
    while leader.next:
        leader = leader.next
        trailer = trailer.next
    # Remove the kth node from the end.
    trailer.next = trailer.next.next
    return dummy.next

Complexity Analysis

Time complexity: The time complexity of remove_kth_last_node is O(n)O(n)O(n). This is because the algorithm first traverses at most nnn nodes of the linked list, and then two pointers traverse the linked list at most once each.

Space complexity: The space complexity is O(1)O(1)O(1).

Linked List Intersection

Linked List Intersection

Return the node where two singly linked lists intersect. If the linked lists don't intersect, return null.

Example:

Output: Node 8

Intuition

Let’s first understand what an intersection between two linked lists is.

An intersection occurs when two linked lists converge at a shared node and, from that point onwards, share all subsequent nodes.

Note, this intersection has nothing to do with the values of the nodes.

A naive approach is to use a hash set. We can traverse the first linked list once and store each node in a hash set. Next, we traverse the second linked list until we find the first node that exists in the hash set, signifying the intersection point since it’s the first node shared between the two linked lists. This approach solves the problem linearly, but can we find a solution that uses constant space?

Consider the following example:

Treating these as two separate linked lists can get confusing with the above visualization. Instead, let’s visualize the input as two linked lists to help us think about the problem more clearly. Note that the tail nodes are still shared between the two linked lists, we’re just visualizing them separately:

Notice that this problem is easier to solve if the two linked lists are of equal length. This is because the intersection node can be found at the same position from the heads of both linked lists. In other words, when we iterate through two linked lists of the same length, we’re guaranteed to reach the intersection node at the same time:

Could we somehow replicate this behavior when dealing with linked lists of varying lengths? The key observation is that, while two linked lists ‘list A’ and ‘list B’ may have different lengths, ‘list A → list B’ has the same length as ‘list B → list A’ (where ‘→’ represents the connection of two lists). Conveniently, these combined linked lists also share the same tail nodes:

We’ve now set up a scenario where we have two combined linked lists of the same length, which share the same tail nodes. By traversing these combined linked lists, we’ll eventually reach the intersection node simultaneously on both linked lists (if one exists).

To do this, we can traverse both combined linked lists with two pointers, and stop once the nodes at both pointers are the same. This node would be the intersection node:

If no intersection exists, both pointers will end up stopping at null nodes:

Traversing combined linked lists An important observation is that to traverse through 'list A → list B', we don't actually need to connect these two linked lists together. Instead, we can traverse 'list A' and, upon reaching its end, continue by traversing 'list B':

This technique allows us to traverse the entire sequence of both linked lists as if they were connected.

Implementation

from ds import ListNode
   
def linked_list_intersection(head_A: ListNode, head_B: ListNode) -> ListNode:
    ptr_A, ptr_B = head_A, head_B
    # Traverse through list A with 'ptr_A' and list B with 'ptr_B' until they meet.
    while ptr_A != ptr_B:
        # Traverse list A -> list B by first traversing 'ptr_A' and then, upon
        # reaching the end of list A, continue the traversal from the head of list B.
        ptr_A = ptr_A.next if ptr_A else head_B
        # Simultaneously, traverse list B -> list A.
        ptr_B = ptr_B.next if ptr_B else head_A
    # At this point, 'ptr_A' and 'ptr_B' either point to the intersection node or both
    # are null if the lists do not intersect. Return either pointer.
    return ptr_A

Complexity Analysis

Time complexity: The time complexity of linked_list_intersection is O(n+m)O(n+m)O(n+m), where nnn and mmm denote the lengths of list A and B, respectively. This is because pointers linearly traverse both linked lists sequentially.

Space complexity: The space complexity is O(1)O(1)O(1).

LRU Cache

LRU Cache

Design and implement a data structure for the Least Recently Used (LRU) cache that supports the following operations:

• LRUCache(capacity: int): Initialize an LRU cache with the specified capacity.
• get(key: int) -> int: Return the value associated with a key. Return -1 if the key doesn't exist.
• put(key: int, value: int) -> None: Add a key and its value to the cache. If adding the key would result in the cache exceeding its size capacity, evict the least recently used element. If the key already exists in the cache, update its value.

Example:

Input: [
  put(1, 100),
  put(2, 250),
  get(2),
  put(4, 300),
  put(3, 200),
  get(4),
  get(1),
],
  capacity = 3
Output: [250, 300, -1]

Explanation:

put(1, 100)  # cache is[1: 100]
put(2, 250)  # cache is[1: 100, 2: 250]
get(2)       # return 250
put(4, 300)  # cache is[1: 100, 2: 250, 4: 300]t
put(3, 200)  # cache is[2: 250, 4: 300, 3: 200]
get(4)       # return 300
get(1)       # key 1 was evicted when adding key 3 due to the capacity
             # limit: return -1

Constraints:

• All keys and values are positive integers.
• The cache capacity is positive.

Intuition

When presented with a design problem, the first steps usually involve understanding the problem and deciding which data structures to use. Let's start by understanding how an LRU cache works at a high level.

Consider the LRU cache described below. It currently holds 3 elements and has reached full capacity. Assume that in this representation, the key-value pairs are ordered from the least recently used (left) to the most recently used (right):

Let's try putting a new key-value pair into the cache:

This new pair would effectively be the most recent in the cache, so we know it should be added at the most-recently-used end of the cache. Since the cache is currently at maximum capacity, we need to make room for the new pair by first evicting the least recently used pair:

From this high-level overview, we can summarize operations we need to implement the put function:

1. Remove a key-value pair from the least recently used end of the cache.
2. Add a key-value pair to the most recently used end of the cache.

Now, let's try retrieving a value from this example cache. If we perform get(2), we expect it to return 250. Accessing this pair would effectively make it the most recently used pair. So, we should move it to the most recently used end of the cache:

From this example, we identified two key operations for the get function:

1. Move a key-value pair to the most recent end of the cache.
2. Access a value using its key.

We’ve now narrowed the design down to the four main operations listed above. These will help us identify which data structures we can employ to design the LRU cache.

Choosing data structures Operations 1 and 2‾\underline{\text{Operations 1 and 2}}Operations 1 and 2​

The first two operations involve adding and removing key-value pairs. Specifically, we need the ability to remove a key-value pair from one end of a data structure (representing the least recently used end) and add a key-value pair to the other.

Which data structure allows us to efficiently add or remove an element from it? A suitable data structure for these operations is a linked list, particularly because we can add and remove a node in constant time if we have a reference to that node. But should we use a singly or doubly linked list?

Singly vs. doubly linked list‾\underline{\text{Singly vs. doubly linked list}}Singly vs. doubly linked list​

Adding or removing a node from the head of a linked list takes O(1)O(1)O(1) time, whether it’s a singly or doubly linked list. However, removing the tail node from a singly linked list takes O(n)O(n)O(n) time, even with a reference to the tail, because we need to traverse the list to access the node before the tail. In contrast, a doubly linked list allows O(1)O(1)O(1) removal of the tail because each node has a reference to its previous node, enabling direct access without traversal. So, let’s choose the doubly linked list.

An important feature we need is the ability to access both ends of the doubly linked list when adding or removing nodes. With this in mind, let's establish some definitions:

• The tail of the linked list signifies the most frequently used node.
• The head of the linked list signifies the least recently used node.

To reference the ends of the linked list, we can establish head and tail nodes, where head points to the least recently used node, and tail points to the most recently used node:

Operations 3 and 4‾\underline{\text{Operations 3 and 4}}Operations 3 and 4​

Operation 3 indicates that we’ll need to be able to move a node to the most recently-used end of the cache, and that this node doesn’t necessarily need to be at the head or tail of the linked list. If this node was somewhere in the middle, we’d need to traverse the linked list to find it. Is there a way we could access this node in O(1)O(1)O(1) time? Since this node is associated with a key, we could use a hash map to store key-node pairs. This allows us to access a node by its key in constant time. The diagram below illustrates how the hash map's values are references to nodes in the linked list:

Using a hash map also addresses operation 4 regarding efficient access to values from their keys.

Now we’ve decided on using a doubly linked list and a hash map to represent the LRU cache, let’s examine how the put and get functions would be implemented.

put(key: int, val: int) -> None: Below is the flow for adding a new key-value pair to the cache. This involves correctly updating the linked list and the hash map, while ensuring the cache does not exceed its capacity:

To better understand how to add a new node to a doubly linked list that’s at maximum capacity, check out the following example:

As you can see, we’ll need a function to remove a node (remove_node), as well as a function to add a node to the tail of the linked list (add_to_tail). We discuss these functions in more detail in the implementation section.

get(key: int) -> int: Below is the process for retrieving a key's value from the cache:

Now let’s take a look at an example of how the doubly linked list is updated during a get function call:

Now that we understand how the doubly linked list and hash map are used to design the LRU cache, let's dive into its implementation details, including the details of the helper methods remove_node and add_to_tail.

Implementation

We can use the custom class below to represent a node in a doubly linked list:

class DoublyLinkedListNode:
   def __init__(self, key: int, val: int):
       self.key = key
       self.val = val
       self.next = self.prev = None

The example below illustrates how to add a node to the tail of the linked list. Let's refer to the node before the tail as prev_node.

The new node should appear after prev_node and before the tail node. Let’s set the new node’s prev and next pointers to reflect this:

Now connect prev_node and tail to the new node:

Below is the implementation of this function:

def add_to_tail(self, node: DoublyLinkedListNode) -> None:
    prev_node = self.tail.prev
    node.prev = prev_node
    node.next = self.tail
    prev_node.next = node
    self.tail.prev = node

The example below illustrates how to remove a node from the doubly linked list:

To remove a node, we make its two adjacent nodes point at each other, effectively excluding the node to be removed from the linked list:

Below is the implementation of this function:

def remove_node(self, node: DoublyLinkedListNode) -> None:
    node.prev.next = node.next
    node.next.prev = node.prev

With the help of the above two functions, we can complete the full implementation of the LRU cache.

LRU Cache

class DoublyLinkedListNode:
    def __init__(self, key: int, val: int):
        self.key = key
        self.val = val
        self.next = self.prev = None
    
class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        # A hash map that maps keys to nodes.
        self.hashmap = {}
        # Initialize the head and tail dummy nodes and connect them to 
        # each other to establish a basic two-node doubly linked list.
        self.head = DoublyLinkedListNode(-1, -1)
        self.tail = DoublyLinkedListNode(-1, -1)
        self.head.next = self.tail
        self.tail.prev = self.head
    
    def get(self, key: int) -> int:
        if key not in self.hashmap:
            return -1
        # To make this key the most recently used, remove its node and
        # re-add it to the tail of the linked list.
        self.remove_node(self.hashmap[key])
        self.add_to_tail(self.hashmap[key])
        return self.hashmap[key].val
    
    def put(self, key: int, value: int) -> None:
        # If a node with this key already exists, remove it from the
        # linked list.
        if key in self.hashmap:
            self.remove_node(self.hashmap[key])
        node = DoublyLinkedListNode(key, value)
        self.hashmap[key] = node
        # Remove the least recently used node from the cache if adding
        # this new node will result in an overflow.
        if len(self.hashmap) > self.capacity:
            del self.hashmap[self.head.next.key]
            self.remove_node(self.head.next)
        self.add_to_tail(node)
    
    def add_to_tail(self, node: DoublyLinkedListNode) -> None:
        prev_node = self.tail.prev
        node.prev = prev_node
        node.next = self.tail
        prev_node.next = node
        self.tail.prev = node
    
    def remove_node(self, node: DoublyLinkedListNode) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev

Complexity Analysis

Time complexity: The time complexity for the helper functions remove_node and add_tail_node is O(1)O(1)O(1) because they perform constant-time operations on a doubly linked list. The put and get functions utilize these helper functions, while also performing constant-time hash map operations. Consequently, they also have an O(1)O(1)O(1) time complexity.

Space complexity: The overall space complexity of this solution is O(n)O(n)O(n), where nnn is the capacity of the cache. This is because both the doubly linked list and hash map can each occupy O(n)O(n)O(n) space.

Interview Tip

Tip: Explore how combining data structures can help achieve certain functionality. It’s possible to encounter situations where no single data structure provides the functionality required for your solution. In such cases, try to work out if this functionality can be achieved using a combination of data structures. For instance, in this problem we combined a doubly-linked list and a hash map to achieve the functionality required for the LRU cache.

Palindromic Linked List

Palindromic Linked List

Given the head of a singly linked list, determine if it's a palindrome.

Example 1:

Output: True

Example 2:

Output: False

Intuition

A linked list would be palindromic if its values read the same forward and backward. A naive way to check this would be to store all the values of the linked list in an array, allowing us to freely traverse these values forward and backward to confirm if it’s palindromic. However, this takes linear space. Instead, it would be better if we had a way to traverse the linked list in reverse order to confirm if it's a palindrome. Is there a way to go about this?

Going off the above definition, we know that if a linked list is a palindrome, reversing it would result in the same sequence of values.

This means we could create a copy of the linked list, reverse it, and compare its values with the original linked list. However, this would still take up linear space. Can we adjust this idea to avoid creating a new linked list?

An important observation is that we only need to compare the first half of the original linked list with the reverse of the second half (if there are an odd number of elements, we can just include the middle node in both halves) to check if the linked list is a palindrome:

Before we can perform this comparison, we need to:

1. Find the middle of the linked list to get the head of the second half.
2. Reverse the second half of the linked list from this middle node.

Notice that step 2 involves modifying the input. In this problem, let’s assume this is acceptable. However, it's always good to check with the interviewer if changing the input is allowed before moving forward with the solution.

Now, let’s see how these two steps can be applied. Start by obtaining the middle node (mid) of the linked list.

To learn how to get to the middle of a linked list, read the explanation in the Linked List Midpoint problem in the Fast and Slow Pointers chapter.

Then, reverse the second half of the linked list starting at mid. The last node of the original linked list becomes the head of the second half. This second head is used to traverse the newly reversed second half.

To learn how to reverse a linked list in O(n)O(n)O(n) time, read the explanation in the Reverse Linked List problem in this chapter.

The last thing we need to do is check if the first half matches the now-reversed second half. We can do this by simultaneously traversing both halves node by node, and comparing each node from the first half to the corresponding node from the second half. If at any point the node values don't match, it indicates the linked list is not a palindrome.

We can use two pointers (ptr1 and ptr2) to iterate through the first and the reversed second half of the linked list, respectively:

Implementation

from ds import ListNode
    
def palindromic_linked_list(head: ListNode) -> bool: 
    # Find the middle of the linked list and then reverse the second half of the # linked list starting at this midpoint.
    mid = find_middle(head)
    second_head = reverse_list(mid)
    # Compare the first half and the reversed second half of the list
    ptr1, ptr2 = head, second_head
    res = True
    while ptr2:
        if ptr1.val != ptr2.val:
            res = False
        ptr1, ptr2 = ptr1.next, ptr2.next
    return res
    
# From the 'Reverse Linked List' problem.
def reverse_list(head: ListNode) -> ListNode:
    prevNode, currNode = None, head
    while currNode:
        nextNode = currNode.next
        currNode.next = prevNode
        prevNode = currNode
        currNode = nextNode
    return prevNode
    
# From the 'Linked List Midpoint' problem.
def find_middle(head: ListNode) -> ListNode:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

Complexity Analysis

Time complexity: The time complexity of palindromic_linked_list is O(n)O(n)O(n), where nnn denotes the length of the linked list. This is because it involves iterating through the linked list three times: once to find the middle node, once to reverse the second half, and once more to compare the two halves.

Space complexity: The space complexity is O(1)O(1)O(1).

Interview Tip

Tip: Confirm if it’s acceptable to modify the linked list. In our solution, we reversed the second half of the linked list which dismantled the input’s initial structure. Why does this matter? Oftentimes, the input data structure should not be modified, particularly if it's shared or accessed concurrently. As such, it’s important to confirm with your interviewer whether input modification is acceptable and to briefly address the implications of this.

Flatten a Multi-Level Linked List

Flatten a Multi-Level Linked List

In a multi-level linked list, each node has a next pointer and child pointer. The next pointer connects to the subsequent node in the same linked list, while the child pointer points to the head of a new linked list under it. This creates multiple levels of linked lists. If a node does not have a child list, its child attribute is set to null.

Flatten the multi-level linked list into a single-level linked list by linking the end of each level to the start of the next one.

Example:

Intuition

Consider the two main conditions required to form the flattened linked list:

1. The order of the nodes on each level needs to be preserved.
2. All the nodes in one level must connect before appending nodes from the next level.

The challenge with this problem is figuring out how we process linked lists in lower levels. One strategy that might come to mind is level-order traversal using breadth-first search. However, breadth-first search usually involves the use of a queue, which would result in at least a linear space complexity. Is there a way we could merge the levels of the linked lists in place?

A key observation is that for any level of the multi-level linked list, we have direct access to all the nodes on the next level. This is because each node’s child node at any given level ‘L’ has direct access to nodes on the next level ‘L + 1’:

How can we connect the nodes on level ‘L + 1’ to the end of level ‘L’? Since we have access to the nodes at the next level from the current level’s child pointers, we can append each child linked list to the end of the current level, which effectively merges these two levels into one.

So, with all the nodes on level ‘L + 1’ appended to level ‘L’, we can continue this process by appending nodes from level ‘L + 2’ to level ‘L + 1’, and so on.

Now that we have a high-level idea about what we should do, let’s try this strategy on the following example:

We’ll start by appending level 2’s nodes to the end of level 1. Before we can do this, we would need a reference to level 1’s tail node so we can easily add nodes to the end of the linked list. To set this reference, we'll create a tail pointer and advance it through level 1's linked list until it reaches the last node, which happens when tail.next is equal to null:

Now, let’s add the child linked lists (5 → 6 and 7 → 8) to the tail node. We must keep the tail pointer fixed at the end of the linked list, so let’s introduce a separate pointer, curr, to traverse the linked list. Whenever curr encounters a node with a child node that isn’t null, we know we’ve found a child linked list. In the example, the first node (node 1) has a child linked list, which we want to add to the tail node:

To add this child linked list to the end of the tail node, set tail.next to the head of the child list:

Before incrementing curr to find the next node with a child linked list, we need to readjust the position of the tail pointer so it’s pointing at the last node of the newly extended linked list (node 6 in this case). Again, we can do this by iterating the tail pointer until its next node is null:

With the tail pointer now repositioned, we can continue this process of:

• Finding the next node with a child linked list using the curr pointer.
• Adding the child linked list to the tail node.
• Advancing the tail pointer to the last node of the flattened linked list.

After the process is complete, we can return head, which is the head of the flattened linked list.

One last important detail to mention is that after appending any child linked list to the tail, we should nullify the child attribute to ensure the linked list is fully flattened.

Implementation

The definition of the MultiLevelListNode class is provided below:

class MultiLevelListNode:
    def __init__(self, val, next, child):
        self.val = val
        self.next = next
        self.child = child

from ds import MultiLevelListNode
   
def flatten_multi_level_list(head: MultiLevelListNode) -> MultiLevelListNode:
    if not head:
        return None
    tail = head
    # Find the tail of the linked list at the first level.
    while tail.next:
        tail = tail.next
    curr = head
    # Process each node at the current level. If a node has a child linked list,
    # append it to the tail and then update the tail to the end of the extended linked
    # list. Continue until all nodes at the current level are processed.
    while curr:
        if curr.child:
            tail.next = curr.child
            curr.child = None
            while tail.next:
                tail = tail.next
        curr = curr.next
    return head

Complexity Analysis

Time complexity: The time complexity of flatten_multi_level_list is O(n)O(n)O(n), where nnn denotes the number of nodes in the multi-level linked list. This is because we iterate through each node in the multi-level linked list at most twice: once to iterate tail and once to iterate curr.

Space complexity: We only allocated a constant number of variables, so the space complexity is O(1)O(1)O(1).

Introduction to Fast and Slow Pointers

Introduction to Fast and Slow Pointers

Intuition

The fast and slow pointer technique is a specialized variant of the two-pointer pattern, characterized by the differing speeds at which two pointers traverse a data structure. In this technique, we designate a fast pointer and a slow pointer:

• Usually, the slow pointer moves one step in each iteration.
• Usually, the fast pointer moves two steps in each iteration.

This creates a dynamic in which the fast pointer moves at twice the speed of the slow pointer:

Keep in mind these pointers aren't limited to just one and two steps. As long as the fast pointer advances more steps than the slow pointer does, the logic of the fast and slow pointer technique still applies.

Real-world Example

Detecting cycles in symlinks: Symlinks are shortcuts that point to files or directories in a file system. A real-world example of using the fast and slow pointer technique is detecting cycles in symlinks.

In this process, the slow pointer follows each symlink one step at a time, while the fast pointer moves two steps at a time. If the fast pointer catches up to the slow pointer, it indicates a loop in the symlinks, which can cause infinite loops or errors when accessing files. To understand how fast and slow pointers detect cycles in this way, study the Linked List Loop problem.

Chapter Outline

Fast and slow pointers are particularly beneficial in data structures like linked lists, where index-based access isn't available. They allow us to gather crucial information about the data structure's elements through the relative positions of the two pointers, rather than with indexing. This will become clearer as we explore some common use cases in this chapter.

Linked List Loop

Linked List Loop

Given a singly linked list, determine if it contains a cycle. A cycle occurs if a node's next pointer references an earlier node in the linked list, causing a loop.

Example:

Output: True

Intuition

A straightforward approach is to iterate through the linked list while keeping track of the nodes that were already visited in a hash set. Encountering a previously-visited node during the traversal indicates the presence of a cycle. Below is the code snippet for this approach:

from ds import ListNode
    
def linked_list_loop_naive(head: ListNode) -> bool:
    visited = set()
    curr = head
    while curr:
        # Cycle detected if the current node has already been visited.
        if curr in visited:
            return True
        visited.add(curr)
        curr = curr.next
    return False

This solution takes O(n)O(n)O(n) time, where nnn is the number of nodes in the linked list, since each node is visited once. However, this comes at the cost of O(n)O(n)O(n) extra space due to the hash set. Is there a way to achieve a linear time complexity while using constant space?

Imagine a race track represented as a circular linked list (i.e., a linked list with a perfect cycle) where two runners start at the same node.

If both runners move at the same speed, they will always be together at each node. However, consider what happens when one runner (the slow runner) moves one step at a time, while the other runner (the fast runner) moves two steps at a time. In this scenario, the fast runner will overtake the slow runner at some point since the track is cyclic. But how can we use this information to detect a cycle?

In a linked list, detecting whether the fast runner has overtaken the slow runner is difficult due to the lack of positional indicators (like indexes in an array). A better way to find a cycle is to see if the fast runner reunites with the slow runner by both landing on the same node at some point. This would be a clear sign the linked list has a cycle.

The question now is, will the fast runner reunite with the slow runner, or is there a chance for the fast runner to consistently bypass the slow runner without ever converging on the same node? To answer this, let’s start by looking at some examples.

Perfect cycle First, let’s check whether the two runners, represented as a slow pointer and a fast pointer, will reunite in a linked list that forms a perfect cycle. As we can see from the figure below, the pointers will eventually meet.

Delayed cycle What about when the cycle doesn’t start immediately in the linked list? Consider simulating the fast and slow pointer technique over the following example:

Again, the pointers eventually met in the cycle despite the fact that fast and slow entered the cycle at different times.

Will fast always catch up with slow? In both cases, it might seem like the fast pointer could keep overtaking the slow pointer without ever meeting it, but this isn’t true. Here’s an easier way to understand why they will meet.

The fast pointer moves 2 steps at a time, and the slow pointer moves 1 step at a time, so the fast pointer will gain a distance of 1 node over the slow pointer at each iteration. This can be observed below, where the distance between the fast and slow pointers reduces by one in each iteration until they inevitably meet.

Therefore, the maximal number of steps required for the fast pointer to catch up with the slower pointer is k steps (once both are in the cycle), where k is the length of the cycle. In the worst case, the cycle will contain all the linked list’s nodes, and the pointers will eventually meet in n steps.

No cycle The final case is when there is no cycle. In this case, the fast pointer will eventually reach the end of the list and exit the while-loop:

Implementation

This algorithm is formally known as ‘Floyd's Cycle Detection’ algorithm [1].

from ds import ListNode
    
def linked_list_loop(head: ListNode) -> bool:
    slow = fast = head
    # Check both 'fast' and 'fast.next' to avoid null pointer exceptions when we
    # perform 'fast.next' and 'fast.next.next'.
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if fast == slow:
            return True
    return False

Complexity Analysis

Time complexity: The time complexity of linked_list_loop is O(n)O(n)O(n) because the fast pointer will meet the slow pointer in a linear number of steps, as described.

Space complexity: The space complexity is O(1)O(1)O(1).

Linked List Midpoint

Linked List Midpoint

Given a singly linked list, find and return its middle node. If there are two middle nodes, return the second one.

Example 1:

Output: Node 4

Example 2:

Output: Node 4

Constraints:

• The linked list contains at least one node.
• The linked list contains unique values.

Intuition

The most intuitive approach to solve this problem is to traverse the linked list to find its length (n), and then traverse the linked list a second time to find the middle node (n / 2):

This approach solves the problem in O(n)O(n)O(n) time, but requires two iterations to find the midpoint. However, there’s a cleaner approach that uses only a single iteration.

When iterating through the linked list, our exact position is unclear. We only know where we are when we reach the final node. Is it possible to create a scenario where, as soon as one pointer reaches the end of the linked list, the other pointer is positioned at the middle node?

If we had one pointer move at half the speed of the other, by the time the faster pointer reaches the end of the list, the slower one will be at the middle of the linked list.

We can achieve this by using the fast and slow pointer technique:

• Move a slow pointer one node at a time.
• Move a fast pointer two nodes at a time.

One thing we must be careful about is when we should stop advancing the fast pointer. We need to stop when the slow pointer reaches the middle node. When the list length is odd, this happens when fast.next equals null, as we can see above.

What about when the length of the linked list is even? Consider the below example:

As you can see, to have slow point at the second middle node, we'd need to stop fast when it reaches a null node.

Implementation

from ds import ListNode
    
def linked_list_midpoint(head: ListNode) -> ListNode:
    slow = fast = head
    # When the fast pointer reaches the end of the list, the slow pointer will be at
    # the midpoint of the linked list.
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

Complexity Analysis

Time complexity: The time complexity of linked_list_midpoint is O(n)O(n)O(n) because we traverse the linked list linearly using two pointers.

Space complexity: The space complexity is O(1)O(1)O(1).

Stop and Think

What if you were asked to modify your algorithm to return the first middle node when the linked list is of even length?

Answer: Following the same method, we should stop advancing the fast pointer when fast.next.next is null. This way, slow will end up pointing to the first middle node:

Interview Tip

Tip: Be prepared to address potential gaps in the information provided. During an interview, it’s possible the interviewer won't specify which middle node should be returned for linked lists of even length, leaving it up to you to recognize and address this special scenario. You might be expected to identify ambiguities like this and actively engage with the interviewer to discuss a suitable resolution.

Happy Number

Happy Number

In number theory, a happy number is defined as a number that, when repeatedly subjected to the process of squaring its digits and summing those squares, eventually leads to 1. An unhappy number will never reach 1 during this process, and will get stuck in an infinite loop [1].

Given an integer, determine if it's a happy number.

Example:

Input: n = 23
Output: True

Explanation: 222^222 + 323^232 = 13 ⇒ 121^212 + 323^232 = 10 ⇒ 121^212 + 020^202 = 1

Intuition

We can simulate the process of identifying a happy number by repeatedly summing the squares of each digit of a number, and then applying the same process to the resulting sum.

According to the problem statement, this process could conclude in one of two ways:

• Case 1: the process continues until the final number is 1.
• Case 2: the process gets stuck in an infinite loop.

If we diagram both scenarios, we observe something interesting:

This looks quite similar to a linked list problem. In particular, the problem of determining if a linked list has a cycle (case 2) or doesn’t (case 1).

We can reduce this problem to the same cycle detection challenge as the Linked List Loop problem. By applying the fast and slow pointer technique (i.e., Floyd's Cycle Detection algorithm), we can efficiently determine if a cycle exists.

However, in this problem, we don't have an actual linked list to perform the fast and slow pointer algorithm on. Therefore, we need to find a way to traverse the sequence of numbers generated in the happy number process.

Conveniently, we already know what the “next” number in the sequence is for any number x. As described in the problem statement, the next number can be calculated by summing the square of each digit of x. So, if each number were a node in a linked list, we could get the “next” node by calculating the next number in the sequence.

Getting the next number in the sequence To calculate the next number of x, we need a way to access each digit of x. This can be done in two steps:

1. The modulo operation (x % 10) is used to extract the last digit of a number x.
2. Divide x by 10 (x = x / 10) to truncate the last digit, positioning the next digit as the new last digit.

We can see this unfold in full below for x = 123:

Now that we have a way to traverse the sequence, we can implement Floyd’s Cycle Detection algorithm. To start, set the fast and slow pointers at the start of this sequence. Then move the pointers as follows:

• Advance the slow pointer one number at a time (slow = get_next_num(slow)).
• Advance the fast pointer two numbers at a time (fast = get_next_num(get_next_num(fast))).

If the fast and slow pointers meet during the process, it indicates the presence of a cycle, meaning the number is not a happy number. Otherwise, the algorithm will end when we reach 1, in which case the number is a happy number.

Implementation

def happy_number(n: int) -> bool:
    slow = fast = n
    while True:
        slow = get_next_num(slow)
        fast = get_next_num(get_next_num(fast))
        if fast == 1:
            return True
        # If the fast and slow pointers meet, a cycle is detected. Hence, 'n' is not
        # a happy number.
        elif fast == slow:
            return False
    
def get_next_num(x: int) -> int:
    next_num = 0
    while x > 0:
        # Extract the last digit of 'x'.
        digit = x % 10
        # Truncate (remove) the last digit from 'x' using floor division.
        x //= 10
        # Add the square of the extracted digit to the sum.
        next_num += digit ** 2
    return next_num

Complexity Analysis

Time complexity: The time complexity of happy_number is O(log⁡(n))O(\log(n))O(log(n)). The full analysis of this time complexity is quite complicated and beyond the scope of interviews. For interested readers, please see the detailed analysis below.

Space complexity: The space complexity is O(1)O(1)O(1).

Interview Tip

Tip: Visualize the problem. At first glance, this problem seems like it requires mathematical reasoning to solve. However, when we visualized the problem, we were able to formulate a solution using an algorithm we already know (Floyd’s Cycle Detection). Visualizing a problem can help uncover hidden patterns or data structures that can lead to the solution.

Happy Number Time Complexity Analysis

The following time complexity analysis establishes an upper bound on the steps required to determine a happy number. In this analysis, we define the "next number" of a number nnn as the result obtained by summing the squares of the digits of nnn.

1) Upper limit for the next number For any number nnn with a fixed number of digits, the maximum value for its successor is achieved when all its digits are 9. For instance, the maximum next number from a 3-digit number happens when this 3-digit number is 999.

2) Size of the next number relative to the number of digits

• If a number nnn has 1 or 2 digits, it’s possible for the next number to be larger than nnn (e.g., the next number of 99 is 162, which is one digit longer).
• If a number nnn has 3 or more digits, the next number is always smaller than the original value of nnn. The table below highlights how the largest number with 3 or more digits has a smaller next number.

3) Implications for cycles Since the next number is always smaller for numbers with three or more digits, it means a cycle can only commence in the happy number process once the number falls below 243 (the next number of 999). This is because we’ve observed that any number nnn larger than 243 will have the next number smaller than nnn. However, once we fall below 243, the next number can potentially be larger, potentially cycling back to a previous number.

4) Time complexity for numbers less than 243 Once a number falls below 243, the algorithm will take less than 243 steps to either converge to 1 or to cycle back to a previous number in the sequence. Therefore, since the length of the cycle or the number of steps to reach 1 is bounded by 243, the time complexity of Floyd’s cycle detection algorithm for numbers less than 243 is O(1)O(1)O(1).

5) Time complexity for numbers greater than 243 The number of digits in a number is approximately equal to log⁡(n)\log(n)log(n) (base 10). So, the calculation of the next number of nnn will take approximately log⁡(n)\log(n)log(n) steps (i.e., get_next_num will take log⁡(n)\log(n)log(n) steps to execute).

Let's call nnn’s next number n2n^2n2. The next number after n2n^2n2 (n3n^3n3) will take approximately log⁡(n2)\log(n^2)log(n2) steps to calculate. The next number after n3n^3n3 (n4n^4n4) will take approximately log⁡(n3)\log(n^3)log(n3) steps to calculate, and so on. From this, we can summarize the time complexity of this process as O(log⁡(n)+log⁡(n2)+log⁡(n3)+…)O(\log(n)+\log(n^2)+\log(n^3)+…)O(log(n)+log(n2)+log(n3)+…). Since we've established that n>n2>…>nkn>n^2>…>n^kn>n2>…>nk where nkn^knk is the last number greater than 243, the dominant component of this time complexity is O(log⁡(n))O(\log(n))O(log(n)). So, the time complexity for numbers greater than 243 is O(log⁡(n))O(\log(n))O(log(n)).

Conclusion When nnn is less than 243, the time complexity is O(1), and when nnn is greater than 243, the time complexity is O(log⁡(n))O(\log(n))O(log(n)). Therefore, the overall time complexity of the algorithm is O(log⁡(n))O(\log(n))O(log(n)).

Interview Tip

Tip: Don’t waste time on complex proofs if it isn’t an important part of the interview.

During an interview, correctly deciphering the exact time of an algorithm like the one used to solve this problem isn't usually expected. In situations like this, you can instead make an educated guess about how the algorithm's runtime would grow with larger inputs based on the behavior of the algorithm. Mention any assumptions you make when discussing your estimates. It might also be helpful to mention what parts of the problem or the solution make it difficult to analyze the time complexity. In this problem, it’s initially unclear how many steps the happy number process would take before reaching 1 or revealing a cycle.

Introduction to Sliding Windows

Introduction to Sliding Windows

Intuition

The sliding window technique is a subset of the two-pointer pattern, as it uses two pointers (generally left and right) to define the bounds of a "window" in iterable data structures like arrays. The window defines a subcomponent of the data structure (e.g., a subarray or substring), and it slides across the data structure unidirectionally, typically searching for a subcomponent that meets a certain requirement.

Sliding windows are particularly valuable in scenarios where algorithms might otherwise rely on using two nested loops to search through all possible subcomponents to find an answer, resulting in an O(n2)O(n^2)O(n2) time complexity, or worse. When using a sliding window, the subcomponent(s) we’re looking for can usually be found in O(n)O(n)O(n) time, in comparison. But before discussing how they work, let’s establish some terminology:

• To expand the window is to advance the right pointer:
• To shrink the window is to advance the left pointer:
• To slide the window is to advance both the left and right pointers: Note that sliding is equivalent to expanding and shrinking the window at the same time.

Now, let’s break down the two main types of sliding window algorithms:

1. Fixed sliding window.
2. Dynamic sliding window.

Fixed Sliding Window

A fixed sliding window maintains a specific length as it slides across a data structure.

We use the fixed sliding window technique when the problem asks us to find a subcomponent of a certain length. If we know what this length is, we can fix our window to that length and slide it through the array.

If a fixed window of length k traverses a data structure from start to finish, it’s guaranteed to see every subcomponent of length k in that data structure.

Below is a generic template of how a fixed sliding window traverses a data structure.

left = right = 0
while right < n:
    # If the window has reached the expected fixed length, we slide the window (move
    # both left and right).
    if right - left + 1 == fixed_window_size:
        # Process the current window.
        result = process_current_window()
        left += 1
    right += 1

Dynamic Sliding Window

Unlike fixed sliding windows, dynamic windows can expand or shrink in length as they traverse a data structure.

Generally, dynamic sliding windows can be applied to problems that ask us to find the longest or shortest subcomponent that satisfies a condition (for example, a condition could be that the numbers in the window must be greater than 10).

When finding the longest subcomponent, the dynamics of expanding and shrinking are typically as follows:

• If a window satisfies the condition, expand it to see if we can find a longer window that also meets the condition.
• If the condition is violated, shrink the window until the condition is met again.

Below is a generic template demonstrating how this works:

left = right = 0
while right < n:
    # While the condition is violated, the window is invalid, so shrink the window by
    # advancing the left pointer.
    while condition is violated:
        left += 1
    # Once the window is valid, process it and then expand the window by advancing the
    # right pointer.
    result = process_current_window()
    right += 1

Note that the provided templates for fixed and dynamic windows primarily emphasize the movement of the left and right pointers rather than the specifics of updating the window itself. If the problem requires updating the window, the logic around it will be highly context-dependent. This is explored in detail through specific problems in this chapter.

Real-world Example

Buffering in video streaming: In video streaming, a dynamic sliding window can be used to manage buffering and ensure smooth playback.

For instance, when streaming a video, the player downloads chunks of the video data and stores them in a buffer. A sliding window controls which part of the video is buffered, with the window "sliding" forward as the video plays. The sliding window ensures the video player can adapt to varying network conditions by dynamically adjusting the buffer size and position, leading to a smoother streaming experience for the viewer.

Chapter Outline

Substring Anagrams

Substring Anagrams

Given two strings, s and t , both consisting of lowercase English letters, return the number of substrings in s that are anagrams of t.

An anagram is a word or phrase formed by rearranging the letters of another word or phrase, using all the original letters exactly once.

Example:

Input: s = 'caabab', t = 'aba'
Output: 2

Explanation: There is an anagram of t starting at index 1 ("caabab") and another starting at index 2 ("caabab")

Intuition

We can reframe how we think about an anagram by altering the provided definition. A substring of s qualifies as an anagram of t if it contains exactly the same characters as t in any order.

For a substring in s to be an anagram of t, it must have the same length as t (denoted as len_t). This means we only need to consider substrings of s that match the length len_t, which saves us from examining every possible substring.

To examine all substrings of a fixed length, len_t, we can use the fixed sliding window technique because a window of len_t is guaranteed to slide through every substring of this length. We can see this in the example below:

Now, we just need a way to check if a window is an anagram of t. Remember that in an anagram, the order of the letters doesn’t matter; only the frequency of each letter does. By comparing the frequency of each character in a window against the frequencies of characters in string t, we can determine if that window is an anagram of t.

Let's explore this reasoning with an example. Before starting the sliding window algorithm, we need a way to store the frequencies of the characters in string t. We could use a hash map for this, or an array, expected_freqs, to store the frequencies of each character in string t.

expected_freqs is an integer array of size 26, with each index representing one of the lowercase English letters (0 for 'a', 1 for 'b', and so on, up to 25 for 'z').

To set up the sliding window algorithm, let’s define the following components:

• Left and right pointers: Initialize both at the start of the string to define the window's boundaries.
• window_freqs: Use an array of size 26 to keep track of the frequencies of characters within the window.
• count: Maintain a variable to count the number of anagrams detected.

Before we slide the window, we first need to expand it to a fixed length of len_t. This can be done by advancing the right pointer until the window length is equal to len_t. As we expand, ensure to keep window_freqs updated to reflect the frequencies of the characters in the window:

Once the window is at the fixed length of len_t, we can check if it’s an anagram of t by checking if the expected_freqs and window_freqs arrays are the same. This can be done in constant time since it requires only 26 comparisons, one for each lowercase English letter.

To slide this window across the string, advance both the left and right pointers one step in each iteration. Ensure to keep window_freqs updated by incrementing the frequency of each new character at the right pointer and decrementing the frequency of the character at the left pointer as we move past this left character:

Once we’ve finished processing all substrings of length len_t, we can return count, which represents the number of anagrams found.

A small optimization we can make is returning 0 if t's length exceeds the length of s because forming an anagram of t from the substrings of s is impossible if t is longer.

Implementation

In Python, we can use ord(character) - ord('a') to find the index of a lowercase English letter in an array of size 26. The ord function takes an integer and returns its ASCII value. This formula calculates the distance of this character from 'a', resulting in an index between 0 and 25.

def substring_anagrams(s: str, t: str) -> int:
    len_s, len_t = len(s), len(t)
    if len_t > len_s:
        return 0
    count = 0
    expected_freqs, window_freqs = [0] * 26, [0] * 26
    # Populate 'expected_freqs' with the characters in string 't'.
    for c in t:
        expected_freqs[ord(c) - ord('a')] += 1
    left = right = 0
    while right < len_s:
        # Add the character at the right pointer to 'window_freqs' before sliding the
        # window.
        window_freqs[ord(s[right]) - ord('a')] += 1
        # If the window has reached the expected fixed length, we advance the left
        # pointer as well as the right pointer to slide the window.
        if right - left + 1 == len_t:
            if window_freqs == expected_freqs:
                count += 1
            # Remove the character at the left pointer from 'window_freqs' before
            # advancing the left pointer.
            window_freqs[ord(s[left]) - ord('a')] -= 1
            left += 1
        right += 1
    return count

Complexity Analysis

Time complexity: The time complexity of substring_anagrams is O(n)O(n)O(n), where nnn denotes the length of s. Here’s why:

• Populating the expected_freqs array takes O(m)O(m)O(m) time, where m denotes the length of t. Since mmm is guaranteed to be less than or equal to nnn at this point, it’s not a dominant term in the time complexity.
• Then, we traverse string s linearly with two pointers, which takes O(n)O(n)O(n) time.
• Note that at each iteration, the comparison performed between the two frequency arrays (expected_freqs and window_freqs) takes O(1)O(1)O(1) time because each array contains only 26 elements.

Space complexity: The space complexity is O(1)O(1)O(1) because each frequency array contains only 26 elements.

Longest Substring With Unique Characters

Longest Substring With Unique Characters

Given a string, determine the length of its longest substring that consists only of unique characters.

Example:

Input: s = 'abcba'
Output: 3

Explanation: Substring "abc" is the longest substring of length 3 that contains unique characters ("cba" also fits this description).

Intuition

The brute force approach involves examining all possible substrings and checking if any consist of exclusively unique characters. Let’s break down this approach:

• Checking a substring for uniqueness can be done in O(n)O(n)O(n) time by scanning the substring and using a hash set to keep track of each character, where n denotes the length of s. If we encounter a character already in the hash set, we know it’s a duplicate character.
• Iterating through all possible substrings takes O(n2)O(n^2)O(n2) time.

This means the brute force approach would take O(n3)O(n^3)O(n3) time overall. This is quite slow, largely because we look through every substring. Is there a way to reduce the number of substrings we examine?

Sliding window Sliding window approaches can be quite useful for problems that involve substrings. In particular, because we’re looking for the longest substring that satisfies a specific condition (i.e., contains unique characters), a dynamic sliding window algorithm might be the way to go, as discussed in the introduction.

We can categorize any window in two ways. A window either:

1. Consists only of unique characters (a window with no duplicate characters).

1. Contains at least one character of a frequency greater than 1.

If A is true, we should expand the window by advancing the right pointer to find a longer window that also contains no duplicates.

If B is true because we encounter a duplicate character in the window, we should shrink the window by advancing the left pointer until it no longer contains a duplicate.

Let’s try this strategy over the following example. We initialize a hash set to keep track of the characters in a window.

To implement the sliding window technique, we should establish the following:

• Left and right pointers: Initialize both at the start of the string to define the window's boundaries.
• hash_set: Maintain a hash set to record the unique characters within the window, updating it as the window expands. Note, the hash set shown in the diagram displays its state before the character at the right pointer is added to it.

Now, let’s start looking for the longest window. Expand the window from the beginning of the string by advancing the right pointer. Keep expanding until a duplicate character is found:

We see above that the ‘b’ at index 3 is a duplicate character in the window because ‘b’ is already in the hash set.

Now that we found a duplicate, we should shrink the window by advancing the left pointer until the window no longer contains a duplicate ‘b’. Once the window is valid again, continue expanding:

Expanding the window any further will cause the right pointer to exceed the string’s boundary, at which point we end our search. The longest substring we’ve found with no duplicates is of length 3. We can use the variable max_len to keep track of this length during our search.

Implementation

def longest_substring_with_unique_chars(s: str) -> int:
    max_len = 0
    hash_set = set()
    left = right = 0
    while right < len(s):
        # If we encounter a duplicate character in the window, shrink the window until
        # it’s no longer a duplicate.
        while s[right] in hash_set:
            hash_set.remove(s[left])
            left += 1
        # Once there are no more duplicates in the window, update 'max_len' if the
        # current window is larger.
        max_len = max(max_len, right - left + 1)
        hash_set.add(s[right])
        # Expand the window.
        right += 1
    return max_len

Complexity Analysis

Time complexity: The time complexity of longest_substring_with_unique_chars is O(n)O(n)O(n) because we traverse the string linearly with two pointers.

Space complexity: The space complexity is O(m)O(m)O(m) because we use a hash set to store unique characters, where m represents the total number of unique characters within the string.

Optimization

The above approach solves the problem, but we can still optimize it. The optimization has to do with how we shrink the window when encountering a duplicate character. Consider the following example, where the right pointer encounters a duplicate ‘c’:

In the previous approach, we respond to encountering a duplicate by continuously advancing the left pointer to shrink the window until the window no longer contains a duplicate:

The crucial insight here is that we advanced the left pointer until it passed the previous occurrence of ‘c’ in the window. This indicates that if we know the index of the previous occurrence of ‘c’, we can move our left pointer immediately past that index to remove it from the window:

This gives us a new strategy for advancing the left pointer: if the right pointer encounters a character whose previous index (i.e., previous occurrence) is in the window, move the left pointer one index past that previous index.

We can use a hash map (prev_indexes) to store the previous index of each character in the string.

Now we just need to ensure the previous index of a character is in the window. To do this, we compare its index to the left pointer:

• If this index is after the left pointer, it’s inside the window.
• If it is before the left pointer, it’s outside the window

Below is a visual of how to check whether a character is inside the window:

Implementation - Optimized Approach

def longest_substring_with_unique_chars_optimized(s: str) -> int:
    max_len = 0
    prev_indexes = {}
    left = right = 0
    while right < len(s):
        # If a previous index of the current character is present in the current
        # window, it's a duplicate character in the window.
        if s[right] in prev_indexes and prev_indexes[s[right]] >= left:
            # Shrink the window to exclude the previous occurrence of this character.
            left = prev_indexes[s[right]] + 1
        # Update 'max_len' if the current window is larger.
        max_len = max(max_len, right - left + 1)
        prev_indexes[s[right]] = right
        # Expand the window.
        right += 1
    return max_len

Complexity Analysis

Time complexity: The time complexity of the optimized implementation is O(n)O(n)O(n) because we traverse the string linearly with two pointers.

Space complexity: The space complexity is O(m)O(m)O(m) because we use a hash map to store unique characters, where mmm represents the total number of unique characters within the string.

Longest Uniform Substring After Replacements

Longest Uniform Substring After Replacements

A uniform substring is one in which all characters are identical. Given a string, determine the length of the longest uniform substring that can be formed by replacing up to k characters.

Example:

Input: s = 'aabcdcca', k = 2
Output: 5

Explanation: if we can only replace 2 characters, the longest uniform substring we can achieve is "ccccc", obtained by replacing 'b' and 'd' with 'c'.

Intuition

Determining if a substring is uniform Before we try finding the longest uniform substring, let’s first determine the most efficient way to make a string uniform with the fewest character replacements. Consider the example below:

Which characters should we replace to ensure the minimum number of replacements are performed to make the string uniform? There are three main choices: make the string all ‘a’s, or all ‘b’s, or all ‘c’s. The most efficient choice, requiring the fewest replacements, is to make all characters ‘a’, which involves just three replacements:

The key observation is that the minimum number of replacements needed to achieve uniformity is obtained by replacing all characters except the most frequent one.

This suggests that if we know the highest frequency of a character in a substring, we can determine if our value of k is sufficient to make that substring uniform. The number of characters that need to be replaced (num_chars_to_replace) can be found by subtracting this highest frequency from the total number of characters in the substring:

Once we’ve calculated num_chars_to_replace for a given substring, we can assess if the substring can be made uniform:

• If num_chars_to_replace ≤ k, the substring can be made uniform.
• If num_chars_to_replace > k, the substring cannot be made uniform.

To calculate num_chars_to_replace, we need to know the value of highest_freq. This requires tracking the frequency of each character, which can be efficiently managed using a hash map (freqs). This hash map allows us to update highest_freq whenever we encounter a character with a higher frequency. Below is an illustration of how freqs is updated:

Now that we have the tools to determine if a substring can be made uniform, the next step is to figure out how to identify the longest uniform substring. Let’s explore a technique that lets us do this.

Dynamic sliding window We know sliding windows can be useful for solving problems involving substrings. This problem requires that we find the longest substring that satisfies a specific condition:

num_chars_to_replace <= k

So, a dynamic sliding window might be appropriate, as discussed in the chapter introduction.

We can use the above condition to determine how to expand or shrink the window:

• If the condition is met (i.e., the window is valid), we expand the window to find a longer window that still meets this condition.
• If the condition is violated (i.e., the window is invalid), we shrink the window until it meets the condition again.

Let’s see how this works over the example below:

Start by defining the left and right boundaries of the window at index 0. Continue expanding the window for as long as it satisfies our condition (nums_char_to_replace <= k):

Once the window expands to the fifth character (‘d’), it will contain 3 characters that must be replaced to make the window uniform. Since we can only replace up to k = 2 characters, the window is invalid. So, we shrink the window:

Notice that after shrinking the window, the value of highest_freq is still 2, which is no longer correct. Recall that our current method for updating highest_freq only increases it when encountering a character with a higher frequency, meaning highest_freq can only remain the same or increase, but it can never decrease.

One way to work around this is to develop a new method for updating highest_freq that accurately decreases it when the highest frequency in a window decreases. However, our goal is to find the longest substring that meets the condition, so shrinking the window might not even be necessary. The crucial point here is that when we find a valid window of a certain length, no shorter window will provide a longer uniform substring.

This means we can just slide the window instead of shrinking it whenever we encounter an invalid window, effectively maintaining the length of the current window.

With this observation, we should correct our previous logic:

• If the window satisfies the condition: expand.
• If the window doesn’t satisfy the condition: slide.

Let’s correct the action taken in the first invalid window above by sliding instead of shrinking. Then, we can continue processing the rest of the string.

The above window is the final window because we cannot expand or slide it any further. The longest valid window encountered during this process is a window of length 5.

Implementation

def longest_uniform_substring_after_replacements(s: str, k: int) -> int:
    freqs = {}
    highest_freq = max_len = 0
    left = right = 0
    while right < len(s):
        # Update the frequency of the character at the right pointer and the highest
        # frequency for the current window.
        freqs[s[right]] = freqs.get(s[right], 0) + 1
        highest_freq = max(highest_freq, freqs[s[right]])
        # Calculate replacements needed for the current window.
        num_chars_to_replace = (right - left + 1) - highest_freq
        # Slide the window if the number of replacements needed exceeds 'k'.
        # The right pointer always gets advanced, so we just need to advance 'left'.
        if num_chars_to_replace > k:
            # Remove the character at the left pointer from the hash map before
            # advancing the left pointer.
            freqs[s[left]] -= 1
            left += 1
        # Since the length of the current window increases or stays the same, assign
        # the length of the current window to 'max_len'.
        max_len = right - left + 1
        # Expand the window.
        right += 1
    return max_len

Complexity Analysis

Time complexity: The time complexity of longest_uniform_substring_after_replacements is O(n)O(n)O(n), where nnn is the length of the input string. This is because we traverse the string linearly with two pointers.

Space complexity: The space complexity is O(m)O(m)O(m), where mmm is the number of unique characters in the string stored in the hash map freqs.

Introduction to Binary Search

Introduction to Binary Search

Intuition

Let's say you have a standard, hard-copy English dictionary, and you want to find the definition of the word "inheritance." How could we do this?

One approach is to flick through it page by page, until reaching the page with "inheritance." But this is inefficient, and realistically, you're more likely to immediately open a page somewhere in the middle.

Let's say you do this and land on a page of words beginning with "M." Realizing that "inheritance" is somewhere to the left of "M" in the alphabet, you open a page somewhere between the letters "A" and "M." You continue this process of checking if "inheritance" is to the right or left of the current page, and narrowing the search down until you find the correct page. With this method, you've significantly reduced the number of pages to be searched, in contrast to linearly turning every page in order. This is the fundamental concept of binary search.

Implementing Binary Search

Binary search is an algorithm that searches for a value in a sorted data set.

Even experienced developers can find it quite tricky to implement binary search correctly because "the devil's in the detail."

• How should the boundary variables left and right be initialized?
• Should we use left < right or left ≤ right as the exit condition in our while-loop?
• How should the boundary variables be updated? Should we choose left = mid, left = mid + 1, right = mid, or right = mid - 1?

This chapter offers clear, intuitive guidance on how to master these challenges, and confidently handle even the trickiest edge case.

To begin any binary search implementation, do the following:

1. Define the search space.
2. Define the behavior inside the loop for narrowing the search space.
3. Choose an exit condition for the while-loop.
4. Return the correct value.

Let's break down these steps.

1. Defining the search space The search space encompasses all possible values that may include the value we're searching for. For instance, when searching for a target in a sorted array, the search space should cover the entire array, as the target could be anywhere within it. This is illustrated in the array below, where the left and right pointers define the search space:

2. Narrowing the search space Narrowing the search space involves progressively moving the left or right pointer inward until the search space is reduced to one element or none.

At each point in the binary search, we need to decide how we narrow our search space. We can either:

• Narrow the search space toward the left (by moving the right pointer inward):

• Narrow the search space toward the right (by moving the left pointer inward):

Using the midpoint We decide whether to move the left or right pointer based on the value in the middle of the search space, indicated by the midpoint variable (mid).

The main question to ask at each iteration of binary search is: is the value being searched for to the left or the right of the midpoint?

Here's the general idea: if the value we're looking for is to the right of the midpoint, narrow the search space toward the right. Otherwise, narrow the search space toward the left.

To narrow the search space towards the right, there are two options:

• left = mid + 1

We do this if the midpoint value is definitively not the value we're looking for and should excluded from the search space.

• left = mid We do this if the midpoint value itself could potentially be the value we're looking for and should still be included in the search space.

The exclude/include logic applies when narrowing the search space towards the left, as well (i.e., between right = mid - 1 and right = mid).

Calculating the midpoint In most cases, the midpoint is calculated using mid = (left + right) // 2 in Python.1 To lower the risk of integer overflow, mid = left + (right - left) // 2 is preferred in many other languages.

3. Choosing an exit condition Choosing an exit condition for when the while-loop should terminate can be tricky. Our choices are primarily between left < right and left ≤ right. Both conditions are applicable in different situations.

• When the exit condition is left < right, the while-loop will break when left and right meet.2
• On the other hand, left ≤ right ends once left has surpassed right.

When the left and right pointers meet after exiting the left < right condition, both converge to a single value. This is the final value in the search space after the binary search process is complete. This will be the exit condition we use throughout this chapter.

4. Returning the correct value As previously mentioned, the while-loop terminates once we've narrowed the search space down to a final value (assuming no value was returned during earlier iterations), pointed at by both left and right:

This final value is the answer we're looking for, assuming a valid answer exists.

Time Complexity

The time complexity of the binary search is O(log⁡(n))O(\log(n))O(log(n)), where nnn is the number of values in the search space. The algorithm is logarithmic because, in each iteration of the algorithm, it divides the search space in half until a single value is located, or no value is found. This reduction by half in each step is characteristic of logarithmic behavior.

Real-world Example

Transaction search in financial systems: In financial systems, a binary search can be used to quickly find a transaction or record by narrowing down the search range, as the data is typically stored in order. This makes it efficient to retrieve specific entries without searching through the entire database.

Chapter Outline

Binary search has many applications, and we explore a range of problems covering various uses.

Footnotes

1. In rare cases, we calculate the midpoint differently, such as when doing an upper-bound binary search. The details are explained in the First and Last Occurrences of a Number problem. ↩
2. There are some rare situations where left and right will cross, which is also explored in the First and Last Occurrences of a Number problem. ↩

Find the Insertion Index

Find the Insertion Index

You are given a sorted array that contains unique values, along with an integer target.

• If the array contains the target value, return its index.
• Otherwise, return the insertion index. This is the index where the target would be if it were inserted in order, maintaining the sorted sequence of the array.

Example 1:

Input: nums = [1, 2, 4, 5, 7, 8, 9], target = 4
Output: 2

Example 2:

Input: nums = [1, 2, 4, 5, 7, 8, 9], target = 6
Output: 4

Explanation: 6 would be inserted at index 4 to be positioned between 5 and 7: [1, 2, 4, 5, 6, 7, 8, 9].

Intuition

The goal of this problem varies depending on whether the sorted input array contains the target value or not. If it does, we should return its index. If it doesn’t, we return its insertion index.

When the target doesn’t exist in the array, we observe the insertion index is found at the first value in the array greater than the target, as can be seen in the second diagram above, where the first value larger than the target of 6, is 7.

Since we don’t know if the target exists in the array before we start looking for it, we can combine both cases by finding the first value greater than or equal to the target. This gives us a universal objective regardless of whether the target is in the array or not.

As the array is sorted, we can use binary search to find the desired index.

Binary search In this binary search, we’re effectively looking for the first value that matches a condition, where the condition is that the number is greater than or equal to the target. Let’s visualize which values of the array meet this condition and which don’t:

From this diagram, we can see the value we want to find is effectively the lower bound of values that satisfy this condition:

Note that finding the lower bound is equivalent to finding the leftmost value. With this in mind, let’s come up with an algorithm.

First, define the search space. If the target exists in the array, it could be located at any index within the range from 0 to n - 1. However, if the target is not in the array and is larger than all the elements, its insertion index is n. Therefore, our search space should cover all indexes in the range [0, n].

To figure out how we narrow the search space, let’s first explore an example array that contains the target, then dive into an example where the array doesn’t contain the target.

Target exists in the array Consider searching for target value 4 in the following sorted array.

Initially, the midpoint is positioned at element 5, which is a number that satisfies our condition of being greater than or equal to the target. This means the lower bound is either at this midpoint, or to its left since the lower bound is the leftmost value that satisfies the condition.

So, narrow the search space toward the left, while including the midpoint (i.e., right = mid):

Now, the midpoint is positioned at element 2. The lower bound should be a value greater than or equal to the target (4), which means the current midpoint is too small. To look for a larger value, we need to search to the right of the midpoint.

So, narrow the search space toward the right while excluding the midpoint:

Now, the midpoint is positioned at element 4, which satisfies the condition of being greater than or equal to the target. So, narrow the search space toward the left while including the midpoint:

Once the left and right pointers meet, the lower bound is located, which is the first value greater than or equal to the target. Now, we just return left to return this value’s index.

Target doesn’t exist in the array Let’s test the above logic in the following example where the target is not in the array:

As we can see, by the end of the binary search, we’ve narrowed down the search space to a single value, identifying index 4 as the insertion index. Return left.

Summary For clarity, let’s summarize the two main scenarios we encounter while narrowing down the search space.

Case 1: The midpoint value is greater than or equal to the target, indicating the lower bound is either at the midpoint, or to its left. In this case, we narrow the search space toward the left, ensuring the midpoint is included:

Case 2: The midpoint value is less than the target, indicating the lower bound is somewhere to the right. In this case, we narrow the search space toward the right, ensuring the midpoint is excluded:

Implementation

from typing import List
    
def find_the_insertion_index(nums: List[int], target: int) -> int:
    left, right = 0, len(nums)
    while left < right:
        mid = (left + right) // 2
        # If the midpoint value is greater than or equal to the target, the lower
        # bound is either at the midpoint, or to its left.
        if nums[mid] >= target:
            right = mid
        # The midpoint value is less than the target, indicating the lower bound is
        # somewhere to the right.
        else:
            left = mid + 1
    return left

Complexity Analysis

Time complexity: The time complexity of find_the_insertion_index is O(log⁡(n))O(\log(n))O(log(n)) because it performs a binary search over a search space of size n+1n+1n+1.

Space complexity: The space complexity is O(1)O(1)O(1).

First and Last Occurrences of a Number

First and Last Occurrences of a Number

Given an array of integers sorted in non-decreasing order, return the first and last indexes of a target number. If the target is not found, return [-1, -1] .

Example 1:

Input: nums = [1, 2, 3, 4, 4, 4, 5, 6, 7, 8, 9, 10, 11],
       target = 4
Output: [3, 5]

Explanation: The first and last occurrences of number 4 are indexes 3 and 5, respectively.

Intuition

A brute-force solution to this problem involves a linear search to find the first and last occurrences of the target number. However, since the array is sorted, we can try searching for these two occurrences using binary search.

The challenge of using binary search here is that we need to find two separate occurrences of the same number. This means that a standard binary search alone isn’t sufficient.

To help us find a solution, it’s important to understand that the problem is effectively asking us to find the lower and upper bound of a number in the array:

This indicates we can solve this problem in two main steps:

1. Perform a binary search to find the lower bound of the target.
2. Perform a binary search to find the upper bound of the target.

Lower-bound binary search To find the start position of the target, let’s first define the search space. The target could be anywhere in the array, so the search space should encompass all the array’s indexes.

Next, let’s figure out how to narrow the search space. At each point in the binary search, there are three conditions to consider based on the midpoint value:

• when it's greater than the target
• when it's less than the target
• when it’s equal to the target

In each of these cases, think about where the target is in relation to the midpoint. Note that we’re effectively looking for the leftmost occurrence of the target value.

Midpoint value is greater than the target If the midpoint value is greater, it means the target is to the left of this number. So, narrow the search space toward the left.

When we do this, we can exclude the midpoint from the search space (i.e., right = mid - 1) because its value is not equal to the target:

Midpoint value is less than the target If the midpoint value is smaller, it means the target is to the right of this number. So, narrow the search space toward the right. Again, we can exclude the midpoint from the search space (i.e., left = mid + 1) because its value is not equal to the target:

Midpoint value is equal to the target Now is when things get interesting. When the midpoint value is equal to the target, there are two possibilities:

1. This is the lower bound of the target value.
2. This is not the lower bound, so the lower bound is somewhere further to the left.

We don’t know which possibility is true at the moment, so we should narrow the search space toward the left to continue looking for the lower bound, while also including the midpoint itself in the search space (i.e., right = mid).

Continue this reasoning for the next midpoint as it’s also equal to the target:

The final value, once the left and right pointers meet, is the lower bound of the target.

Upper-bound binary search There’s a lot of similarity between this and lower-bound binary search. For starters, the search space is identical. Additionally, the cases when the midpoint value is greater than or less than the target are handled the same. This makes sense because, in both binary searches, we’re seeking the same target value. So, when the midpoint value is not equal to the target, the actions we take will be the same as the actions taken in the lower-bound binary search.

The difference in logic occurs when the midpoint is equal to the target, as we’re now looking for the rightmost value of the target, instead of the leftmost value. As such, let’s just focus on the logic for when the midpoint value is equal to the target.

Midpoint value is equal to the target Similar to lower-bound binary search, there are two possibilities: either this is the upper bound, or it’s not. Again, we’re not sure which is true. So, let’s narrow the search space toward the right to continue looking for an upper bound while including the midpoint in the search space (i.e., left = mid):

When we continue this logic for the next midpoint values, we notice something peculiar happen:

It looks like we just got stuck in an infinite loop, where the position of the left pointer keeps getting set to mid when they’re both at the same index. Why does this happen?

Debugging the infinite loop When the left and right pointers are directly next to each other, mid ends up being positioned where the left pointer is:

Since one of our operations is left = mid, we get stuck in an infinite loop where left and mid are continuously set to each other’s positions, which means progress cannot be made. The reason this wasn’t a problem during lower-bound binary search was that we never had left = mid as an operation in the logic. One way to avoid this issue is by biasing the midpoint to the right.

When the midpoint is biased to the right, we avoid an infinite loop during upper-bound binary search.

• We no longer need to worry about the left pointer since mid is now being positioned at the right pointer when the search space has two elements.
• We won’t encounter any infinite loops with the right pointer because it never gets set to the midpoint’s position, as we use right = mid - 1.

A right bias of the midpoint can be achieved using mid = (left + right) // 2 + 1:

Now, performing left = mid allows us to properly narrow the search space.

As a general rule, in upper-bound binary search, we should bias mid to the right.

Let’s apply this change to the same example and see what happens:

As we can see, we’ve avoided an infinite loop, with the left and right pointers meeting at the upper bound of the target.

If the target doesn’t exist The last step in both algorithms is to check that the final values located are equal to the target. If the target does not exist in the array, the final values in both binary search algorithms won’t be equal to the target. In this case, we should return -1.

Implementation

from typing import List
    
def first_and_last_occurrences_of_a_number(nums: List[int], target: int) -> List[int]:
    lower_bound = lower_bound_binary_search(nums, target)
    upper_bound = upper_bound_binary_search(nums, target)
    return [lower_bound, upper_bound]
    
def lower_bound_binary_search(nums: List[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > target:
            right = mid - 1
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left if nums and nums[left] == target else -1
    
def upper_bound_binary_search(nums: List[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    while left < right:
        # In upper-bound binary search, bias the midpoint to the right.
        mid = (left + right) // 2 + 1
        if nums[mid] > target:
            right = mid - 1
        elif nums[mid] < target:
            left = mid + 1
        else:
            left = mid
    # If the target doesn’t exist in the array, then it's possible that
    # 'left = mid + 1' places the left pointer outside the array when `mid == n - 1`.
    # So, we use the right pointer in the return statement instead.
    return right if nums and nums[right] == target else -1

Complexity Analysis

Time complexity: The time complexity of both the lower_bound_binary_search and upper_bound_binary_search helper functions is O(log⁡(n))O(\log(n))O(log(n)), where nnn is the length of the input array. This is because each function performs a binary search over the entire array. Therefore, first_and_last_occurrences_of_a_number is also O(log⁡(n))O(\log(n))O(log(n)) because it calls each helper function once.

Space complexity: The space complexity is O(1)O(1)O(1).

Interview Tip

Tip: Always test your algorithm. Binary search can be a tricky algorithm to implement. The best way to uncover unexpected errors is to test your code. The infinite loop encountered during the upper-bound binary search problem is quite easy to miss while designing the algorithm. If you're unable to recognize this issue during implementation, manual testing can help reveal it. In binary search, an infinite loop can be uncovered when testing a search space that contains just two elements, similar to what we did in the explanation.

Cutting Wood

Cutting Wood

You are given an array representing the heights of trees, and an integer k representing the total length of wood that needs to be cut.

For this task, a woodcutting machine is set to a certain height, H. The machine cuts off the top part of all trees taller than H, while trees shorter than H remain untouched. Determine the highest possible setting of the woodcutter (H) so that it cuts at least k meters of wood.

Assume the woodcutter cannot be set higher than the height of the tallest tree in the array.

Example:

Input: heights = [2, 6, 3, 8], k = 7
Output: 3

Explanation: The highest possible height setting that yields at least k = 7 meters of wood is 3, which yields 8 meters of wood. Any height setting higher than this will yield less than 7 meters of wood.

Constraints:

• It's always possible to attain at least k meters of wood.
• There's at least one tree.

Intuition

At first, it might strike you as strange that this problem is in the Binary Search chapter. The given input array isn't necessarily sorted, so how is binary search applicable here? Well, this is an example of a common application of binary search, where the search space does not encompass the input array.

Let’s consider a visualization of four trees of heights [2, 6, 3, 8] and assume k = 7:

The tallest tree above has a height of 8. So the height setting, H, can be set to any height between 0 and 8.

• The most amount of wood is cut at H = 0, where all trees are cut from the bottom.
• The least amount of wood is cut at H = 8, where no wood is cut at all.

Gradually increasing the height setting of the woodcutter from H = 0 to H = 8 yields less and less wood, and our goal is to find the highest value of H that gives us at least k meters of wood.

Determining if a height setting yields enough wood We need a function that determines if any given height setting H yields at least k meters of wood.

Let’s name this function cuts_enough_wood(H, k), which will calculate the total wood obtained by cutting the trees taller than H, and return true if this total meets or exceeds k. Below is a visual representation of how to determine if a height setting of 3 yields enough wood in the example:

Applying this function to all possible values of H (from 0 to 8) gives us the outcome below, where heights 0 to 3 yield at least k meters of wood and heights 4 to 8 are too high and don’t yield enough. Note that here, we visualize which H values make the function cuts_enough_wood return true, and which will result in false.

We could call cuts_enough_wood on each value of H from 0 to 8 until we reach the highest value that still causes cuts_enough_wood to return true. However, a key observation is that the above sequence of boolean outcomes is effectively a sorted sequence, since all true outcomes are positioned before false ones.

As this is a sorted sequence, we should try using binary search.

Binary search The goal is to find the last value of H that cuts at least k meters of wood. In other words, we’re looking for the upper bound value of H that satisfies this condition.

As such, we should use upper-bound binary search. This means we’ll need to calculate the midpoint using mid = (left + right) // 2 + 1, as mentioned in the First and Last Occurrences of a Number problem.

Let’s first define the search space. Our search space should encompass all values of H between 0 and the height of the tallest tree in the array, as these are all possible answers.

To figure out how to narrow the search space, let's use the example below, setting left and right pointers at the ends of the search space:

Initially, the midpoint is set to H = 4. When we call cuts_enough_wood(4, k), it returns false. This means the height setting is not yielding enough wood and is, hence, set too high. To find a lower height setting, we should narrow our search space toward the left:

The next midpoint is set to H = 2. When we call cuts_enough_wood(2, k), it returns true. This means the upper bound is either at the midpoint or to its right, as the upper bound is the rightmost height setting that cuts enough wood.

So, narrow the search space toward the right while including the midpoint:

The next midpoint is set to H = 3. When we call cuts_enough_wood(3, k), it returns true. So, narrow the search space toward the right while including the midpoint:

Once the left and right pointers meet, we have located the upper bound height setting that yields at least k meters of wood.

Summary Case 1: The midpoint is set at a height that allows us to cut at least k meters of wood, indicating the upper bound is somewhere to the right. Narrow the search space to the right while including the midpoint:

Case 2: The midpoint is at a height that doesn’t allow us to cut enough wood, indicating the upper bound is somewhere to the left. Narrow the search space to the left while excluding the midpoint:

Implementation

from typing import List
    
def cutting_wood(heights: List[int], k: int) -> int:
    left, right = 0, max(heights)
    while left < right:
        # Bias the midpoint to the right during the upper-bound binary search.
        mid = (left + right) // 2 + 1
        if cuts_enough_wood(mid, k, heights):
            left = mid
        else:
            right = mid - 1
    return right
    
# Determine if the current value of 'H' cuts at least 'k' meters of wood.
def cuts_enough_wood(H: int, k: int, heights: List[int]) -> bool:
    wood_collected = 0
    for height in heights:
        if height > H:
            wood_collected += (height - H)
    return wood_collected >= k

Complexity Analysis

Time complexity: The time complexity of cutting_wood is O(nlog⁡(m))O(n\log(m))O(nlog(m)), where mmm is the maximum height of the trees. This is because we perform a binary search over the range [0, mmm]. Each iteration of the binary search calls the cuts_enough_wood function, which runs in O(n)O(n)O(n) time, where nnn is the number of trees. This results in an overall time complexity of O(log⁡(m))O(n)=O(nlog⁡(m))O(\log(m))O(n)=O(n\log(m))O(log(m))O(n)=O(nlog(m)).

Space complexity: The space complexity is O(1)O(1)O(1).

Find the Target in a Rotated Sorted Array

Find the Target in a Rotated Sorted Array

A rotated sorted array is an array of numbers sorted in ascending order, in which a portion of the array is moved from the beginning to the end. For example, a possible rotation of [1, 2, 3, 4, 5] is [3, 4, 5, 1, 2] , where the first two numbers are moved to the end.

Given a rotated sorted array of unique numbers, return the index of a target value. If the target value is not present, return -1.

Example:

Input: nums = [8, 9, 1, 2, 3, 4, 5, 6, 7], target = 1
Output: 2

Intuition

A naive solution is to iterate through the input array until we find the target number. This strategy takes linear time, and doesn’t take into account that the input is a rotated sorted array. Given the array was sorted before it was rotated, we should figure out how binary search might be useful in finding the target.

First, let’s define the search space for the binary search. Since the target value could exist anywhere in the array, the search space should encompass the entire array.

Now, let’s figure out how to narrow the search space, which is an interesting challenge considering the array isn’t perfectly sorted. Let’s work through this by exploring an example:

Let’s set left and right pointers at the boundaries of the array and consider the first midpoint value:

In a normal sorted array, we’d be able to logically assess whether to search to the left or the right of the midpoint, based solely on the midpoint value and the target. In a rotated sorted array, it’s much less straightforward to determine which side the target value is on.

To decide whether to narrow the search space toward the left or right of the midpoint, let’s visualize the height of each number in the array and pay attention to subarrays [left : mid] and [mid : right] separately. Note, we include the midpoint in both subarrays since the midpoint is used to decide which subarray to narrow the search space towards:

Here, we see the subarray [mid : right] is sorted in ascending order. Since it’s sorted, we know what the smallest and largest numbers in that range are: 3 and 7, respectively. This means we can check if the target is in this subarray by checking if it’s in between 3 and 7. The target (1) is not in this range, so therefore, it must be in the left subarray.

So, we should narrow the search space toward the left, excluding the midpoint (right = mid - 1):

The reason we excluded the midpoint value was because it wasn’t equal to the target, and so should no longer be considered in the search space.

Let’s continue with the example.

This time, the sorted subarray is the left subarray, [left : mid]. So, we can use this subarray to check where the target value is. Since the target (1) doesn't fall within the range between 8 and 9, it indicates the target resides in the right subarray. Therefore, we narrow our search space toward the right, excluding the midpoint (left = mid + 1):

Again, we excluded the midpoint value (9) as it was not equal to the target.

Finally, we’ve found the target at the midpoint, so we can return its index (mid):

Summary From our discussion above, an important strategy emerges: between the two subarrays, [left : mid] and [mid : right], we can use the sorted one to determine where the target is.

Before examining the subarrays, let’s first compare the target with the value at the midpoint. If they match, we've found our target at mid. If not, then we decide where to adjust our search depending on which subarray is sorted, as detailed in the following two test cases:

Case 1: the left subarray, [left : mid], is sorted

• If the target falls in the range of this left subarray, we narrow the search space toward the left.
• Otherwise, we narrow the search space toward the right.

Case 2: the right subarray, [mid : right] is sorted

• If the target falls in the range of this right subarray, we narrow the search space toward the right.
• Otherwise, narrow the search space toward the left.

It’s possible to encounter a situation where both subarrays are sorted. In this case, it doesn’t matter which subarray we use to check where the target is.

One final thing to note is that the array might not contain the target value at all. In this case, once the binary search terminates and narrows down to a single value, we need to check if this value is the target. If not, it indicates the target is not present in the array, and we return -1.

Implementation

from typing import List
    
def find_the_target_in_a_rotated_sorted_array(nums: List[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        # If the left subarray [left : mid] is sorted, check if the target falls in
        # this range. If it does, search the left subarray. Otherwise, search the
        # right.
        elif nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # If the right subarray [mid : right] is sorted, check if the target falls
        # in this range. If it does, search the right subarray. Otherwise, search the
        # left.
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    # If the target is found in the array, return it’s index. Otherwise, return -1.
    return left if nums and nums[left] == target else -1

Complexity Analysis

Time complexity: The time complexity of find_the_target_in_a_rotated_sorted_array is O(log⁡(n))O(\log(n))O(log(n)) because we're performing a binary search over an array of length nnn.

Space complexity: The space complexity is O(1)O(1)O(1).

Find the Median From Two Sorted Arrays

Find the Median From Two Sorted Arrays

Given two sorted integer arrays, find their median value as if they were merged into a single sorted sequence.

Example 1:

Input: nums1 = [0, 2, 5, 6, 8], nums2 = [1, 3, 7]
Output: 4.0

Explanation: Merging both arrays results in [0, 1, 2, 3, 5, 6, 7, 8], which has a median of (3 + 5) / 2 = 4.0.

Example 2:

Input: nums1 = [0, 2, 5, 6, 8], nums2 = [1, 3, 7, 9]
Output: 5.0

Explanation: Merging both arrays results in [0, 1, 2, 3, 5, 6, 7, 8, 9], which has a median of 5.

Constraints:

• At least one of the input arrays will contain an element.

Intuition

The brute force approach to this problem involves merging both arrays and finding the median in this merged array. This approach takes O((m+n)log⁡(m+n))O((m+n)\log(m+n))O((m+n)log(m+n)) time where mmm and nnn denote the lengths of each array, respectively. This complexity is primarily due to the cost of sorting the merged array of length m+nm+nm+n. This approach can be improved to O(m+n)O(m+n)O(m+n) time by merging both arrays in order, which is possible because both arrays are already sorted. However, is there a way to find the median without merging the two arrays?

In this explanation, we use "total length" to refer to the combined length of both input arrays. Let's discuss odd and even total lengths separately, as these result in two different types of medians.

Consider the following two arrays that have an even total length:

Below is what these two arrays would look like when merged. Let's see if we can draw any insights from this.

Observe that the merged array can be divided into two halves, which reveals the median values on the inner edge of each half.

A challenge here is identifying which values in either input array belongs to the left half of the merged array, and which belong to the right half. One thing we do know is the size of each half of the merged array: half of the total length.

Slicing both arrays To figure out which values belong to each half, we can try "slicing" both arrays into two segments, where the left segments of both arrays and the right segments of both arrays each have 4 total values. Let's refer to the values on the left and right of the slice as the "left partition" and "right partition." Below are three examples of what this slice could look like:

As we can see, there are several ways to slice the arrays to produce two partitions of equal size (4). However, only one of these slices corresponds to the halves of the merged array. In our example, it's this slice:

Let's refer to this as the "correct slice." We'll explain how to identify the correct slice shortly, but first, let's consider how to identify which slice correctly corresponds to the halves of the merged array.

Determining the correct slice

An important observation is that all values in the left partition must be less than or equal to the values in the right partition.

We can assess this by comparing the two end values of the left partition with the start values of the right partition (illustrated below). Let's refer to the end values of the left partition as L1 and L2, respectively. Similarly, let's call the start values of the right partition R1 and R2.

Since the values in each array are sorted, we know that conditions L1 ≤ R1 and L2 ≤ R2 are always true. Then, all we have to do is check that L1 ≤ R2 and L2 ≤ R1. We can observe how this comparison reveals the correct slice from the previous three example slices:

Notice that in the third example above, the second array does not contribute any values to the left partition. So, to work around this, we set the second array's left value to - so that L2 ≤ R1 is true by default.

Searching for the correct slice Now, our goal is to search through all possible slices until we find the correct one. We do this by searching through all possible placements of L1, R1, L2, and R2. Note that we only need to search for L1 since the other three values can be inferred based on L1's index.

Let's take a closer look at how this works. Once we identify L1's index, we can calculate L2's index based on L1's index, which is demonstrated in the diagram below. R1 and R2 are just the values immediately to the right of L1 and L2, respectively.

Since we search for L1 over nums1, which is a sorted array, we can use binary search instead of searching for it linearly. The search space will encompass all values of the nums1.

Let's figure out how to narrow the search space. Here, we'll define the midpoint as L1_index, since it's also the index of L1. Let's discuss how the search space is narrowed based on these conditions:

• If L1 > R2, then L1 is larger than it should be because we expect L1 to be less than or equal to R2. To search for a smaller L1, narrow the search space toward the left:
• If L2 > R1, then R1 is smaller than it should be because we expect R1 to be less than or equal to L2. To search for a larger R1, narrow the search space toward the right:
• If L1 ≤ R2, and L2 ≤ R1, the correct slice has been located:

Search space optimization A small optimization here is to ensure that nums1 is the smallest array between the two input arrays. This ensures our search space is as small as possible. If nums2 is smaller than nums1, we can just swap the two arrays, allowing nums1 to always be the smaller array.

Returning the median Once binary search has identified the correct slice, we need to return the median. With an even total length, the median is calculated using the array's two middle values. From our set of partition slice values (L1, R1, L2, and R2), which of them are the middle two? We know one of the median values is from the left partition and the other is from the right partition. From the left partition, the largest value between L1 and L2 will be closest to the middle. From the right, the smallest value between R1 and R2 is closer to the middle:

So, to return the median, we just return the sum of these two values, divided by 2 using floating-point division.

What if the total length of both arrays is odd? The main difference when the total length of both arrays is odd compared to an even length is that we can no longer slice the arrays into two equal halves. One half must have an additional value.

The diagram above shows that the right half ends up with one extra value. This is because when we calculate the slice position, we ensure the left half has a size of half the total length. In this example, this calculation using integer division gives us a left half size of (5 + 4) // 2 = 4. Consequently, this means the right half ends up with 5 values. When the total length is odd, the median can be found in the right half:

So, after the binary search narrows down the correct slice, we can just return the smallest value between R1 and R2.

Implementation

from typing import List
   
def find_the_median_from_two_sorted_arrays(nums1: List[int], nums2: List[int]) -> float:
    # Optimization: ensure 'nums1' is the smaller array.
    if len(nums2) < len(nums1):
        nums1, nums2 = nums2, nums1
    m, n = len(nums1), len(nums2)
    half_total_len = (m + n) // 2
    left, right = 0, m - 1
    # A median always exists in a non-empty array, so continue binary search until
    # it's found.
    while True:
        L1_index = (left + right) // 2
        L2_index = half_total_len - (L1_index + 1) - 1
        # Set to -infinity or +infinity if out of bounds.
        L1 = float('-inf') if L1_index < 0 else nums1[L1_index]
        R1 = float('inf') if L1_index >= m - 1 else nums1[L1_index + 1]
        L2 = float('-inf') if L2_index < 0 else nums2[L2_index]
        R2 = float('inf') if L2_index >= n - 1 else nums2[L2_index + 1]
        # If 'L1 > R2', then 'L1' is too far to the right. Narrow the search space
        # toward the left.
        if L1 > R2:
            right = L1_index - 1
        # If 'L2 > R1', then 'L1' is too far to the left. Narrow the search space
        # toward the right.
        elif L2 > R1:
            left = L1_index + 1
        # If both 'L1' and 'L2' are less than or equal to both 'R1' and 'R2', we
        # found the correct slice.
        else:
            if (m + n) % 2 == 0:
                return (max(L1, L2) + min(R1, R2)) / 2.0
            else:
                return min(R1, R2)

Complexity Analysis

Time complexity: The time complexity of find_the_median_from_two_sorted_arrays is O(log⁡(min(m,n)))O(\log(min(m,n)))O(log(min(m,n))) because we perform binary search over the smaller of the two input arrays.

Space complexity: The space complexity is O(1)O(1)O(1).

Note: this explanation refers to the two middle values as "median values" to keep things simple. However, it's important to understand that these two values aren't technically "medians," as there's only ever one median. These are just the two values used to calculate the median.

Matrix Search

Matrix Search

Determine if a target value exists in a matrix. Each row of the matrix is sorted in non-decreasing order, and the first value of each row is greater than or equal to the last value of the previous row.

Example:

Output: True

Intuition

A naive solution to this problem is to linearly scan the matrix until we encounter the target value. However, this isn’t taking advantage of the sorted properties of the matrix.

A key observation is that all values in a given row are greater than or equal to all values in the previous row. This indicates the entire matrix can be considered as a single, continuous, sorted sequence of values:

If we were able to flatten this matrix into a single, sorted array, we could perform a binary search on the array. Creating a separate array and populating it with the matrix’s values still takes O(m⋅n)O(m\cdot n)O(m⋅n) time, and also takes O(m⋅n)O(m\cdot n)O(m⋅n) space, where mmm and nnn are the dimensions of the matrix. Is there a way to perform a binary search on the matrix without flattening it?

Let’s map the indexes of the flattened array to their corresponding cells in the matrix:

This index mapping would give us a way to access the elements of the matrix in a similar way to how we would access them in the flattened array. To figure out how to do this, let’s find a way to map any cell (r, c) to its corresponding index in the flattened array.

Let’s start by examining the mapped indexes of each row of the matrix:

• Row 0 starts at index 0.
• Row 1 starts at index n.
• Row 2 starts at index 2n.

From the above observations, we see a pattern: for any row r, the first cell of the row corresponds to the index r⋅n.

When we also consider the column value c, we can conclude that for any cell (r, c), the corresponding index in the flattened array is r⋅n + c.

Now that we understand how the 2D matrix maps to the 1D flattened array, let’s work backward to obtain the row and column indexes from an index in the flattened array. Let i = r⋅n + c. The row and column values are:

• r = i // n
• c = i % n

We can see how these are obtained below:

Now that we have these formulas, let’s use binary search to find the target.

Binary search To define the search space, we need the first and last indexes of the flattened array. The first index is 0, and the last index is m⋅n - 1. So, we set the left and right pointers to 0 and m⋅n - 1 respectively.

To figure out how to narrow the search space, let’s explore an example matrix that contains the target of 21.

We can calculate mid using the formula: mid = (left + right) // 2. Then, determine the corresponding row and column values. Here, the value at the midpoint (10) is less than the target, which means the target is to the right of the midpoint. So, let’s narrow the search space toward the right:

The new midpoint value is still less than the target, so let’s narrow the search space towards the right:

The midpoint value is now larger than the target, which means the target is to the left of the midpoint. So, let’s move the search space to the left:

Now, the midpoint is equal to the target, so we return true to conclude the search.

Note that our exit condition should be while left ≤ right in order to also examine the above search space when left == right.

Implementation

from typing import List
    
def matrix_search(matrix: List[List[int]], target: int) -> bool:
    m, n = len(matrix), len(matrix[0])
    left, right = 0, m * n - 1
    # Perform binary search to find the target.
    while left <= right:
        mid = (left + right) // 2
        r, c = mid // n, mid % n
        if matrix[r][c] == target:
            return True
        elif matrix[r][c] > target:
            right = mid - 1
        else:
            left = mid + 1
    return False

Complexity Analysis

Time complexity: The time complexity of matrix_search is O(log⁡(m⋅n))O(\log(m\cdot n))O(log(m⋅n)) because it performs a binary search over a search space of size m⋅nm\cdot nm⋅n.

Space complexity: The space complexity is O(1)O(1)O(1).

Local Maxima in Array

Local Maxima in Array

A local maxima is a value greater than both its immediate neighbors. Return any local maxima in an array. You may assume that an element is always considered to be strictly greater than a neighbor that is outside the array.

Example:

Input: nums = [1, 4, 3, 2, 3]
Output: 1 # index 4 is also acceptable

Constraints:

• No two adjacent elements in the array are equal.

Intuition

A naive way to solve this problem is to linearly search for a local maxima by iteratively comparing each value to its neighbors and returning the first local maxima we find. A linear solution isn't terrible, but since we can return any maxima, there’s likely a more efficient approach.

The first important thing to notice is that since this is an array with no adjacent duplicates, it will always contain at least one local maxima. If it's not at one of the edges of the array, there'll be at least one somewhere in the middle:

Now, let's say we're at some random index in the array, index i. An interesting observation is that if the next number (at index i + 1) is greater than the current, there’s definitely a local maxima somewhere to the right of i. This is because the two points at index i and i + 1 form an ascending slope, and this slope would be heading upwards towards some maxima:

The opposite applies if points i and i + 1 form a descending slope. This would imply a maxima exists somewhere to the left or at i. Notice here that the point at index i itself could be a maxima too:

Once we know whether a local maxima exists to the left or to the right, we can continue searching in that direction until we find it. In other words, we narrow our search toward the direction of the maxima. Doesn't this type of reasoning sound similar to how we narrow search space in a binary search? This indicates that it might be possible to find a local maxima using binary search.

Binary search First, let’s define the search space. A local maxima could exist at any index of the array. So, the search space should encompass the entire array.

To figure out how we narrow the search space, let’s use the below example, setting left and right pointers at the boundaries of the array:

The midpoint is initially set at index 3, which forms a descending slope with its right neighbor since nums[mid] > nums[mid + 1]. This suggests that either a maxima exists to the left of index 3 or that index 3 itself is a maxima). So, we should continue our search to the left, while including the midpoint in the search space:

The next midpoint is set at index 1, which forms an ascending slope with its right neighbor since nums[mid] < nums[mid + 1]. This suggests that a maxima exists somewhere to the right of the midpoint. So, let’s continue the search to the right, while excluding the midpoint:

The next midpoint is set at index 2, which forms a descending slope with its right neighbor. So, we continue by searching to the left, while including the midpoint:

Now that the left and right pointers have met, locating index 2 as a local maxima, we return this maxima’s index (left).

Summary Case 1: The midpoint forms a descending slope with its right neighbor, indicating the midpoint is a local maxima, or that a local maxima exists to the left. Narrow the search space toward the left while including the midpoint:

Case 2: The midpoint forms an ascending slope with its right neighbor, indicating a local maxima exists to the right. Narrow the search space toward the right while excluding the midpoint:

Implementation

from typing import List
    
def local_maxima_in_array(nums: List[int]) -> int:
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[mid + 1]:
            right = mid
        else:
            left = mid + 1
    return left

Complexity Analysis

Time complexity: The time complexity of local_maxima_in_array is O(log⁡(n))O(\log(n))O(log(n)), where nnn denotes the length of the array. This is because we use binary search to find a local maxima.

Space complexity: The space complexity is O(1)O(1)O(1).

Weighted Random Selection

Weighted Random Selection

Given an array of items, each with a corresponding weight, implement a function that randomly selects an item from the array, where the probability of selecting any item is proportional to its weight.

In other words, the probability of picking the item at index i is: weights[i] / sum(weights).

Return the index of the selected item.

Example:

Input: weights = [3, 1, 2, 4]

Explanation: sum(weights) = 10 3 has a 3/10 probability of being selected. 1 has a 1/10 probability of being selected. 2 has a 2/10 probability of being selected. 4 has a 4/10 probability of being selected. For example, we expect index 0 to be returned 30% of the time.

Constraints:

• The weights array contains at least one element.

Intuition

A completely uniform random selection implies every index has an equal chance of being selected. A weighted random selection means some items are more likely to be picked than others. If we repeatedly perform a random selection many times, the frequency of each index being picked will match their expected probabilities.

The challenge with this problem is determining a method to randomly select an index based on its probability.

Let’s say we had weights 1 and 4 for indexes 0 and 1, respectively:

Here, index 1 should be selected with a probability of 4/5, significantly higher than index 0’s probability of 1/5:

A useful observation is that all probabilities have the same denominator (which is 5 in this case). Now, imagine we had a line with the same length as this denominator, and we divided this line into two segments of size 1 and 4, respectively:

If we were to randomly pick a number on this line, we’d pick the first segment with a probability of 1/5 and the second segment 4/5 times. Now, imagine index 0 represents the first segment, and index 1 represents the second segment:

If we randomly select a number on this line, we’ll select index 0 with a probability of 1/5, and index 1 with a probability of 4/5. This reflects their expected probabilities.

What we need now is a way to identify which numbers on the number line correspond to which index so that when we pick a random number on this line, we know which index to return.

Before we continue, let’s establish the definitions of terms used in this explanation:

• “Weights” refers to the values of the elements in the weights array.
• “Indexes” refers to the indexes of the weights array.
• “Numbers” or “numbers on the number line” refers to the numbers from 1 to sum(weights).

Determining which numbers on the number line correspond to which indexes As mentioned before, to know which index to return, we need a way to tell which index our random number line number corresponds to. Consider a larger distribution of weights:

One strategy is to use a hash map. In this hash map, each number on the line is a key, and its corresponding index is the value:

This method uses a lot of space because we need to store a key-value pair for each number on the number line. Let's consider some other more space-efficient methods.

A more efficient strategy is to store only the endpoints of each segment instead.

Naturally, the endpoint of a segment marks where that segment ends. It also helps us know where the next segment begins, as each new segment starts right after the previous one ends. This way, we can determine the start and end of each index’s segment.

By storing only the endpoints, we need to keep just n values, one for each endpoint. When storing these endpoints in an array, the array index of each endpoint is the same as its index value on the number line:

The question now is, how do we find these endpoints?

Obtaining the endpoints of each index’s segment on the line A key observation is that the endpoint of a segment is equal to the length of all previous segments, plus the length of the current segment. We can see how this works below:

This demonstrates that each endpoint is a cumulative sum, suggesting we can obtain the endpoint of each segment by obtaining the prefix sums of the array of weights:

As we can see, the prefix sums array stores the endpoint of each segment.

Now, let's see how the prefix sums array helps us. When we pick a random number from 1 to 10, we need to determine which index it corresponds to using the prefix sum array. Let's see how we can do this.

Using the prefix sums to determine which numbers correspond to which indexes Let’s say we pick a random number from 1 to 10 and get 5. How can we use the prefix sum array to determine which index that 5 corresponds to? To determine the segment, we’ll need to find its corresponding endpoint. We know that:

• Either 5 itself is the endpoint, since 5 could be the endpoint of its own segment, or:
• The endpoint is somewhere to the right of 5 since its endpoint cannot be to the left.

Among all the endpoints to the right of 5, the closest one to 5 will be the endpoint of its segment. Endpoints farther away belong to different segments:

This means for any target, we’re looking for the first prefix sum (endpoint) greater than or equal to the target. Below, we can see which prefix sum first meets this condition for a target of 5:

As we can see, the first prefix sum that satisfies this condition is the same as the lower-bound prefix sum that satisfies this condition. Therefore, we can perform a lower-bound binary search to find it.

Let’s see how this works over our example with a random target of 5. The search space should encompass all prefix sum values:

Let’s begin narrowing the search space. Remember that we’re looking for the lower-bound prefix sum which satisfies the condition prefix_sums[mid] ≥ target.

The initial midpoint value is 4, which is less than the target of 5. This means the lower bound is somewhere to the right of the midpoint, so let’s narrow the search space toward the right:

The midpoint value is now 6, which is greater than the target. This midpoint satisfies our condition, so it could be the lower bound. If it isn’t, then the lower bound is somewhere further to the left. So, let’s narrow the search space toward the left while including the midpoint:

Now, the left and right pointers have met with the search space consisting of a single value which represents the lower bound. So, we can exit the binary search and return the index that corresponds to this prefix sum: left:

Implementation

from typing import List
import random
    
class WeightedRandomSelection:
    def __init__(self, weights: List[int]):
        self.prefix_sums = [weights[0]]
        for i in range(1, len(weights)):
            self.prefix_sums.append(self.prefix_sums[-1] + weights[i])
      
    def select(self) -> int:
        # Pick a random target between 1 and the largest endpoint on the number
        # line.
        target = random.randint(1, self.prefix_sums[-1])
        left, right = 0, len(self.prefix_sums) - 1
        # Perform lower-bound binary search to find which endpoint (i.e., prefix
        # sum value) corresponds to the target.
        while left < right:
            mid = (left + right) // 2
            if self.prefix_sums[mid] < target:
                left = mid + 1
            else:
                right = mid
        return left

Complexity Analysis

Time complexity: The time complexity of the constructor is O(n)O(n)O(n) because we iterate through each weight in the weights array once. The time complexity of select is O(log⁡(n))O(\log(n))O(log(n)) since we perform binary search over the prefix_sums array.

Space complexity: The space complexity of the constructor is O(n)O(n)O(n) due to the prefix_sums array. The space complexity of select is O(1)O(1)O(1).

Introduction to Stacks

Introduction to Stacks

Intuition

Imagine a stack of plates. You can only add a new plate to the top of the stack, and when you need a plate, you take the one from the top. It’s not possible to take a plate from the bottom or middle without first removing all the plates above it.

This analogy encapsulates the essence of the stack data structure. Adding a plate to and taking a plate from the top of the stack, physically demonstrates the two main stack operations:

• Push (adds an element to the top of the stack).
• Pop (removes and returns the element at the top of the stack).

LIFO (Last‐In‐First‐Out) Stacks follow the LIFO principle, meaning the most recently added item is the first to be removed. This unique characteristic makes stacks particularly useful in various scenarios where the order of processing or removal is critical. Here are a few key applications:

• Handling nested structures: Stacks are a good option for parsing or validating nested structures such as nested parentheses in a string (e.g., "(())()"). They allow us to process the innermost nested structures first due to the LIFO principle.
• Reverse order: When elements are added (pushed) onto a stack and then removed (popped), they come out in the reverse order of how they were added. This property is useful for reversing sequences.
• Substitute for recursion: Recursive algorithms use the recursive call stack to manage recursive calls. Ultimately, this recursive call stack is itself a stack. As such, we can often implement recursive functions iteratively using the stack data structure. • Monotonic stacks: These special‐purpose stacks maintain elements in a consistent, increasing or decreasing sorted order. Before adding a new element to the stack, any elements that break this order are removed from the top of the stack, ensuring the stack remains sorted.

Some examples of the above applications are explored in this chapter.

Below is a time complexity breakdown of common stack operations:

Real-world Example

Function call management: As hinted above, a common real‐world example of stacks is in function call management within operating systems or programming languages.

When a function is called, the program pushes the function’s state (including its parameters, local variables, and the return address) onto the call stack. As functions call other functions, their states are also pushed onto the stack. When a function completes, its state is popped off the stack, and the program returns to the calling function. This stack‐based approach ensures that functions return control in the correct order, managing nested or recursive function calls efficiently.

Chapter Outline

This chapter explores a variety of problems, offering detailed explanations for how to use stacks in problem solving. Additionally, we briefly introduce queues and deques, which are two data structures that share similarities with stacks, but operate on different principles.

Valid Parenthesis Expression

Valid Parenthesis Expression

Given a string representing an expression of parentheses containing the characters '(', ')', '[', ']', '{', or '}', determine if the expression forms a valid sequence of parentheses.

A sequence of parentheses is valid if every opening parenthesis has a corresponding closing parenthesis, and no closing parenthesis appears before its matching opening parenthesis.

Example 1:

Input: s = '([]{})'
Output: True

Example 2:

Input: s = '([]{)}'
Output: False

Explanation: The '(' parenthesis is closed before its nested '{' parenthesis is closed.

Intuition

An early observation is that for each type of parenthesis, the number of opening and closing parenthesis must be identical. However, to check if an expression is valid, this observation alone isn’t enough. For example, the string "())(" has the same number of opening and closing parentheses, but is still invalid. This means we need a way to account for the order of parentheses.

Consider the string “()”. The first parenthesis is opening, and we’re waiting for it to be closing. Upon reaching the second parenthesis, the first parenthesis gets closed.

Now, consider the string “[(])”. When we reach index 1, we have two opening parentheses waiting to be closed. In particular, we expect ‘(‘ to be closed before ‘[’. The first closing parenthesis we encounter is ‘]’, which does not close ‘(’. Therefore, this string is invalid.

The key observation here is that the most recent opening parenthesis we encounter should be the first parenthesis that gets closed. So, opening parentheses are processed from most recent to least recent, which is indicative of a last-in-first-out (LIFO) dynamic. This leads to the idea that a stack can be used to solve this problem.

Stack Here’s a high-level strategy:

• Add each opening parenthesis we encounter to the stack. This way, the most recent parenthesis is always at the top of the stack.
• When encountering a closing parenthesis, check if it can close the most recent opening parenthesis. If it can, close that pair of parenthesis by popping off the top of the stack. If not, the string is invalid.

Let’s see how this strategy works over an example:

For each opening parenthesis we encounter, push it to the top of the stack:

Next, we encounter a closing parenthesis. Comparing it to the opening parenthesis at the top of the stack, we see that it correctly closes that opening parenthesis. So, we can pop off the opening parenthesis at the top of the stack:

The next character is an opening parenthesis, which we just push to the top of the stack:

The next character is a closing parenthesis, ‘)’, which does not close the opening parenthesis at the top of the stack, ‘{’. This means this parenthesis expression is invalid. As such, we return false.

If we’ve iterated over the entire string without returning false, that means we’ve accounted for all closing parentheses in the string.

Edge case: extra opening parentheses We only check for invalidity at closing parenthesis, so need to perform a final check to ensure there aren’t any opening parentheses in the string left unclosed. This can be done by checking if the stack is empty after processing the whole input string, as a non-empty stack indicates opening parentheses remain in the stack.

Managing three types of parentheses In our algorithm, we need a way to ensure we compare the correct types of opening and closing parentheses. We can use a hash map for this, which maps each type of opening parenthesis to its corresponding closing parenthesis:

This hash map can also be used as a way to check if a parenthesis is an opening or a closing one: if the parenthesis exists in this hash map as a key, it’s an opening parenthesis.

Implementation

def valid_parenthesis_expression(s: str) -> bool:
    parentheses_map = {'(': ')', '{': '}', '[': ']'}
    stack = []
    for c in s:
        # If the current character is an opening parenthesis, push it onto the stack.
        if c in parentheses_map:
            stack.append(c)
        # If the current character is a closing parenthesis, check if it closes the
        # opening parenthesis at the top of the stack.
        else:
            if stack and parentheses_map[stack[-1]] == c:
                stack.pop()
            else:
                return False
    # If the stack is empty, all opening parentheses were successfully closed.
    return not stack

Complexity Analysis

Time complexity: The time complexity of valid_parenthesis_expression is O(n)O(n)O(n) because we traverse the entire string once. For each character, we perform a constant-time operation, either pushing an opening parenthesis onto the stack or popping it off for a matching closing parenthesis.

Space complexity: The space complexity is O(n)O(n)O(n) because the stack stores at most nnn characters, and the hash map takes up O(1)O(1)O(1) space.

Next Largest Number to the Right

Next Largest Number to the Right

Given an integer array nums, return an output array res where, for each value nums[i], res[i] is the first number to the right that's larger than nums[i]. If no larger number exists to the right of nums[i], set res[i] to ‐1.

Example:

Input: nums = [5, 2, 4, 6, 1]
Output: [6, 4, 6, -1, -1]

Intuition

A brute-force solution to this problem involves iterating through each number in the array and, for each of these numbers, linearly searching to their right to find the first larger number. This approach takes O(n2)O(n^2)O(n2) time, where nnn denotes the length of the array. Can we think of something better?

Let’s approach this problem from a different perspective. Instead of finding the next largest number for each value, what if we check whether the value itself is the next largest number for any value(s) to its left? For example, can we figure out which values in the following example have 6 as their next largest number?:

With this shift in perspective, we should search the array from right to left: certain values we encounter from the right could potentially be the next largest number of values to their left. Let’s call these values “candidates.” But how do we determine which numbers qualify as candidates?

Consider the example below:

Let’s start at the rightmost index, where the only value we know initially is 4:

Right now, we can say 4 is a candidate as it might be the next largest number of values to its left. No candidates have been encountered before 4 because it’s the rightmost element, so we should mark the result for 4 in res as -1:

Next, we encounter a 2. The next largest number of 2 is the most recently added candidate that’s larger than it. In this case, the rightmost candidate in the candidates list represents the most recently added candidate, which is 4 in this case.

Record 4 as the next largest number of 2 in res, and then add 2 to the candidates list because it could be the next largest number of elements to its left:

The next number is 3. Notice that with the introduction of 3, number 2 should no longer be considered a candidate. This is because it’s now impossible for 2 to be the next largest number of any value to its left. Since 3 is both larger and further to the left, it will always be prioritized over 2 as the next largest number. So, let’s remove 2 from the candidates list, as well as any other candidate that’s less than or equal to 3:

Since we removed all candidates smaller than 3, the rightmost candidate is now 4. So, let’s record 4 as the next largest number of 3 in res and add 3 to the candidates list:

This provides a crucial insight:

Whenever we move to a new number, all candidates less than or equal to this number should be removed from the candidates list.

Another key observation is that the list of candidates always maintains a strictly decreasing order of values. This is because we always remove candidates less than or equal to each new value, ensuring values are added in decreasing order. We can see this more clearly in the final state of the candidates list of the previous example:

This indicates a stack is the ideal data structure for storing the candidates list, since stacks can be used to efficiently maintain a monotonic decreasing order of values, as mentioned in the introduction.

The top of the stack represents the most recent candidate to the right of each new number encountered. Given this, here’s how to use the stack to add and remove candidates at each value:

1. Pop off all candidates from the top of the stack less than or equal to the current value.
2. The top of the stack will then represent the next largest number of the current value.

• Record the top of the stack as the answer for the current value.
• If the stack is empty, there’s no next largest number for the current value. So, record -1.

1. Add the current value as a new candidate by pushing it to the top of the stack.

Implementation

from typing import List
    
def next_largest_number_to_the_right(nums: List[int]) -> List[int]:
    res = [0] * len(nums)
    stack = []
    # Find the next largest number of each element, starting with the rightmost
    # element.
    for i in range(len(nums) - 1, -1, -1):
        # Pop values from the top of the stack until the current value's next largest
        # number is at the top.
        while stack and stack[-1] <= nums[i]:
            stack.pop()
        # Record the current value's next largest number, which is at the top of the
        # stack. If the stack is empty, record -1.
        res[i] = stack[-1] if stack else -1
        stack.append(nums[i])
    return res

Complexity Analysis

Time complexity: The time complexity of next_largest_number_to_the_right is O(n)O(n)O(n). This is because each value of nums is pushed and popped from the stack at most once.

Space complexity: The space complexity is O(n)O(n)O(n) because the stack can potentially store all nnn values.

Evaluate Expression

Evaluate Expression

Given a string representing a mathematical expression containing integers, parentheses, addition, and subtraction operators, evaluate and return the result of the expression.

Example:

Input: s = '18-(7+(2-4))'
Output: 13

Intuition

At first, it might seem overwhelming to deal with expressions that include a variety of elements like negative numbers, nested expressions inside parentheses, and numbers with multiple digits. The key to managing this complexity is to break down the problem into smaller, more manageable parts. Let's first focus on evaluating simple expressions that contain no parentheses.

Handling positive and negative signs Consider the following expression:

There's already some complexity in this expression with there being two signs to consider: plus and minus. An immediate simplification we can make is to treat all expressions as ones of pure addition. This is possible when we assign signs to each number (1 representing + and -1 representing -). This sign can be multiplied by the number to attain its correct value. This allows us to just focus on performing additions:

Processing numbers with multiple digits Another complexity in this expression is that some numbers have multiple digits. We’ll need a way to build numbers digit by digit until we reach the end of the number. We can build a number using the variable curr_num, which is initially set to 0. Every time we encounter a new digit, we multiply curr_num by 10 and add the new digit to it, effectively shifting all digits to the left and appending the new digit.

We can see this process play out for the string “123” in the following illustration:

We can stop building this number once we encounter a non-digit character, indicating the end of the number.

Evaluating an expression without parentheses With the information from the section above, let's evaluate the following expression, which contains no parentheses. We’ll start off with a sign of 1:

Upon reaching the ‘-’ operator, we’ve reached the end of the first number (28). So, let’s:

1. Multiply the current number (28) by its sign (1).
2. Add the resulting product (28) to the result.
3. Update the sign to -1 since the current operator is a minus sign.
4. Reset curr_num to 0 before building the next number.

Once we reach the second operator, we multiply the current number (10) by its sign of -1 before adding the resulting product (-10) to the result. This effectively subtracts 10 from the result:

Finally, once we’ve reached the end of the string, we just add the final number (7) to the result after multiplying it by its sign of 1:

Evaluating expressions containing parentheses Now that we can solve simple expressions, it's time to bring parentheses into the discussion. Moving forward, we define a nested expression as one that’s inside a pair of parentheses.

One challenge is that we need to evaluate the results of nested expressions before we can calculate the original expression. Once all nested expressions are evaluated, we can evaluate the original expression.

Consider another problem in this chapter that also contains parentheses: Valid Parenthesis Expression. In that problem, we used a stack to process nested parentheses in the right order. This suggests a stack might also help us evaluate nested expressions in the right order. Let’s explore this idea further.

Similar to Valid Parenthesis Expression, an opening parenthesis ‘(‘ indicates the start of a new nested expression, whereas a closing parenthesis ‘)’ indicates the end of one. Understanding this, let’s try to use a stack to solve the following expression.

We already know how to evaluate expressions without parentheses, so let’s just focus on what to do when we encounter a parenthesis.

At the first opening parenthesis, we know a nested expression has started. Before we evaluate the nested expression, we’ll need to save the running result (res) of the current expression, as well as the sign of this upcoming nested expression. This way, once we’re done evaluating the nested expression, we can resume where we were in the current expression.

Here are the steps for when we encounter an opening parenthesis:

1. stack.push(res): Save the running result on the stack.
2. stack.push(sign): Save the sign of the upcoming nested expression on the stack.
3. res = 0, sign = 1: Reset these variables because we’re about to begin calculating a new expression.

The next parenthesis we encounter is an opening parenthesis. Again, this indicates the start of a new nested expression. Let’s save the current result and sign on the stack, before resetting them to evaluate the upcoming nested expression:

The next parenthesis we encounter is a closing parenthesis. This means the current nested expression just ended, and we need to merge its result with the outer expression. Here’s how we do this:

1. res *= stack.pop(): Apply the sign of the current nested expression to its result.
2. res += stack.pop(): Add the result of the outer expression to the result of the current nested expression.

After applying those operations, the value of res will be 5, representing the result of the highlighted part of the expression below:

At the final closing parenthesis, we can apply the same steps:

Finally, the value of res will be 13, representing the result of the entire expression:

Now that we’ve reached the end of the string, we can return res.

Implementation

def evaluate_expression(s: str) -> int:
    stack = []
    curr_num, sign, res = 0, 1, 0
    for c in s:
        if c.isdigit():
            curr_num = curr_num * 10 + int(c)
        # If the current character is an operator, add 'curr_num' to the result
        # after multiplying it by its sign.
        elif c == '+' or c == '-':
            res += curr_num * sign
            # Update the sign and reset 'curr_num'.
            sign = -1 if c == '-' else 1
            curr_num = 0
        # If the current character is an opening parenthesis, a new nested expression
        # is starting.
        elif c == '(':
            # Save the current 'res' and 'sign' values by pushing them onto
            # the stack, then reset their values to start calculating the new nested
            # expression.
            stack.append(res)
            stack.append(sign)
            res, sign = 0, 1
        # If the current character is a closing parenthesis, a nested expression has
        # ended.
        elif c == ')':
            # Finalize the result of the current nested expression.
            res += sign * curr_num
            # Apply the sign of the current nested expression’s result before adding
            # this result to the result of the outer expression.
            res *= stack.pop()
            res += stack.pop()
            curr_num = 0
    # Finalize the result of the overall expression.
    return res + curr_num * sign

Complexity Analysis

Time complexity: The time complexity of evaluate_expression is O(n)O(n)O(n) because we traverse each character of the expression once, processing nested expressions using the stack, where each stack push or pop operation takes O(1)O(1)O(1) time.

Space complexity: The space complexity is O(n)O(n)O(n) because the stack can grow proportionally to the length of the expression.

Repeated Removal of Adjacent Duplicates

Repeated Removal of Adjacent Duplicates

Given a string, continually perform the following operation: remove a pair of adjacent duplicates from the string. Continue performing this operation until the string no longer contains pairs of adjacent duplicates. Return the final string.

Example 1:

Input: s = 'aacabba'
Output: 'c'

Example 2:

Input: s = 'aaa'
Output: 'a'

Intuition

One challenge in solving this problem is how we handle characters which aren’t currently adjacent duplicates but will be in the future.

A solution we can try is to iteratively build the string character by character and immediately remove each pair of adjacent duplicates that get formed as we’re building the string.

It’s also possible an adjacent duplicate may be formed after another adjacent duplicate gets removed. For example, with the string “abba”, removing “bb” will result in “aa”. Building the string character by character ensures the formation of “aa” gets noticed and removed. To better understand how this works, let’s dive into an example.

Consider the following string:

At the second ‘a’, we notice that adding it would result in an adjacent duplicate forming (i.e., “aa”). So, let’s remove this duplicate before adding any new characters. We’ll do this for all adjacent duplicates we come across as we build the string:

Once the smoke clears, the resulting string we were building ends up just being “c”, which is the expected output.

Now that we know how this strategy works, we just need a data structure that'll allow us to:

1. Add letters to one end of it.
2. Remove letters from the same end.

The stack data structure is a strong option because it allows for both operations.

As we push characters onto the stack, the top of the stack will represent the previous/most recently added character. Given this, to mimic the process of building the “new string” as shown in the example, we:

• Push the current character onto the stack if it’s different from the character at the top (i.e., not a duplicate character.)
• Pop off the character at the top of the stack if it's the same as the current character (i.e., a duplicate.)

Once all characters have been processed, the last thing to do is return the content of the stack as a string, since the final state of the stack will contain all characters that weren’t removed.

Implementation

def repeated_removal_of_adjacent_duplicates(s: str) -> str:
    stack = []
    for c in s:
        # If the current character is the same as the top character on the stack,
        # a pair of adjacent duplicates has been formed. So, pop the top character
        # from the stack.
        if stack and c == stack[-1]:
            stack.pop()
        # Otherwise, push the current character onto the stack.
        else:
            stack.append(c)
    # Return the remaining characters as a string.
    return ''.join(stack)

Complexity Analysis

Time complexity: The time complexity of the repeated_removal_of_adjacent_duplicates function is O(n)O(n)O(n) where nnn denotes the length of the string. This is because we traverse the entire string, and we perform a join operation of up to nnn characters in the stack. The stack push and pop operations contribute O(1)O(1)O(1) time.

Space complexity: The space complexity is O(n)O(n)O(n) because the stack can store at most nnn characters.

Implement a Queue using Stacks

Implement a Queue using Stacks

Implement a queue using the stack data structure. Include the following functions:

• enqueue(x: int) -> None: adds x to the end of the queue.
• dequeue() -> int: removes and returns the element from the front of the queue.
• peek() -> int: returns the front element of the queue.

You may not use any other data structures to implement the queue.

Example

Input: [enqueue(1), enqueue(2), dequeue(), enqueue(3), peek()]
Output: [1, 2]

Constraints:

• The dequeue and peek operations will only be called on a non-empty queue.

Intuition

A queue is a first-in-first-out (FIFO) data structure, whereas stacks are a first-in-last-out (FILO) data structure:

The main difference between these data structures is how items are evicted from them. In a queue, the first value to enter is the first to leave, whereas it would be the last to leave in a stack.

Now that we understand how they work, let’s dive into the problem. Let’s start by seeing if it’s possible to replicate the functionality of a queue with just one stack.

Consider the following stack where we push values 1, 2, and 3 to it after receiving enqueue(1), enqueue(2), and enqueue(3):

We now encounter a problem with attempting a dequeue operation since popping off the top of the stack would return 3. The value we actually want popped off is 1, since it was the first value that entered the data structure. However, 1 is all the way at the bottom of the stack.

To get to the bottom, we need to pop off all the values from the top of the stack and temporarily store these values in a separate data structure (temp) so we can add them back to the stack later:

Once we've popped and returned the bottom value (1), push the values stored in temp back onto the stack in reverse order to ensure they're added back correctly:

We know that if we were to use a data structure such as temp, it’d have to be a stack, since the problem specifies only stacks can be used. In this temporary data structure, we remove values in the opposite order in which we added them. In other words, it follows the LIFO principle, which is conveniently how a stack works. This means we can use a stack for our temporary storage.

Now, even though we have a solution that works, having to pop off every single value from the top of the stack whenever we want to access the bottom value is quite time-consuming. To find a way around this, let’s have a closer look at the state of our two stacks right after we’ve moved the stack values to temp:

In our original solution, we would now move the values from temp back to the main stack. However, notice the top of the temp stack now contains the next value we expect to return. This is because it’s the second value to have entered the data structure, and according to the FIFO eviction policy, it should be the next one to be removed.

So, instead of adding these values back to the main stack, we could just leave them in temp and return the stack’s top value at the next dequeue call.

In the above logic, we ended up using two stacks which each serve a unique purpose. In particular, we used:

1. A stack to push values onto during each enqueue call (enqueue_stack).
2. A stack to pop values from during each dequeue call (dequeue_stack).

An important thing to realize here is that the dequeue stack won’t always be populated with values. So, what should we do when it’s empty? We can just populate it by moving all the values from the enqueue stack to the dequeue stack, just like we did in the example. To understand this more clearly, let’s dive into a full example.

Let’s start with two enqueue calls and push each number onto the enqueue stack.

Now, let's try processing a dequeue call. The first step is to pop off each element from the enqueue stack and push them onto the dequeue stack:

Then, we just return the top value from the dequeue stack:

Let’s enqueue one more value:

If we call dequeue again, we return the value from the top of the dequeue stack:

Now, what happens when we call dequeue and the dequeue stack is empty? We need to repopulate it by popping all the values from the enqueue stack and pushing them into the dequeue stack. Once this is done, we return the top of the dequeue stack as usual:

Regarding the peek function, we follow the same logic as the dequeue function, but instead, we return the top element of the dequeue stack without popping it.

Implementation

As mentioned before, the dequeue and peek functions have mostly the same behavior, with the only difference being that dequeue pops the top value while peek does not. To avoid duplicate code, the common logic between these functions for transferring values from the enqueue stack to the dequeue stack has been extracted into a separate function, transfer_enqueue_to_dequeue.

class Queue:
    def __init__(self):
        self.enqueue_stack = []
        self.dequeue_stack = []

    def enqueue(self, x: int) -> None:
        self.enqueue_stack.append(x)

    def transfer_enqueue_to_dequeue(self) -> None:
        # If the dequeue stack is empty, push all elements from the enqueue stack
        # onto the dequeue stack. This ensures the top of the dequeue stack
        # contains the most recent value.
        if not self.dequeue_stack:
            while self.enqueue_stack:
                self.dequeue_stack.append(self.enqueue_stack.pop())

    def dequeue(self) -> int:
        self.transfer_enqueue_to_dequeue()
        # Pop and return the value at the top of the dequeue stack.
        return self.dequeue_stack.pop() if self.dequeue_stack else None

    def peek(self) -> int:
        self.transfer_enqueue_to_dequeue()
        return self.dequeue_stack[-1] if self.dequeue_stack else None

Complexity Analysis

Time complexity: The time complexity of:

• enqueue is O(1)O(1)O(1) because we add one element to the enqueue stack in constant time.
• dequeue is amortized O(1)O(1)O(1). In the worst case, all elements from the enqueue stack are moved to the dequeue stack. This takes O(n)O(n)O(n) time, where nnn denotes the number of elements in the enqueue queue. However, each element is only ever moved once during its lifetime. So, over nnn dequeue calls, at most nnn elements are moved between stacks, averaging the cost to O(1)O(1)O(1) time per dequeue operation.
• peek is amortized O(1)O(1)O(1) for the same reasons as dequeue.

Space complexity: The space complexity is O(n)O(n)O(n) since we maintain two stacks that collectively store all elements of the queue at any given time.

Maximums of Sliding Window

Maximums of Sliding Window

There's a sliding window of size k that slides through an integer array from left to right. Create a new array that records the largest number found in each window as it slides through.

Example:

Input: nums = [3, 2, 4, 1, 2, 1, 1], k = 4
Output: [4, 4, 4, 2]

Intuition

A brute-force approach to solving this problem involves iterating through each element within a window to find the maximum value of that window. Repeating this for each window will take O(n⋅k)O(n\cdot k)O(n⋅k) time because we traverse kkk elements for up to nnn windows.

The main issue is that as we slide the window, we keep re-examining the same elements we've already looked at in previous windows. This is because two adjacent windows share mostly the same values.

A more efficient solution likely involves keeping track of values we see in any given window so that at the next window, we don't have to iterate over previously seen values again. Specifically, at each window, we should only maintain a record of values that have the potential to become the maximum of a future window. Let's call these values candidates, where all the values that aren't candidates can no longer contribute to a maximum. How can we determine which numbers are candidates?

Consider the window of size 4 in the following array. We'll use left and right pointers to define the window:

To identify the candidates for the next window, let's look at each number individually.

3: Number 3 is a candidate for the current window, but once we move to the next window, we can ignore it since it will no longer be included in the window.

2: Could number 2 be a maximum of a future window? The answer is no. This is because of the 4 to its right: all future windows which contain this 2 will also contain 4, and since 4 is larger, it means 2 could never be a maximum of any future windows.

4: This is the maximum value in the current window, and it'll be included in some future windows. Therefore, 4 could potentially be a maximum for a future window.

1: Could 1 become the maximum of a future window? The answer is yes. While 4 is larger in the current window, it's positioned to the left of 1. As the window shifts to the right, there will eventually be a point where 1 remains in the window while 4 is excluded, making 1 a potential maximum in the future.

Based on the above analysis, we can derive the following strategy whenever the window encounters a new candidate:

1. Remove smaller or equal candidates: Any existing candidates less than or equal to the new candidate should be discarded because they can no longer be maximums of future windows.
2. Adding the new candidate: Once smaller candidates are discarded, the new value can be added as a new candidate.
3. Removing outdated candidates: When the window moves past a value, that value should be discarded to ensure we don't consider values outside the window.

Observe how this strategy is applied to the list of candidates below as the window advances one index to the right:

An important observation is that candidate values always maintain a decreasing order. This is because each new candidate we encounter removes smaller and equal candidates to its left, ensuring the list of candidates is kept in a decreasing order.

This consequently means the maximum value for a window is always the first value in the candidate list.

Therefore, to store the candidates, we need a data structure that can maintain a monotonic decreasing order of values.

Deque We know that typically, a stack allows us to maintain a monotonic decreasing order of values, but in this case, it has a critical limitation: it doesn't provide a way to remove outdated candidates. A stack is a last-in-first-out (LIFO) data structure, which means we only have access to the last (i.e., most recent) end of the data structure. From the diagram above, we know we need access to both ends of the list of candidates, so a stack won't be sufficient.

Is there a data structure that allows us to add and remove from both ends? A double-ended queue, or deque for short, is a great candidate for this. A deque is essentially a doubly linked list under the hood. It allows us to push and pop values from both ends of the data structure in O(1)O(1)O(1) time.

Despite its name, it's easier to think of a deque as a double-ended stack:

Now that we have our data structure, let's see how we can use it over the following example. Note that our deque will store tuples containing both a value and its corresponding index. We keep track of indexes in the deque because they allow us to determine whether a value has moved outside the window. We'll see how this works later in the example.

Start by expanding the window until it's of length k. For each candidate we encounter, we need to ensure the values in the deque maintain a monotonic decreasing order before pushing it in:

When we reach 4, we can't add it to the deque straight away because adding it would violate the decreasing order of the deque. So, let's pop any candidates from the right of the deque that are less than 4 before pushing 4 in.

The next expansion of the window will set it at the expected fixed size of k:

Now that the window is of length k, it's time to begin recording the maximum value of each window. As mentioned earlier, the maximum value is the first value in the candidate list (i.e., the leftmost value of the deque.) The maximum value of this window is 4 since it's the leftmost candidate value.

With the window now at a fixed size of k, our approach shifts from expanding the window to sliding it. As we slide, we should remove any values from the deque whose index is before the left pointer, since those values will be outside the window:

The maximum value of the above window after the three operations are performed is revealed to be 4, as it's the leftmost candidate value.

The maximum value of the above window after the three operations are performed is also 4, as it's the leftmost candidate value.

Before recording the maximum value of this window, we ensured 4 was removed from the deque because its index (index 2) occurs before the left pointer (index 3), indicating it's no longer within the current window. The maximum value for this window after this removal is revealed to be 2.

Implementation

from typing import List
from collections import deque
    
def maximums_of_sliding_window(nums: List[int], k: int) -> List[int]:
    res = []
    dq = deque()
    left = right = 0
    while right < len(nums):
        # 1) Ensure the values of the deque maintain a monotonic decreasing order
        # by removing candidates <= the current candidate.
        while dq and dq[-1][0] <= nums[right]:
            dq.pop()
        # 2) Add the current candidate.
        dq.append((nums[right], right))
        # If the window is of length 'k', record the maximum of the window.
        if right - left + 1 == k:
            # 3) Remove values whose indexes occur outside the window.
            if dq and dq[0][1] < left:
                dq.popleft()
            # The maximum value of this window is the leftmost value in the
            # deque.
            res.append(dq[0][0])
            # Slide the window by advancing both 'left' and 'right'. The right
            # pointer always gets advanced so we just need to advance 'left'
            left += 1
        right += 1
    return res

Complexity Analysis

Time complexity: The time complexity of maximums_of_sliding_window is O(n)O(n)O(n) because we slide over the array in linear time, and we push and pop values of nums into the deque at most once for each number.

Space complexity: The space complexity is O(k)O(k)O(k) because the deque can store up to kkk elements.

Interview Tip

Tip: If you're unsure about what data structure to use for a problem, first identify what attributes or operations you want from the data structure. Use these attributes and operations to pinpoint a data structure that satisfies them and can be used to solve the problem. In this problem, we wanted a data structure that could add and remove elements from both ends of it efficiently, and the best data structure that matched these requirements was a deque.

Introduction to Heaps

Introduction to Heaps

Intuition

A heap is a data structure that organizes elements based on priority, ensuring the highest-priority element is always at the top of the heap. This allows for efficient access to the highest-priority element at any time. There are two main types of heaps:

• Min-heap: prioritizes the smallest element by keeping it at the top of the heap.
• Max-heap: prioritizes the largest element by keeping it at the top of the heap.

Efficient prioritization is possible due to how heaps are structured. A heap is essentially a binary tree. In the case of a min-heap, for example, each node's value is less than or equal to that of its children. This guarantees the root of this tree (the top of the heap) is always the smallest element:

Here's a time complexity breakdown of common heap operations:

This chapter discusses the practical uses of heaps. For a deeper understanding of how a heap works, we recommend diving into the details behind its internal implementation, and how its binary tree structure is consistently maintained during various operations [2].

Priority queue: A priority queue is a special type of heap that follows the structure of min-heaps or max-heaps but allows customization in how elements are prioritized.

Real-world Example

Managing tasks in operating systems: Operating systems often use a priority queue to manage the execution of tasks, and a heap is commonly used to implement this priority queue efficiently.

For example, when multiple processes are running on a computer, each process might be assigned a priority level. The operating system needs to schedule the processes so that higher-priority tasks are executed before lower-priority ones.

Chapter Outline

K Most Frequent Strings

K Most Frequent Strings

Find the k most frequently occurring strings in an array, and return them sorted by frequency in descending order. If two strings have the same frequency, sort them in lexicographical order.

Example:

Input: strs = ['go', 'coding', 'byte', 'byte', 'go', 'interview', 'go'], k = 2
Output: ['go', 'byte']

Explanation: The strings "go" and "byte" appear the most frequently, with frequencies of 3 and 2, respectively.

Constraints:

• k ≤ n, where n denotes the length of the array.

Intuition - Max-Heap

The two main challenges to this problem are:

1. Identifying the k most frequent strings.
2. Sorting those strings first by frequency and then lexicographically.

First, we need a way to keep track of the frequencies of each string. We can use a hash map for this, where the keys represent the strings and the values represent frequencies.

The most straightforward approach is to obtain an array containing the strings from the hash map, sorted by frequency in descending order. The k most frequent strings would be the first k strings in this array.

The main inefficiency of this solution is that it involves sorting all n strings, even though we only need the top k frequent ones to be sorted.

Something useful to consider: if we remove the most frequent string, the new most frequent string after this removal represents the second-most frequent overall. By repeatedly identifying and removing the most frequent string k times, we efficiently obtain our answer.

To implement this idea, we need a data structure that allows efficient access to the most frequent string at any time. A max-heap is perfect for this.

One way to populate the heap is to push all n strings into it one by one, which will take O(nlog(n)) time. Instead, we can perform the heapify operation on an array containing all the string-frequency pairs to create the max-heap in O(n) time.

To collect the k most frequent strings, pop off the top element from the heap k times and store the corresponding strings in the output array res:

Now, we just need to ensure that when two strings have the same frequency, the one that comes first lexicographically has a higher priority in the heap. To do this, we can define a custom comparator for the heap.

Implementation - Max-Heap

We create a Pair class for string-frequency pairs, enabling us to customize priority using a custom comparator.

from typing import List
from collections import Counter
import heapq
    
class Pair:
   def __init__(self, str, freq):
       self.str = str
       self.freq = freq
    
   def __lt__(self, other):
       if self.freq == other.freq:
           return self.str < other.str
       return self.freq > other.freq
    
def k_most_frequent_strings_max_heap(strs: List[str], k: int) -> List[str]:
   freqs = Counter(strs)
   max_heap = [Pair(str, freq) for str, freq in freqs.items()]
   heapq.heapify(max_heap)
   return [heapq.heappop(max_heap).str for _ in range(k)]

Complexity Analysis

Time complexity: O(n + k log(n)). Space complexity: O(n).

Intuition - Min-Heap

As a follow up, your interviewer may ask you to modify your solution to reduce the space used by the heap.

An important observation is that when our heap exceeds size k, we can discard the lowest frequency strings until the heap's size is reduced to k again. We can do this because those discarded strings definitely won't be among the k most frequent strings.

However, we can't implement this strategy with a max-heap because we won't have access to the lowest frequency string. Instead, we need to use a min-heap.

from typing import List
from collections import Counter
import heapq
    
class Pair:
    def __init__(self, str, freq):
        self.str = str
        self.freq = freq
    def __lt__(self, other):
        if self.freq == other.freq:
            return self.str > other.str
        return self.freq < other.freq
    
def k_most_frequent_strings_min_heap(strs: List[str], k: int) -> List[str]:
    freqs = Counter(strs)
    min_heap = []
    for str, freq in freqs.items():
        heapq.heappush(min_heap, Pair(str, freq))
        if len(min_heap) > k:
            heapq.heappop(min_heap)
    return [heapq.heappop(min_heap).str for _ in range(k)][::-1]

Complexity Analysis

Time complexity: O(n log(k)). Space complexity: O(n) for hash map, O(k) for heap.

Combine Sorted Linked Lists

Combine Sorted Linked Lists

Given k singly linked lists, each sorted in ascending order, combine them into one sorted linked list.

Intuition

A good place to start with this problem is by figuring out how to merge just two sorted linked lists. We can do this by initiating a pointer at the start of both linked lists. Comparing the nodes at these pointers, add the smaller one to the output linked list and advance the corresponding pointer.

But what if we have more than two linked lists? Combining two linked lists involves comparing two nodes at each iteration, but combining k linked lists would require k comparisons per iteration.

The reason we need to make so many comparisons is that we don't know which node has the smallest value at any point in the iteration, requiring us to search for it. A min-heap is perfect for this.

To start, populate the heap with the head nodes of all the linked lists, so they're ready for comparison.

Then, let's implement our strategy of adding the smallest-valued node to the output linked list, using the heap to identify it. We'll use a dummy node to help build the output linked list. After a node is popped off, the subsequent node from its linked list is added to the heap.

Once the heap is empty, we can return dummy.next, which is the head of the combined linked list.

Implementation

from typing import List
from ds import ListNode
import heapq
    
def combine_sorted_linked_lists(lists: List[ListNode]) -> ListNode:
    ListNode.__lt__ = lambda self, other: self.val < other.val
    heap = []
    for head in lists:
        if head:
            heapq.heappush(heap, head)
    dummy = ListNode(-1)
    curr = dummy
    while heap:
        smallest_node = heapq.heappop(heap)
        curr.next = smallest_node
        curr = curr.next
        if smallest_node.next:
            heapq.heappush(heap, smallest_node.next)
    return dummy.next

Complexity Analysis

Time complexity: O(n log(k)), where n is total number of nodes. Space complexity: O(k).

Median of an Integer Stream

Median of an Integer Stream

Design a data structure that supports adding integers from a data stream and retrieving the median of all elements received at any point.

• add(num: int) -> None: adds an integer to the data structure.
• get_median() -> float: returns the median of all integers so far.

Example:

Input: [add(3), add(6), get_median(), add(1), get_median()]
Output: [4.5, 3.0]

Intuition

The median is always found in the middle of a sorted list of values. The challenge with this problem is that it's unclear how to keep all the values sorted as new values arrive.

We can use a combination of a min-heap and a max-heap:

• A max-heap manages the left half, where the top value represents the first median value.
• A min-heap manages the right half, where the top value represents the second median value.

If the total number of elements is odd, there's only one median — we designate the max-heap to store this median.

Two rules for managing the heaps:

1. The maximum value of the max-heap (left half) must be less than or equal to the minimum value of the min-heap (right half).
2. The heaps should be of equal size, but the max-heap can have one more element than the min-heap.

Implementation

import heapq
    
class MedianOfAnIntegerStream:
    def __init__(self):
        self.left_half = []   # max-heap (negated)
        self.right_half = []  # min-heap
        
    def add(self, num: int) -> None:
        if not self.left_half or num <= -self.left_half[0]:
            heapq.heappush(self.left_half, -num)
            if len(self.left_half) > len(self.right_half) + 1:
                heapq.heappush(self.right_half, -heapq.heappop(self.left_half))
        else:
            heapq.heappush(self.right_half, num)
            if len(self.right_half) > len(self.left_half):
                heapq.heappush(self.left_half, -heapq.heappop(self.right_half))
    
    def get_median(self) -> float:
        if len(self.left_half) == len(self.right_half):
            return (-self.left_half[0] + self.right_half[0]) / 2
        return float(-self.left_half[0])

Complexity Analysis

Time complexity of add: O(log(n)). Time complexity of get_median: O(1). Space complexity: O(n).

Sort a K-Sorted Array

Sort a K-Sorted Array

Given an integer array where each element is at most k positions away from its sorted position, sort the array in a non-decreasing order.

Example:

Input: nums = [5, 1, 9, 4, 7, 10], k = 2
Output: [1, 4, 5, 7, 9, 10]

Intuition

In a k-sorted array, each element is at most k indexes away from where it would be in a fully sorted array.

A trivial solution to this problem is to sort the array using a standard sorting algorithm. However, since the input is partially sorted (k-sorted), we should assume there's a faster way to sort the array.

For any index i, the element that belongs at index i in the sorted array is located within the range [i - k, i + k]. The value needed at index 0 is the smallest number within the range [0, 0 + k].

To improve this approach, we need a min-heap to efficiently access the minimum value at each range [i, i + k].

Implementation

from typing import List
import heapq
        
def sort_a_k_sorted_array(nums: List[int], k: int) -> List[int]:
    min_heap = nums[:k+1]
    heapq.heapify(min_heap)
    insert_index = 0
    for i in range(k + 1, len(nums)):
        nums[insert_index] = heapq.heappop(min_heap)
        insert_index += 1
        heapq.heappush(min_heap, nums[i])
    while min_heap:
        nums[insert_index] = heapq.heappop(min_heap)
        insert_index += 1
    return nums

Complexity Analysis

Time complexity: O(n log(k)). Space complexity: O(k).

Introduction to Intervals

Introduction to Intervals

Intuition

An interval consists of two values: a start point and an end point. It represents a continuous segment on the number line that includes all values between these two points. It is often used to represent a line, time period, or a continuous range of values.

• An interval's start point indicates where the interval begins.
• An interval's end point indicates where the interval ends.

Intervals can be closed, open, or half-open, based on whether their start or end points are included in the interval.

• Closed intervals: Both the start and end points are included in the interval.

• Open intervals: The start and end points are not included in the interval.

• Half-open intervals: Either the start or the end point is included, while the other is not.

When presented with an interval problem in an interview, It's important to clarify whether the intervals are open, closed, or half-open, as this can change the nature of how intervals overlap.

Overlapping intervals Two intervals overlap if they share at least one common value.

The central challenge in most interval problems involves managing overlapping intervals effectively. Whether identifying or merging overlapping intervals, it's important to determine how the overlap between intervals influences the desired outcome of the problem. The problems in this chapter involve handling overlapping intervals in varying situations.

Sorting intervals In most interval problems, sorting the intervals before solving the problem is quite helpful since it allows them to be processed in a certain order.

We usually sort intervals by their start point so they can be traversed in chronological order. When two or more intervals have the same start point, we might also need to consider each interval's end points during sorting.

Separating start and end points In certain scenarios, it might be beneficial to process the start and end points of intervals separately. This usually involves creating two sorted arrays: one containing all start points and another containing all end points. For example, this is needed in the sweeping line algorithm, which is explored in the Largest Overlap of Intervals problem.

Interval class definition For the problems in this chapter, intervals are represented using the class below.

class Interval:
   def __init__(self, start, end):
       self.start = start
       self.end = end

Real-world Example

Scheduling systems: Intervals are widely used in scheduling systems. For instance, in a conference room booking system, each booking is represented as an interval. The interval representation is used if the system requires functionality, such as determining the maximum number of overlapping bookings to ensure sufficient room availability. By analyzing these intervals, the system can efficiently allocate resources and prevent double bookings.

Chapter Outline

Merge Overlapping Intervals

Merge Overlapping Intervals

Merge an array of intervals so there are no overlapping intervals, and return the resultant merged intervals.

Example:

Input: intervals = [[3, 4], [7, 8], [2, 5], [6, 7], [1, 4]]
Output: [[1, 5], [6, 8]]

Constraints:

• The input contains at least one interval.
• For every index i in the array, intervals[i].start ≤ intervals[i].end.

Intuition

There are two main challenges to this problem:

1. Identifying which intervals overlap each other.
2. Merging those intervals.

Let's start by tackling the first challenge. Consider two intervals, A and B, where interval A starts before B. Below, we visualize the case when these two intervals don't overlap:

The dashed line above shows that interval A ends before interval B starts, which eliminates the possibility of B overlapping A. This indicates that intervals A and B will never overlap when A.end < B.start.

Now, consider a couple of cases where these two intervals do overlap:

In these cases, we see that B starts before (or when) A ends (A.end ≥ B.start). In other words, some portion of B overlaps A since interval A hasn't ended before interval B starts. Therefore, intervals A and B overlap when A.end ≥ B.start.

We have now established the two cases that cover all overlapping and non-overlapping scenarios for two intervals, given interval A starts before interval B:

• If A.end < B.start, the intervals don't overlap.
• If A.end ≥ B.start, the intervals overlap.

To apply these conditions to any two intervals in the input, it's useful to have a way to identify which interval starts first. One idea is to sort the intervals by their start value, which will make it clear which one of each two adjacent intervals starts first.

Merging intervals With the above logic in mind, let's tackle an example. Consider the following intervals:

The first step is to sort these intervals by start value:

To aid the explanation, let's represent the intervals visually:

Let's add/merge each interval into a new array called merged, starting with the first one, which we can add to the merged array straight away as it's the first interval:

After the first interval is added, we start the process of merging. Let's define A as the last interval in the merged array and B as the current interval in the input.

We notice B starts before A ends, indicating an overlap. So, let's merge them:

When merging A and B, we use the leftmost start value and the rightmost end value between them.

We can apply the same logic to the next interval:

When we reach the fourth interval, we notice B starts after A ends, indicating there is no overlap.

So, we just add it as a new interval to the merged array:

The next interval, B, overlaps the last interval in the merged array, A, since B starts when A ends (A.end == B.start).

So, let's merge A with B:

After processing the last interval, we've successfully merged all intervals.

Implementation

from typing import List
from ds import Interval
    
def merge_overlapping_intervals(intervals: List[Interval]) -> List[Interval]:
    intervals.sort(key=lambda x: x.start)
    merged = [intervals[0]]
    for B in intervals[1:]:
        A = merged[-1]
        if A.end < B.start:
            merged.append(B)
        else:
            merged[-1] = Interval(A.start, max(A.end, B.end))
    return merged

Complexity Analysis

Time complexity: O(nlog(n)) due to sorting. Merging itself takes O(n).

Space complexity: O(n) for Python's Tim sort.

Interview Tip

Tip: Visualize intervals to uncover logic and edge cases. Drawing examples helps your interviewer follow along with your reasoning.

Identify All Interval Overlaps

Identify All Interval Overlaps

Return an array of all overlaps between two arrays of intervals; intervals1 and intervals2. Each individual interval array is sorted by start value, and contains no overlapping intervals within itself.

Example:

Input: intervals1 = [[1, 4], [5, 6], [9, 10]],
       intervals2 = [[2, 7], [8, 9]]
Output: [[2, 4], [5, 6], [9, 9]]

Constraints:

• For every index i in intervals1, intervals1[i].start < intervals1[i].end.
• For every index j in intervals2, intervals2[j].start < intervals2[j].end.

Intuition

We're given two arrays of intervals, each containing non-overlapping intervals. This implies an overlap can only occur between an interval from the first array and an interval from the second array.

Identifying the overlap between two overlapping intervals We know from the Merge Overlapping Intervals problem that two intervals, A and B, overlap when A.end >= B.start, assuming A starts before B.

To extract the overlap between these two overlapping intervals, we need to identify when it starts and ends.

• The overlap starts at the furthest start point, which is always B.start.
• The overlap ends at the earliest end point (min(A.end, B.end)).

Therefore, when two intervals overlap, their overlap is defined by the range [B.start, min(A.end, B.end)].

Identifying all overlaps Now, let's return to the two arrays of intervals.

Let's start by considering the first interval from each array:

To check if these intervals overlap, we identify which interval starts first, assigning it as A and the other as B:

if intervals1[i].start <= intervals2[j].start:
    A, B = intervals1[i], intervals2[j]
else:
    A, B = intervals2[j], intervals1[i]

A and B overlap when A.end >= B.start, which is true here. Let's record the overlap: [B.start, min(A.end, B.end)]:

After identifying the overlap, advance the pointer of whichever interval ends first.

We've now identified a process that allows us to identify and record all overlaps while traversing the arrays of intervals:

1. Set A as the interval that starts first, and B as the other interval.
2. Check if A.end >= B.start to see if these intervals overlap. If they do, record the overlap as [B.start, min(A.end, B.end)].
3. Whichever interval ends first, advance its corresponding pointer to move to the next interval.

Continue until either i or j have passed the end of their array.

Implementation

from typing import List
from ds import Interval
   
def identify_all_interval_overlaps(intervals1: List[Interval], intervals2: List[Interval]) -> List[Interval]:
   overlaps = []
   i = j = 0
   while i < len(intervals1) and j < len(intervals2):
       if intervals1[i].start <= intervals2[j].start:
           A, B = intervals1[i], intervals2[j]
       else:
           A, B = intervals2[j], intervals1[i]
       if A.end >= B.start:
           overlaps.append(Interval(B.start, min(A.end, B.end)))
       if intervals1[i].end < intervals2[j].end:
           i += 1
       else:
           j += 1
   return overlaps

Complexity Analysis

Time complexity: O(n+m) where n and m are the lengths of intervals1 and intervals2.

Space complexity: O(1).

Largest Overlap of Intervals

Largest Overlap of Intervals

Given an array of intervals, determine the maximum number of intervals that overlap at any point. Each interval is half-open, meaning it includes the start point but excludes the end point.

Example:

Input: intervals = [[1, 3], [5, 7], [2, 6], [4, 8]]
Output: 3

Constraints:

• The input will contain at least one interval.
• For every index i in the list, intervals[i].start < intervals[i].end.

Intuition

Think about what it means when x intervals overlap at a certain point in time. This means at this point, there are x 'active' intervals, where an interval is active if it has started but not ended.

In the example below, we see three active intervals at time 5:

To find the number of active intervals at any point in time, we need to identify when an interval has started and when an interval has ended. The start point indicates the start of a new active interval, whereas an end point represents an active interval finishing.

Processing start points and end points Let's step through each point in chronological order and determine the number of active intervals at each point.

The first point is a start point, incrementing our counter:

The next point is another start point, incrementing the counter to 2:

The next point is an end point, decrementing the counter to 1:

We've rationalized what to do at each type of point:

• If we encounter a start point: increment active_intervals.
• If we encounter an end point: decrement active_intervals.

The final answer is obtained by recording the largest value of active_intervals encountered.

Edge case: processing concurrent start and end points When a start and end point occur simultaneously, we should process end points before start points to avoid counting an interval as active when it has just ended.

If we process the end point first, we won't encounter this issue:

Therefore, for start and end points that occur simultaneously, process end points before start points.

Iterating over interval points in order Combine all start and end points into a single array, sort it, ensuring end points are prioritized before start points for equal values.

The algorithm we used to solve this problem is known as a 'sweeping line algorithm.' It works by processing start and end points of intervals in order, as if a vertical line was sweeping across them.

Implementation

from typing import List
from ds import Interval
    
def largest_overlap_of_intervals(intervals: List[Interval]) -> int:
   points = []
   for interval in intervals:
       points.append((interval.start, 'S'))
       points.append((interval.end, 'E'))
   points.sort(key=lambda x: (x[0], x[1]))
   active_intervals = 0
   max_overlaps = 0
   for time, point_type in points:
       if point_type == 'S':
           active_intervals += 1
       else:
           active_intervals -= 1
       max_overlaps = max(max_overlaps, active_intervals)
   return max_overlaps

Complexity Analysis

Time complexity: O(n*log(n)) due to sorting the points array of size 2n.

Space complexity: O(n) due to the points array.

Introduction to Prefix Sums

Introduction to Prefix Sums

Intuition

Imagine keeping track of how much money you spend on takeout meals each day over a period of days.

A prefix sum array maintains the running sum of values up to each index in the array. The total spent up until Wednesday is $45 ($10+$15+$20).

To obtain the prefix sum at each index, add the current number from the input array to the prefix sum from the previous index.

In code, the above process looks like this:

def compute_prefix_sums(nums):
    prefix_sum = [nums[0]]
    for i in range(1, len(nums)):
        prefix_sum.append(prefix_sum[-1] + nums[i])

Building a prefix sum array takes O(n) time and O(n) space, where n denotes the length of the array.

Applications of prefix sums Aside from constant-time access to running sums, prefix sums are commonly used to efficiently determine the sum of subarrays. Another interesting variant is prefix products, which populates an array with a running product instead of a running sum.

Real-world Example

Financial analysis: A real-world use of prefix sums is for financial analysis, particularly in calculating cumulative earnings or expenses over time. By precomputing the prefix sums, a company can instantly determine the revenue for any given period without summing each day's revenue individually.

Chapter Outline

Sum Between Range

Sum Between Range

Given an integer array, write a function which returns the sum of values between two indexes.

Example:

Input: nums = [3, -7, 6, 0, -2, 5],
       [sum_range(0, 3), sum_range(2, 4), sum_range(2, 2)]
Output: [2, 4, 6]

Constraints:

• nums contains at least one element.
• Each sum_range operation will query a valid range of the input array.

Intuition

We need to code a function sum_range(i, j). A naive solution iteratively sums from index i to j in linear time per call. Using prefix sums can improve efficiency.

Consider the integer array and its prefix sums:

The prefix sum up to any index j gives the answer to sum_range(0, j). For example, the sum of range [0, 3] is prefix_sum[3].

Therefore, when i == 0:

sum_range(0, j) = prefix_sum[j]

For range [2, 4], the sum equals prefix_sum[4] - prefix_sum[1]:

The sum of range [2, 4] = prefix_sum[4] - prefix_sum[1] by subtracting the sum of [0, 1] from the sum of [0, 4].

Therefore, when i > 0:

sum_range(i, j) = prefix_sum[j] - prefix_sum[i - 1]

Implementation

from typing import List
    
class SumBetweenRange:
    def __init__(self, nums: List[int]):
        self.prefix_sum = [nums[0]]
        for i in range(1, len(nums)):
            self.prefix_sum.append(self.prefix_sum[-1] + nums[i])
    
    def sum_range(self, i: int, j: int) -> int:
        if i == 0:
            return self.prefix_sum[j]
        return self.prefix_sum[j] - self.prefix_sum[i - 1]

Complexity Analysis

Time complexity: Constructor is O(n). sum_range is O(1).

Space complexity: O(n) for the prefix_sum array.

K-Sum Subarrays

K-Sum Subarrays

Find the number of subarrays in an integer array that sum to k.

Example:

Input: nums = [1, 2, -1, 1, 2], k = 3
Output: 3

Intuition

The brute force solution iterates every possible subarray in O(n^3) time. Using prefix sums reduces this.

The sum of a subarray [i,j] = prefix_sum[j] - prefix_sum[i-1] (when i>0), or just prefix_sum[j] when i=0.

We unify both cases by prepending 0 to the prefix sums array so prefix_sum[i-1]=0 when i=0 is valid.

from typing import List
    
def k_sum_subarrays(nums: List[int], k: int) -> int:
    n = len(nums)
    count = 0
    prefix_sum = [0]
    for i in range(0, n):
        prefix_sum.append(prefix_sum[-1] + nums[i])
    for j in range(1, n + 1):
        for i in range(1, j + 1):
            if prefix_sum[j] - prefix_sum[i - 1] == k:
                count += 1
    return count

This O(n^2) solution can be optimized using a hash map. For each prefix sum (curr_prefix_sum), find how many times curr_prefix_sum - k appeared previously.

For each element, check if curr_prefix_sum - k is in the hash map. If found, add its frequency to count.

Strategy: 1) Update curr_prefix_sum. 2) If curr_prefix_sum-k in map, add frequency to count. 3) Add curr_prefix_sum to map.

Implementation

from typing import List
    
def k_sum_subarrays_optimized(nums: List[int], k: int) -> int:
    count = 0
    prefix_sum_map = {0: 1}
    curr_prefix_sum = 0
    for num in nums:
        curr_prefix_sum += num
        if curr_prefix_sum - k in prefix_sum_map:
            count += prefix_sum_map[curr_prefix_sum - k]
        prefix_sum_map[curr_prefix_sum] = prefix_sum_map.get(curr_prefix_sum, 0) + 1
    return count

Complexity Analysis

Time complexity: O(n) - iterate through nums once.

Space complexity: O(n) for the hash map.

Product Array Without Current Element

Product Array Without Current Element

Given an array of integers, return an array res so that res[i] is equal to the product of all elements except nums[i] itself.

Example:

Input: nums = [2, 3, 1, 4, 5]
Output: [60, 40, 120, 30, 24]

Explanation: The output value at index 0 is the product of all numbers except nums[0] (3*1*4*5 = 60).

Intuition

The straightforward solution divides total product by each element (total=120). But what if division is not allowed?

Without division, the output for any index = product of all numbers to its left * product of all numbers to its right.

We need two arrays:

• left_products: left_products[i] is the product of all values to the left of i.
• right_products: right_products[i] is the product of all values to the right of i.

Prefix products Prefix products use cumulative multiplication (initialized with 1 instead of 0).

1. Instead of cumulative addition, we use cumulative multiplication.
2. We initialize the prefix product array with 1 instead of 0.

right_products is built similarly from right to left. Once both arrays are ready, res[i] = left_products[i] * right_products[i].

Reducing space: populate res with left products first, then multiply by running right_product in-place.

Implementation

from typing import List
    
def product_array_without_current_element(nums: List[int]) -> List[int]:
    n = len(nums)
    res = [1] * n
    for i in range(1, n):
        res[i] = res[i - 1] * nums[i - 1]
    right_product = 1
    for i in range(n - 1, -1, -1):
        res[i] *= right_product
        right_product *= nums[i]
    return res

Complexity Analysis

Time complexity: O(n) - iterate over nums twice.

Space complexity: O(1). The res array is not included in the space complexity analysis.

Introduction to Trees

Introduction to Trees

Intuition

A tree is a hierarchical data structure composed of nodes, where each node connects to one or more child nodes. Each node in a tree contains the data it stores (val) and references to its child nodes. The most common type of tree is a binary tree, in which each node connects to up to two children: a left child and a right child.

Below is the implementation of the TreeNode class:

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

Terminology:

• Parent: a node with one or more children.
• Child: a node that has a parent.
• Subtree: a tree formed by a node and its descendants.
• Path: a single, continuous sequence of nodes connected by edges.
• Depth: the number of edges from the root to a given node.

Attributes of a tree:

• Root: the topmost node of the tree and the only node without a parent.
• Intermediate node: a node with a parent node and at least one child.
• Leaf: a node with no children.
• Edge: the connection between two nodes. Trees usually have directed edges, meaning the edges only point from parent to child.
• Height: the length of the longest path from the root to a leaf.1

In the following discussions, we primarily focus on binary trees.

Tree Traversals

Depth-first search (DFS) DFS is a method for exploring all nodes of a tree by starting at the root and moving as far down a branch as possible, before backtracking to explore other branches.

DFS is typically implemented recursively, following a structure similar to the code snippet below:

def dfs(node: TreeNode):
    if node is None:
        return
    process(node)       # Process the current node.
    dfs(node.left)      # Traverse the left subtree.
    dfs(node.right)     # Traverse the right subtree.

The above recursive implementation follows the order of preorder traversal. Two other common DFS traversal techniques include inorder traversal and postorder traversal. Here's how they differ:

DFS has many use cases and is the most common choice for tree traversal.

• Preorder traversal is the most common type of DFS traversal. It's also used when we need to process the root node of each subtree before its children.
• Inorder traversal is used when we want to process the nodes of a tree from left to right.
• Postorder traversal is the least frequently used traversal method, but is important when each node's subtrees must be processed before their root.

The problems in this chapter explore the use cases of DFS in more detail, providing practical examples of when and how to apply these traversal methods.

Breadth-first search (BFS) BFS traverses the nodes of a tree level by level. It processes the nodes at the present level before moving on to nodes at the next depth level.

def bfs(root: TreeNode):
    if root is None:
        return
    queue = deque([root])
    while queue:
        node = queue.popleft()
        process(node)  # Process the current node.
        if node.left:
            queue.append(node.left)  # Add the left child to the queue.
        if node.right:
            queue.append(node.right)  # Add the right child to the queue.

BFS is commonly used to find the shortest path to a specific destination in a tree, or to process the tree level by level. When it's important to know the specific level of each node during traversal, we use a variant of BFS called level-order traversal, which is discussed in detail in this chapter.

Complexity breakdown Below, n denotes the number of nodes in the tree, and h denotes the height of the tree.

Real-world Example

File systems: In many operating systems, the file system is organized as a hierarchical tree structure. The root directory is the root of the tree, and every file or folder in the system is a node. Folders can have subfolders or files as child nodes, and this structure allows for efficient organization, navigation, and retrieval of files. When you browse through folders on a computer, you're essentially navigating a tree structure.

Chapter Outline

Note that some of the problems listed under DFS can be solved using BFS or other traversal algorithms, too. The same applies to the problems under BFS.

Footnotes

1. Some sources may define the height of a tree differently. In this book, we use a definition that makes designing recursive algorithms more intuitive. Here, the height of a tree with just one node is considered 1. ↩

Invert Binary Tree

Invert Binary Tree

Invert a binary tree and return its root. When a binary tree is inverted, it becomes the mirror image of itself.

Example:

Intuition - Recursive

To invert a binary tree is to essentially "flip" the tree along a vertical axis.

from ds import TreeNode
    
def invert_binary_tree_recursive(root: TreeNode) -> TreeNode:
    if not root:
        return None
    root.left, root.right = root.right, root.left
    invert_binary_tree_recursive(root.left)
    invert_binary_tree_recursive(root.right)
    return root

Implementation - Iterative

from ds import TreeNode
    
def invert_binary_tree_iterative(root: TreeNode) -> TreeNode:
    if not root:
        return None
    stack = [root]
    while stack:
        node = stack.pop()
        node.left, node.right = node.right, node.left
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return root

Balanced Binary Tree Validation

Balanced Binary Tree Validation

Determine if a binary tree is height-balanced, meaning no node's left subtree and right subtree have a height difference greater than 1.

from ds import TreeNode
    
def balanced_binary_tree_validation(root: TreeNode) -> bool:
    return get_height_imbalance(root) != -1
    
def get_height_imbalance(node: TreeNode) -> int:
    if not node:
        return 0
    left_height = get_height_imbalance(node.left)
    right_height = get_height_imbalance(node.right)
    if left_height == -1 or right_height == -1:
        return -1
    if abs(left_height - right_height) > 1:
        return -1
    return 1 + max(left_height, right_height)

Rightmost Nodes of a Binary Tree

Rightmost Nodes of a Binary Tree

Return an array containing the values of the rightmost nodes at each level of a binary tree.

from ds import TreeNode
    
def rightmost_nodes_of_a_binary_tree(root: TreeNode) -> List[int]:
    if not root:
        return []
    res = []
    queue = deque([root])
    while queue:
        level_size = len(queue)
        for i in range(level_size):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
            if i == level_size - 1:
                res.append(node.val)
    return res

Widest Binary Tree Level

Widest Binary Tree Level

Return the width of the widest level in a binary tree, where the width of a level is defined as the distance between its leftmost and rightmost non-null nodes.

from ds import TreeNode
    
def widest_binary_tree_level(root: TreeNode) -> int:
    if not root:
        return 0
    max_width = 0
    queue = deque([(root, 0)])
    while queue:
        level_size = len(queue)
        leftmost_index = queue[0][1]
        rightmost_index = leftmost_index
        for _ in range(level_size):
            node, i = queue.popleft()
            if node.left:
                queue.append((node.left, 2*i + 1))
            if node.right:
                queue.append((node.right, 2*i + 2))
            rightmost_index = i
        max_width = max(max_width, rightmost_index - leftmost_index + 1)
    return max_width

Binary Search Tree Validation

Binary Search Tree Validation

Verify whether a binary tree is a valid binary search tree (BST).

from ds import TreeNode
    
def binary_search_tree_validation(root: TreeNode) -> bool:
    return is_within_bounds(root, float('-inf'), float('inf'))
    
def is_within_bounds(node: TreeNode, lower_bound: int, upper_bound: int) -> bool:
    if not node:
        return True
    if not lower_bound < node.val < upper_bound:
        return False
    if not is_within_bounds(node.left, lower_bound, node.val):
        return False
    return is_within_bounds(node.right, node.val, upper_bound)

Lowest Common Ancestor

Lowest Common Ancestor

Return the lowest common ancestor (LCA) of two nodes, p and q, in a binary tree.

from ds import TreeNode
    
def lowest_common_ancestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    dfs(root, p, q)
    return lca
    
def dfs(node: TreeNode, p: TreeNode, q: TreeNode) -> bool:
    global lca
    if not node:
        return False
    node_is_p_or_q = node == p or node == q
    left_contains_p_or_q = dfs(node.left, p, q)
    right_contains_p_or_q = dfs(node.right, p, q)
    if node_is_p_or_q + left_contains_p_or_q + right_contains_p_or_q == 2:
        lca = node
    return node_is_p_or_q or left_contains_p_or_q or right_contains_p_or_q

Build Binary Tree From Preorder and Inorder Traversals

Build Binary Tree From Preorder and Inorder Traversals

Construct a binary tree using arrays of values obtained after a preorder traversal and an inorder traversal of the tree.

from ds import TreeNode
from typing import List
    
preorder_index = 0
inorder_indexes_map = {}
    
def build_binary_tree(preorder: List[int], inorder: List[int]) -> TreeNode:
    global inorder_indexes_map
    for i, val in enumerate(inorder):
        inorder_indexes_map[val] = i
    return build_subtree(0, len(inorder) - 1, preorder, inorder)
    
def build_subtree(left, right, preorder, inorder):
    global preorder_index, inorder_indexes_map
    if left > right:
        return None
    val = preorder[preorder_index]
    inorder_index = inorder_indexes_map[val]
    node = TreeNode(val)
    preorder_index += 1
    node.left = build_subtree(left, inorder_index - 1, preorder, inorder)
    node.right = build_subtree(inorder_index + 1, right, preorder, inorder)
    return node

Maximum Sum of a Continuous Path in a Binary Tree

Maximum Sum of a Continuous Path in a Binary Tree

Return the maximum sum of a continuous path in a binary tree.

from ds import TreeNode
    
max_sum = float('-inf')
    
def max_path_sum(root: TreeNode) -> int:
   global max_sum
   max_path_sum_helper(root)
   return max_sum
    
def max_path_sum_helper(node: TreeNode) -> int:
   global max_sum
   if not node:
       return 0
   left_sum = max(max_path_sum_helper(node.left), 0)
   right_sum = max(max_path_sum_helper(node.right), 0)
   max_sum = max(max_sum, node.val + left_sum + right_sum)
   return node.val + max(left_sum, right_sum)

Binary Tree Symmetry

Binary Tree Symmetry

Determine if a binary tree is vertically symmetric.

from ds import TreeNode
    
def binary_tree_symmetry(root: TreeNode) -> bool:
    if not root:
        return True
    return compare_trees(root.left, root.right)
    
def compare_trees(node1: TreeNode, node2: TreeNode) -> bool:
    if not node1 and not node2:
        return True
    if not node1 or not node2:
        return False
    if node1.val != node2.val:
        return False
    if not compare_trees(node1.left, node2.right):
        return False
    return compare_trees(node1.right, node2.left)

Binary Tree Columns

Binary Tree Columns

Given the root of a binary tree, return a list of arrays where each array represents a vertical column of the tree.

from ds import TreeNode
from typing import List
from collections import defaultdict, deque
    
def binary_tree_columns(root: TreeNode) -> List[List[int]]:
    if not root:
        return []
    column_map = defaultdict(list)
    leftmost_column = rightmost_column = 0
    queue = deque([(root, 0)])
    while queue:
        node, column = queue.popleft()
        if node:
            column_map[column].append(node.val)
            leftmost_column = min(leftmost_column, column)
            rightmost_column = max(rightmost_column, column)
            queue.append((node.left, column - 1))
            queue.append((node.right, column + 1))
    return [column_map[i] for i in range(leftmost_column, rightmost_column + 1)]

Kth Smallest Number in a Binary Search Tree

Kth Smallest Number in a Binary Search Tree

Given the root of a binary search tree (BST) and an integer k, find the kth smallest node value.

def kth_smallest_number_in_BST_iterative(root: TreeNode, k: int) -> int:
    stack = []
    node = root
    while stack or node:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        k -= 1
        if k == 0:
            return node.val
        node = node.right

Serialize and Deserialize a Binary Tree

Serialize and Deserialize a Binary Tree

Write a function to serialize a binary tree into a string, and another function to deserialize that string back into the original binary tree structure.

from ds import TreeNode
    
def serialize(root: TreeNode) -> str:
    serialized_list = []
    preorder_serialize(root, serialized_list)
    return ','.join(serialized_list)
    
def preorder_serialize(node, serialized_list) -> None:
    if node is None:
        serialized_list.append('#')
        return
    serialized_list.append(str(node.val))
    preorder_serialize(node.left, serialized_list)
    preorder_serialize(node.right, serialized_list)
    
def deserialize(data: str) -> TreeNode:
    node_values = iter(data.split(','))
    return build_tree(node_values)
    
def build_tree(values):
    val = next(values)
    if val == '#':
        return None
    node = TreeNode(int(val))
    node.left = build_tree(values)
    node.right = build_tree(values)
    return node

Introduction to Tries

Introduction to Tries

Intuition

Tries, also known as prefix trees, are specialized tree-like data structures that efficiently store strings by taking advantage of shared prefixes.

TrieNode There are two attributes each TrieNode should have.

1. Children: Each TrieNode has a data structure to store references to its child nodes. A hash map is typically used for this, with a character as the key and its corresponding child node as the value.

2. End of word indicator: Each TrieNode needs an attribute to indicate whether it marks the end of a word.

• A boolean attribute (is_word) to confirm if the node is the end of a word.
• A string variable (word) that stores the word itself at the node.

When to use tries The primary use of a trie is to handle efficient prefix searches.

Real-world Example

Autocomplete: When you start typing a word, some systems use a trie to quickly suggest possible completions.

Chapter Outline

Design a Trie

Design a Trie

Design and implement a trie data structure that supports the following operations:

• insert(word: str) -> None: Inserts a word into the trie.
• search(word: str) -> bool: Returns true if a word exists in the trie, and false if not.
• has_prefix(prefix: str) -> bool: Returns true if the trie contains a word with the given prefix, and false if not.

Implementation

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

class Trie:
   def __init__(self):
       self.root = TrieNode()
    
   def insert(self, word: str) -> None:
       node = self.root
       for c in word:
           if c not in node.children:
               node.children[c] = TrieNode()
           node = node.children[c]
       node.is_word = True
    
   def search(self, word: str) -> bool:
       node = self.root
       for c in word:
           if c not in node.children:
               return False
           node = node.children[c]
       return node.is_word
    
   def has_prefix(self, prefix: str) -> bool:
       node = self.root
       for c in prefix:
           if c not in node.children:
               return False
           node = node.children[c]
       return True

Insert and Search Words with Wildcards

Insert and Search Words with Wildcards

Design and implement a data structure that supports insert and wildcard search operations.

• insert(word: str) -> None: Inserts a word into the data structure.
• search(word: str) -> bool: Returns true if a word exists in the data structure and false if not. The word may contain wildcards ('.') that can represent any letter.

Implementation

class InsertAndSearchWordsWithWildcards:
   def __init__(self):
       self.root = TrieNode()
    
   def insert(self, word: str) -> None:
       node = self.root
       for c in word:
           if c not in node.children:
               node.children[c] = TrieNode()
           node = node.children[c]
       node.is_word = True
    
   def search(self, word: str) -> bool:
       return self.search_helper(0, word, self.root)
    
   def search_helper(self, word_index: int, word: str, node: TrieNode) -> bool:
       for i in range(word_index, len(word)):
           c = word[i]
           if c == '.':
               for child in node.children.values():
                   if self.search_helper(i + 1, word, child):
                       return True
               return False
           else:
               if c not in node.children:
                   return False
               node = node.children[c]
       return node.is_word

Find All Words on a Board

Find All Words on a Board

Given a 2D board of characters and an array of words, find all the words in the array that can be formed by tracing a path through adjacent cells in the board.

Input: board = [['b', 'y', 's'], ['r', 't', 'e'], ['a', 'i', 'n']],
       words = ['byte', 'bytes', 'rat', 'rain', 'trait', 'train']
Output: ['byte', 'bytes', 'rain', 'train']

Implementation

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None

from typing import List
    
def find_all_words_on_a_board(board: List[List[str]], words: List[str]) -> List[str]:
    root = TrieNode()
    for word in words:
        node = root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.word = word
    res = []
    for r in range(len(board)):
        for c in range(len(board[0])):
            if board[r][c] in root.children:
                dfs(board, r, c, root.children[board[r][c]], res)
    return res
    
def dfs(board, r, c, node, res):
    if node.word:
        res.append(node.word)
        node.word = None
    temp = board[r][c]
    board[r][c] = '#'
    directions = [(0,1),(0,-1),(1,0),(-1,0)]
    for dr, dc in directions:
        nr, nc = r + dr, c + dc
        if 0 <= nr < len(board) and 0 <= nc < len(board[0]) and board[nr][nc] in node.children:
            dfs(board, nr, nc, node.children[board[nr][nc]], res)
    board[r][c] = temp

Introduction to Graphs

Introduction to Graphs

Intuition

A graph is a data structure composed of nodes (vertices) connected by edges. Graphs are used to model relationships, where the edges define the relationships.

Below is the implementation of the GraphNode class:

class GraphNode:
    def __init__(self, val):
        self.val = val
        self.neighbors = []

Terminology:

• Adjacent node/neighbor: two nodes are adjacent if there's an edge connecting them.
• Degree: the number of edges connected to a node.
• Path: a sequence of nodes connected by edges.

Attributes:

• Directed vs. undirected: in a directed graph, edges have a direction associated with them.
• Weighted vs. unweighted: in a weighted graph, edges have a weight associated with them, such as distance or cost.
• Cyclic vs. acyclic: A cyclic graph contains at least one cycle, which is a path that starts and ends at the same node.

Representations In some problems, you might not be given the graph directly. In these situations, it's usually necessary to create your own representation of the graph. The two most common representations to choose from are an adjacency list and an adjacency matrix.

In an adjacency list, the neighbors of each node are stored as a list.

In an adjacency matrix, the graph is represented as a 2D matrix where matrix[i][j] indicates an edge between nodes i and j.

Adjacency lists are the most common choice for most implementations. They are preferred when representing sparse graphs and when we need to iterate over all the neighbors of a node efficiently.

Adjacency matrices are preferred when representing dense graphs, and frequent checks are needed for the existence of specific edges.

Traversals The primary graph traversal techniques are DFS and BFS.

def dfs(node: GraphNode, visited: Set[GraphNode]):
    visited.add(node)
    process(node)
    for neighbor in node.neighbors:
        if neighbor not in visited:
            dfs(neighbor, visited)

def bfs(node: GraphNode):
    visited = set()
    queue = deque([node])
    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            process(node)
            for neighbor in node.neighbors:
                queue.append(neighbor)

Both DFS and BFS have a time complexity of O(n+e), where n denotes the number of nodes and e denotes the number of edges.

Real-world Example

Social networks: Users are represented as nodes, and connections between users are edges.

Chapter Outline

Graph Deep Copy

Graph Deep Copy

Given a reference to a node within an undirected graph, create a deep copy (clone) of the graph. The copied graph must be completely independent of the original one.

Example:

Constraints:

• The value of each node is unique.
• Every node in the graph is reachable from the given node.

Intuition

Our strategy for this problem is to traverse the original graph and create the deep copy during the traversal. We use DFS.

dfs(node):
    cloned_node = new GraphNode(node)
    for neighbor in node.neighbors:
        cloned_neighbor = dfs(neighbor)
        cloned_node.neighbors.add(cloned_neighbor)
    return cloned_node

We use a hash map to avoid cloning nodes that have already been cloned.

Implementation

from ds import GraphNode
    
def graph_deep_copy(node: GraphNode) -> GraphNode:
    if not node:
        return None
    return dfs(node)
    
def dfs(node: GraphNode, clone_map = {}) -> GraphNode:
    if node in clone_map:
        return clone_map[node]
    cloned_node = GraphNode(node.val)
    clone_map[node] = cloned_node
    for neighbor in node.neighbors:
        cloned_neighbor = dfs(neighbor, clone_map)
        cloned_node.neighbors.append(cloned_neighbor)
    return cloned_node

Complexity Analysis

Time complexity: O(n+e). Space complexity: O(n).

Count Islands

Count Islands

Given a binary matrix representing 1s as land and 0s as water, return the number of islands.

An island is formed by connecting adjacent lands 4-directionally (up, down, left, and right).

Example:

Output: 2

Intuition

We iterate through the matrix and when we find a land cell, we explore its island using DFS, marking visited cells as -1.

Implementation

from typing import List
    
def count_islands(matrix: List[List[int]]) -> int:
    if not matrix:
        return 0
    count = 0
    for r in range(len(matrix)):
        for c in range(len(matrix[0])):
            if matrix[r][c] == 1:
                dfs(r, c, matrix)
                count += 1
    return count
    
def dfs(r: int, c: int, matrix: List[List[int]]) -> None:
    matrix[r][c] = -1
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    for d in dirs:
        next_r, next_c = r + d[0], c + d[1]
        if is_within_bounds(next_r, next_c, matrix) and matrix[next_r][next_c] == 1:
            dfs(next_r, next_c, matrix)

Complexity Analysis

Time complexity: O(m*n). Space complexity: O(m*n).

Matrix Infection

Matrix Infection

You are given a matrix where each cell is either 0 (Empty), 1 (Uninfected), or 2 (Infected). Each second, every infected cell infects its 4-directionally adjacent uninfected cells. Determine the number of seconds required for all uninfected cells to become infected. If impossible, return -1.

Example:

Input: matrix = [[1, 1, 1, 0], [0, 0, 2, 1], [0, 1, 1, 0]]
Output: 3

Intuition

Use multi-source BFS (level-order traversal). Add all initially infected cells to the queue. Each level traversed = 1 second. Count uninfected cells and decrement as they get infected; return -1 if any remain.

Implementation

from typing import List
from collections import deque
    
def matrix_infection(matrix: List[List[int]]) -> int:
   dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
   queue = deque()
   ones = seconds = 0
   for r in range(len(matrix)):
       for c in range(len(matrix[0])):
           if matrix[r][c] == 1:
               ones += 1
           elif matrix[r][c] == 2:
               queue.append((r, c))
   while queue and ones > 0:
       seconds += 1
       for _ in range(len(queue)):
           r, c = queue.popleft()
           for d in dirs:
               next_r, next_c = r + d[0], c + d[1]
               if (0 <= next_r < len(matrix) and 0 <= next_c < len(matrix[0])
                       and matrix[next_r][next_c] == 1):
                   matrix[next_r][next_c] = 2
                   ones -= 1
                   queue.append((next_r, next_c))
   return -1 if ones > 0 else seconds

Complexity Analysis

Time complexity: O(m*n). Space complexity: O(m*n).

Bipartite Graph Validation

Bipartite Graph Validation

Given an undirected graph, determine if it's bipartite. A graph is bipartite if the nodes can be colored in one of two colors, so that no two adjacent nodes are the same color.

Example:

Input: graph = [[1, 4], [0, 2], [1], [4], [0, 3]]
Output: True

Intuition

Use graph coloring with DFS: color adjacent nodes alternating colors (1 and -1). If two adjacent nodes share the same color, it's not bipartite. Handle multiple components by calling DFS on every uncolored node.

Implementation

def bipartite_graph_validation(graph: List[List[int]]) -> bool:
    colors = [0] * len(graph)
    for i in range(len(graph)):
        if colors[i] == 0 and not dfs(i, 1, graph, colors):
           return False
    return True
    
def dfs(node: int, color: int, graph: List[List[int]], colors: List[int]) -> bool:
    colors[node] = color
    for neighbor in graph[node]:
        if colors[neighbor] == color:
            return False
        if colors[neighbor] == 0 and not dfs(neighbor, -color, graph, colors):
            return False
    return True

Complexity Analysis

Time complexity: O(n+e). Space complexity: O(n).

Longest Increasing Path

Longest Increasing Path

Find the longest strictly increasing path in a matrix of positive integers. A path is a sequence of cells where each one is 4-directionally adjacent to the previous one.

Example:

Output: 5

Intuition

Model as DAG (directed, acyclic). DFS from each cell to find longest path starting there. Use memoization to avoid redundant DFS calls.

Implementation

from typing import List
    
def longest_increasing_path(matrix: List[List[int]]) -> int:
    if not matrix:
        return 0
    res = 0
    m, n = len(matrix), len(matrix[0])
    memo = [[0] * n for _ in range(m)]
    for r in range(m):
        for c in range(n):
            res = max(res, dfs(r, c, matrix, memo))
    return res
    
def dfs(r: int, c: int, matrix: List[List[int]], memo: List[List[int]]):
    if memo[r][c] != 0:
        return memo[r][c]
    max_path = 1
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    for d in dirs:
        next_r, next_c = r + d[0], c + d[1]
        if (0 <= next_r < len(matrix) and 0 <= next_c < len(matrix[0])
                and matrix[next_r][next_c] > matrix[r][c]):
            max_path = max(max_path, 1 + dfs(next_r, next_c, matrix, memo))
    memo[r][c] = max_path
    return max_path

Complexity Analysis

Time complexity: O(m*n). Space complexity: O(m*n).

Shortest Transformation Sequence

Shortest Transformation Sequence

Given two words, start and end, and a dictionary, return the length of the shortest transformation sequence to transform start to end. Each word differs from the preceding word by exactly one letter. If no such sequence exists, return 0.

Example:

Input: start = 'red', end = 'hit',
       dictionary = ['red', 'bed', 'hat', 'rod', 'rad', 'rat', 'hit', 'bad', 'bat']
Output: 5

Intuition

Model as graph: words are nodes, edges exist between words differing by one letter. Use BFS (level-order traversal) from start to find shortest path to end. Generate neighbors by trying all alphabet substitutions.

Implementation

def shortest_transformation_sequence(start: str, end: str, dictionary: List[str]) -> int:
    dictionary_set = set(dictionary)
    if start not in dictionary_set or end not in dictionary_set:
        return 0
    if start == end:
        return 1
    lower_case_alphabet = 'abcdefghijklmnopqrstuvwxyz'
    queue = deque([start])
    visited = set([start])
    dist = 0
    while queue:
        for _ in range(len(queue)):
            curr_word = queue.popleft()
            if curr_word == end:
                return dist + 1
            for i in range(len(curr_word)):
                for c in lower_case_alphabet:
                    next_word = curr_word[:i] + c + curr_word[i+1:]
                    if next_word in dictionary_set and next_word not in visited:
                        visited.add(next_word)
                        queue.append(next_word)
        dist += 1
    return 0

Complexity Analysis

Time complexity: O(n*L^2). Space complexity: O(n*L).

Merging Communities

Merging Communities

There are n people numbered from 0 to n-1, each initially in separate communities. When two people connect, their communities merge. Implement connect(x, y) and get_community_size(x).

Intuition

Use Union-Find (Disjoint Set Union) data structure. Union operation merges two communities. Find operation returns a community's representative. Optimize with union by size and path compression.

Implementation

class UnionFind:
    def __init__(self, size: int):
        self.parent = [i for i in range(size)]
        self.size = [1] * size
   
    def union(self, x: int, y: int) -> None:
        rep_x, rep_y = self.find(x), self.find(y)
        if rep_x != rep_y:
            if self.size[rep_x] > self.size[rep_y]:
                self.parent[rep_y] = rep_x
                self.size[rep_x] += self.size[rep_y]
            else:
                self.parent[rep_x] = rep_y
                self.size[rep_y] += self.size[rep_x]
   
    def find(self, x: int) -> int:
        if x == self.parent[x]:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
   
    def get_size(self, x: int) -> int:
        return self.size[self.find(x)]

class MergingCommunities:
    def __init__(self, n: int):
        self.uf = UnionFind(n)
   
    def connect(self, x: int, y: int) -> None:
        self.uf.union(x, y)
   
    def get_community_size(self, x: int) -> int:
        return self.uf.get_size(x)

Complexity Analysis

connect and get_community_size: amortized O(1). Constructor: O(n). Space complexity: O(n).

Prerequisites

Prerequisites

Given n courses labeled 0 to n-1 and prerequisite pairs, determine if it's possible to enroll in all courses.

Example:

Input: n = 3, prerequisites = [[0, 1], [1, 2], [2, 1]]
Output: False

Intuition

Use Kahn's algorithm (topological sort). A cycle means enrollment is impossible. Process nodes with in-degree 0 first; if all n nodes are processed, enrollment is possible.

Implementation

from typing import List
from collections import defaultdict, deque
    
def prerequisites(n: int, prerequisites: List[List[int]]) -> bool:
    graph = defaultdict(list)
    in_degrees = [0] * n
    for prerequisite, course in prerequisites:
        graph[prerequisite].append(course)
        in_degrees[course] += 1
    queue = deque()
    for i in range(n):
        if in_degrees[i] == 0:
            queue.append(i)
    enrolled_courses = 0
    while queue:
        node = queue.popleft()
        enrolled_courses += 1
        for neighbor in graph[node]:
            in_degrees[neighbor] -= 1
            if in_degrees[neighbor] == 0:
                queue.append(neighbor)
    return enrolled_courses == n

Complexity Analysis

Time complexity: O(n+e). Space complexity: O(n+e).

Shortest Path

Shortest Path

Given n nodes, non-negative weighted edges, and a start node, return an array of shortest path lengths from start to each node. Unreachable nodes get -1.

Example:

Input: n = 6, edges = [[0,1,5],[0,2,3],[1,2,1],[1,3,4],[2,3,4],[2,4,5]], start = 0
Output: [0, 4, 3, 7, 8, -1]

Intuition

Use Dijkstra's algorithm (greedy). Always process the unvisited node with shortest known distance using a min-heap. Works for non-negative weights.

Implementation

from typing import List
from collections import defaultdict
import heapq
    
def shortest_path(n: int, edges: List[int], start: int) -> List[int]:
    graph = defaultdict(list)
    distances = [float('inf')] * n
    distances[start] = 0
    for u, v, w in edges:
        graph[u].append((v, w))
        graph[v].append((u, w))
    min_heap = [(0, start)]
    while min_heap:
        curr_dist, curr_node = heapq.heappop(min_heap)
        if curr_dist > distances[curr_node]:
            continue
        for neighbor, weight in graph[curr_node]:
            neighbor_dist = curr_dist + weight
            if neighbor_dist < distances[neighbor]:
                distances[neighbor] = neighbor_dist
                heapq.heappush(min_heap, (neighbor_dist, neighbor))
    return [-1 if d == float('inf') else d for d in distances]

Complexity Analysis

Time complexity: O((n+e)log(n)). Space complexity: O(n+e).

Connect the Dots

Connect the Dots

Given a set of points on a plane, determine the minimum cost to connect all these points. Cost = Manhattan distance between two points.

Example:

Input: points = [[1, 1], [2, 6], [3, 2], [4, 3], [7, 1]]
Output: 15

Intuition

Minimum Spanning Tree (MST) problem. Use Kruskal's algorithm: sort all edges by cost, use Union-Find to add lowest-cost edges that don't create cycles. Stop when n-1 edges added.

Implementation

from typing import List
    
def connect_the_dots(points: List[List[int]]) -> int:
    n = len(points)
    edges = []
    for i in range(n):
        for j in range(i + 1, n):
            cost = (abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]))
            edges.append((cost, i, j))
    edges.sort()
    uf = UnionFind(n)
    total_cost = edges_added = 0
    for cost, p1, p2 in edges:
        if uf.union(p1, p2):
            total_cost += cost
            edges_added += 1
            if edges_added == n - 1:
                break
    return total_cost

class UnionFind:
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.size = [1] * size

    def union(self, x, y) -> bool:
        rep_x, rep_y = self.find(x), self.find(y)
        if rep_x != rep_y:
            if self.size[rep_x] > self.size[rep_y]:
                self.parent[rep_y] = rep_x
                self.size[rep_x] += self.size[rep_y]
            else:
                self.parent[rep_x] = rep_y
                self.size[rep_y] += self.size[rep_x]
            return True
        return False

    def find(self, x) -> int:
        if x == self.parent[x]:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

Complexity Analysis

Time complexity: O(n^2 log n). Space complexity: O(n^2).

Introduction to Backtracking

Introduction to Backtracking

Intuition

Imagine you're stuck at an intersection point in a maze, and you know one of the three routes ahead leads to the exit:

However, you're not sure which route to take. To find the exit, you decide to try each option one by one, starting with option A. As you walk through passage A, you encounter a new intersection containing two more routes, D and E:

You try option D, but it leads to a dead end. So, you backtrack to the second intersection point:

Next, you try option E, but it also leads to a dead end, so you backtrack to the second junction point. After concluding that neither path D nor E works, you backtrack again to the first intersection point:

Having determined that path A doesn't lead to the exit, you move on to path B and discover that it leads to the exit:

This brute force process of testing all possible paths and backtracking upon failure is called 'backtracking.'

State space tree In backtracking, the state space tree, also known as the decision tree, is a conceptual tree constructed by considering every possible decision that can be made at each point in a process.

For example, here's how we would represent the state space tree for the maze scenario:

Here's a simplified explanation of a state space tree:

• Edges: Each edge represents a possible decision, move, or action.
• Root node: The root node represents the initial state or position before any decisions are made.
• Intermediate nodes: Nodes representing partially completed states or intermediate positions.
• Leaf nodes: The leaf nodes represent complete or invalid solutions.
• Path: A path from the root to any leaf node represents a sequence of decisions that lead to a complete or invalid solution.

Drawing out the state space tree for a problem helps to visualize the entire solution space, and all possible decisions. In addition, it's a great way to understand how the algorithm works. By figuring out how to traverse this tree, we essentially create the backtracking algorithm.

Backtracking algorithm Traversing the state space tree is typically done using recursive DFS. Let's discuss how it's implemented at a high level.

Termination condition: Define the condition that specifies when a path should end. This condition should define when we've found a valid and/or invalid solution.

Iterate through decisions: Iterate through every possible decision at the current node, which contains the current state of the problem. For each decision:

1. Make that decision and update the current state accordingly.
2. Recursively explore all paths that branch from this updated state by calling the DFS function on this state.
3. Backtrack by undoing the decision we made and reverting the state.

Below is a crude template for backtracking:

def dfs(state):
    # Termination condition.
    if meets_termination_condition(state):
        process_solution(state)
        return
    # Explore each possible decision that can be made at the current state.
    for decision in possible_decisions(state):
        make_decision(state, decision)
        dfs(state)
        undo_decision(state, decision)  # Backtrack.

Analyzing time complexity

Analyzing the time complexity of backtracking algorithms involves understanding the branching factor and the depth of the state space tree:

• Branching factor: The number of children each node has. It typically represents the maximum number of decisions that can be made for a given state.
• Depth: The length of the deepest path in the state space tree. It corresponds to the number of decisions or steps required to reach a complete solution.

The time complexity is often estimated as O(b^d), where b denotes the branching factor and d denotes the depth.

When to use backtracking Backtracking is useful when we need to explore all possible solutions to a problem. For example, if we need to find all possible ways to arrange items, or generate all possible subsets, permutations, or combinations, backtracking can help to identify every possible solution.

Real-world Example

AI algorithms for games: backtracking is used in AI algorithms for games like chess and Go to explore possible moves and strategies. The programs examine each potential move, simulate the game's progression, and evaluate the outcome. If a move leads to an unfavorable position, the program will backtrack to the previous move and try alternative options, systematically exploring the game tree until it finds the optimal strategy.

Chapter Outline

Find All Permutations

Find All Permutations

Return all possible permutations of a given array of unique integers. They can be returned in any order.

Example:

Input: nums = [4, 5, 6]
Output: [[4, 5, 6], [4, 6, 5], [5, 4, 6], [5, 6, 4], [6, 4, 5], [6, 5, 4]]

Intuition

Our task in this problem is quite straightforward: find all permutations of a given array. The key word here is "all". To achieve this, we need an algorithm that generates each possible permutation one at a time. The technique that naturally fits this requirement is backtracking. As with any backtracking solution, it's useful to first visualize the state space tree.

State space tree Let's figure out how to build just one permutation. Consider the array [4, 5, 6]. We can start by picking one number from this array for the first position of this permutation.

Now that we've found one permutation, let's backtrack to find others. Start by removing the most recently added number, 6, bringing us back to [4, 5]:

Are there any other numbers we can append to [4, 5]? Well, 6 is the only option at this point, which we already explored. So, let's backtrack again by removing 5, bringing us back to [4]:

Are there any numbers other than 5 we can add to [4] at this point? Yes, we can use 6, so let's add it and continue searching:

The only number we can use at this point is 5, so let's add it to [4, 6], giving us another permutation:

Following this backtracking process until we've explored all branches allows us to generate all permutations:

Every time we reach a permutation (i.e., when the permutation we're building reaches a size of n, where n denotes the length of the input array), add it to our output.

Traversing the state space tree Generating all permutations can be achieved by traversing the state space tree.

Each node in this tree, except leaf nodes, represents a permutation candidate: a partially completed permutation that we're building. The root node represents an empty permutation, and an element is added to each permutation candidate as we progress deeper into the tree. The leaf nodes represent completed permutations.

Starting from the root node, we can traverse this tree using backtracking:

1. Pick an unused number and add it to the current permutation candidate. Mark this number as used by adding it to the used hash set.
2. Make a recursive call with this updated permutation candidate to explore its branches.
3. Backtrack: remove the last number we added to the current candidate array, and the used hash set.

Whenever a permutation candidate reaches the length of n, add it to our output.

Implementation

from typing import List, Set
    
def find_all_permutations(nums: List[int]) -> List[List[int]]:
    res = []
    backtrack(nums, [], set(), res)
    return res
    
def backtrack(nums: List[int], candidate: List[int], used: Set[int], res: List[List[int]]) -> None:
    # If the current candidate is a complete permutation, add it to the result.
    if len(candidate) == len(nums):
        res.append(candidate[:])
        return
    for num in nums:
        if num not in used:
            # Add 'num' to the current permutation and mark it as used.
            candidate.append(num)
            used.add(num)
            # Recursively explore all branches using the updated permutation
            # candidate.
            backtrack(nums, candidate, used, res)
            # Backtrack by reversing the changes made.
            candidate.pop()
            used.remove(num)

Complexity Analysis

Time complexity: The time complexity of find_all_permutations is O(n * n!). Starting from the root, we recursively explore n candidates. For each of these n candidates, we explore n-1 more candidates, then n-2, etc. For each of the n! permutations, we make a copy of it and add it to the output, which takes O(n) time.

Space complexity: The space complexity is O(n) because the maximum depth of the recursion tree is n. The algorithm also maintains the candidate and used data structures, both of which also contribute O(n) space.

Find All Subsets

Find All Subsets

Return all possible subsets of a given set of unique integers. Each subset can be ordered in any way, and the subsets can be returned in any order.

Example:

Input: nums = [4, 5, 6]
Output: [[], [4], [4, 5], [4, 5, 6], [4, 6], [5], [5, 6], [6]]

Intuition

The key intuition for solving this problem lies in understanding that each subset is formed by making a specific decision for every number in the input array: to include the number, or exclude it. For example, from the array [4, 5, 6], the subset [4, 6] is created by including 4, excluding 5, and including 6.

State space tree Consider the input array [4, 5, 6]. Let's start with the root node of the tree, which is an empty subset:

To figure out how to branch out from here, let's consider our decision of whether to include or exclude an element. Let's make this decision with the first element of the input array, 4:

For each of these subsets, we repeat the process, branching out again based on the same choice for the second element: include or exclude it:

Finally, for the third element, we continue branching out for each existing subset based on whether we include or exclude this element:

One important thing missing from this state space tree is a way to tell which element of the input array we're making a decision on at each node of the tree. We can use an index, i, for this:

As shown, the final level of the tree (i.e., when i == n, where n denotes the length of the input array) contains all the subsets of the input array. We can add each of these subsets to our output. To get to these subsets, we need to traverse the tree, and backtracking is great for this.

Implementation

from typing import List
    
def find_all_subsets(nums: List[int]) -> List[List[int]]:
    res = []
    backtrack(0, [], nums, res)
    return res
    
def backtrack(i: int, curr_subset: List[int], nums: List[int], res: List[List[int]]) -> None:
    # Base case: if all elements have been considered, add the current subset to the
    # output.
    if i == len(nums):
        res.append(curr_subset[:])
        return
    # Include the current element and recursively explore all paths that branch from
    # this subset.
    curr_subset.append(nums[i])
    backtrack(i + 1, curr_subset, nums, res)
    # Exclude the current element and recursively explore all paths that branch from
    # this subset.
    curr_subset.pop()
    backtrack(i + 1, curr_subset, nums, res)

Complexity Analysis

Time complexity: O(2^n * n). The state space tree has a depth of n and a branching factor of 2. For each of the 2^n subsets created, we make a copy of them and add the copy to the output, which takes O(n) time.

Space complexity: O(n) because the maximum depth of the recursion tree is n.

N Queens

N Queens

There is a chessboard of size n x n. Your goal is to place n queens on the board such that no two queens attack each other. Return the number of distinct configurations where this is possible.

Example:

Input: n = 4
Output: 2

Intuition

Queens can move vertically, horizontally, and diagonally:

So, it's only possible to place a queen on a square of the board when:

• No other queen occupies the same row of that square.
• No other queen occupies the same column of that square.
• No other queen occupies either diagonal of that square.

Placing the queens - backtracking A straightforward strategy is to place one queen on the board at a time, making sure each new queen is placed on a safe square where it can't be attacked. If we can no longer safely place a queen, it means one or more of the previously placed queens need to be repositioned.

To make backtracking more efficient, we can place each queen on a new row. This way, we don't have to worry about conflicts between queens on the same row, and only need to check for an opposing queen on the same column and along the diagonals of the square where the new queen is placed.

A partial state space tree for this backtracking process is visualized below for n = 4:

Detecting opposing queens One challenge in this problem is determining if a square is attacked by another queen. We can use hash sets to efficiently check for this.

Note that we don't need a hash set for rows because we always place each queen on a different row. For columns, whenever we place a new queen on a square (r, c), we can add that square's column id (c) to a column hash set.

For diagonals: the diagonal can be identified using the id r - c, and the anti-diagonal is identified using the id r + c.

The key observation here is that, for any square (r, c), its diagonal can be identified using the id r - c, and its anti-diagonal is identified using the id r + c.

Placing and removing a queen Now that we have a way to identify opposing queens, we know the action of "placing" a queen means adding its column, diagonal, and anti-diagonal ids to their respective hash sets. Inversely, to remove a queen, we just remove those exact ids from the hash sets.

Implementation

from typing import Set
    
res = 0
    
def n_queens(n: int) -> int:
   dfs(0, set(), set(), set(), n)
   return res
    
def dfs(r: int, diagonals_set: Set[int], anti_diagonals_set: Set[int], cols_set: Set[int], n: int) -> None:
    global res
    # Termination condition: If we have reached the end of the rows, we've placed all
    # 'n' queens.
    if r == n:
        res += 1
        return
    for c in range(n):
        curr_diagonal = r - c
        curr_anti_diagonal = r + c
        # If there are queens on the current column, diagonal or anti-diagonal, skip
        # this square.
        if (c in cols_set or curr_diagonal in diagonals_set or curr_anti_diagonal in anti_diagonals_set):
            continue
        # Place the queen by marking the current column, diagonal, and anti-diagonal
        # as occupied.
        cols_set.add(c)
        diagonals_set.add(curr_diagonal)
        anti_diagonals_set.add(curr_anti_diagonal)
        # Recursively move to the next row to continue placing queens.
        dfs(r + 1, diagonals_set, anti_diagonals_set, cols_set, n)
        # Backtrack by removing the queen's marks.
        cols_set.remove(c)
        diagonals_set.remove(curr_diagonal)
        anti_diagonals_set.remove(curr_anti_diagonal)

Complexity Analysis

Time complexity: O(n!). For the first queen, there are n choices. For the second queen, there are n-a choices, where a denotes the number of squares on the second row attacked by the first queen. This trend approximately results in a factorial growth of the search space.

Space complexity: O(n) because the maximum depth of the recursion tree is n. The hash sets also contribute to this space complexity because they each store up to n values.

Combinations of a Sum

Combinations of a Sum

Given an integer array and a target value, find all unique combinations in the array where the numbers in each combination sum to the target. Each number in the array may be used an unlimited number of times in the combination.

Example:

Input: nums = [1, 2, 3], target = 4
Output: [[1, 1, 1, 1], [1, 1, 2], [1, 3], [2, 2]]

Constraints:

• All integers in nums are positive and unique.
• The target value is positive.
• The output must not contain duplicate combinations. For example, [1, 1, 2] and [1, 2, 1] are considered the same combination.

Intuition

Since we can use each integer in the input array as many times as we like, we can create an infinite number of combinations. To manage this, we need to narrow our search.

An important point that will help us with this is that all values in the integer array are positive integers. This means that as we add more values to a combination, its sum will increase. Therefore, we should stop building a combination once its sum is equal to or exceeds the target value.

To ensure a universal representation to avoid duplicates, we can represent combinations so that the integers appear in the same order as in the original array. We use a start_index to enforce this.

State space tree Consider the input array [1, 2, 3] and a target of 4.

One issue with this approach is that it resulted in duplicate combinations. To avoid these duplicates, we use start_index:

Initially, for the root combination, start_index is set to 0. As we recursively build each combination, start_index is updated to the index of the current element being added.

Implementation

We repurpose our target value - when we choose a number to add to a combination, we reduce the target value by that number. When we reach a target of 0, we've found a valid combination. If the target becomes negative, we terminate the current branch.

from typing import List
    
def combinations_of_sum_k(nums: List[int], target: int) -> List[List[int]]:
    res = []
    dfs([], 0, nums, target, res)
    return res
    
def dfs(combination: List[int], start_index: int, nums: List[int], target: int,
        res: List[List[int]]) -> None:
    # Termination condition: If the target is equal to 0, we found a combination
    # that sums to 'k'.
    if target == 0:
        res.append(combination[:])
        return
    # Termination condition: If the target is less than 0, no more valid
    # combinations can be created.
    if target < 0:
        return
    # Starting from start_index, explore all combinations after adding nums[i].
    for i in range(start_index, len(nums)):
        # Add the current number to create a new combination.
        combination.append(nums[i])
        # Recursively explore all paths that branch from this new combination.
        dfs(combination, i, nums, target - nums[i], res)
        # Backtrack.
        combination.pop()

Complexity Analysis

Time complexity: O(n^(target/m)), where n denotes the length of the array, and m denotes the smallest candidate. The recursion tree will branch down until the sum of the smallest candidates reaches or exceeds the target, resulting in a tree depth of target/m.

Space complexity: O(target/m), which includes the recursive call stack depth and the combination list.

Phone Keypad Combinations

Phone Keypad Combinations

You are given a string containing digits from 2 to 9 inclusive. Each digit maps to a set of letters as on a traditional phone keypad:

Return all possible letter combinations the input digits could represent.

Example: