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(n^2)$ 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])

for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
        compare(nums[i], nums[j]);
    }
}

for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        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)$ 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.

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

Input: nums = [1, 1, 1], target = 2
Output: [0, 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 []

function pairSumSortedBruteForce(nums, target) {
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
    return [];
}

public int[] pairSumSortedBruteForce(int[] nums, int target) {
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (nums[i] + nums[j] == target) {
                return new int[]{i, j};
            }
        }
    }
    return new int[]{};
}

This approach has a time complexity of $O(n^2)$, where $n$ 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 []

function pairSumSorted(nums, target) {
    let left = 0, right = nums.length - 1;
    while (left < right) {
        const 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++;
        // If the sum is larger, decrement the right pointer, aiming to decrease the
        // sum towards the target value.
        } else if (sum > target) {
            right--;
        // If the target pair is found, return its indexes.
        } else {
            return [left, right];
        }
    }
    return [];
}

public int[] pairSumSorted(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int 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++;
        // If the sum is larger, decrement the right pointer, aiming to decrease the
        // sum towards the target value.
        } else if (sum > target) {
            right--;
        // If the target pair is found, return its indexes.
        } else {
            return new int[]{left, right};
        }
    }
    return new int[]{};
}

Complexity Analysis

Time complexity: The time complexity of pair_sum_sorted is $O(n)$ because we perform approximately $n$ 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)$.

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.

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]

function tripletSumBruteForce(nums) {
    const n = nums.length;
    // Use a hash set to ensure we don't add duplicate triplets.
    const triplets = new Set();
    // Iterate through the indexes of all triplets.
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            for (let k = j + 1; k < n; k++) {
                if (nums[i] + nums[j] + nums[k] === 0) {
                    // Sort the triplet before including it in the hash set.
                    const triplet = [nums[i], nums[j], nums[k]].sort((a, b) => a - b);
                    triplets.add(JSON.stringify(triplet));
                }
            }
        }
    }
    return Array.from(triplets, item => JSON.parse(item));
}

public List<List<Integer>> tripletSumBruteForce(int[] nums) {
    int n = nums.length;
    // Use a hash set to ensure we don't add duplicate triplets.
    Set<List<Integer>> triplets = new HashSet<>();
    // Iterate through the indexes of all triplets.
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                if (nums[i] + nums[j] + nums[k] == 0) {
                    // Sort the triplet before including it in the hash set.
                    List<Integer> triplet = Arrays.asList(nums[i], nums[j], nums[k]);
                    Collections.sort(triplet);
                    triplets.add(triplet);
                }
            }
        }
    }
    return new ArrayList<>(triplets);
}

This solution is quite inefficient with a time complexity of $O(n^3)$, where $n$ 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:

$\underline{\text{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 ...

// To prevent duplicate triplets, ensure 'a' is not a repeat of the previous element
// in the sorted array.
if (i > 0 && nums[i] === nums[i - 1]) {
    continue;
}
// ... Find triplets ...

// To prevent duplicate triplets, ensure 'a' is not a repeat of the previous element
// in the sorted array.
if (i > 0 && nums[i] == nums[i - 1]) {
    continue;
}
// ... Find triplets ...

$\underline{\text{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

function tripletSum(nums) {
    const triplets = [];
    nums.sort((a, b) => a - b);
    for (let i = 0; i < nums.length; i++) {
        // 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 && nums[i] === nums[i - 1]) {
            continue;
        }
        // Find all pairs that sum to a target of '-a' ('-nums[i]').
        const pairs = pairSumSortedAllPairs(nums, i + 1, -nums[i]);
        for (const pair of pairs) {
            triplets.push([nums[i], ...pair]);
        }
    }
    return triplets;
}

function pairSumSortedAllPairs(nums, start, target) {
    const pairs = [];
    let left = start, right = nums.length - 1;
    while (left < right) {
        const sum = nums[left] + nums[right];
        if (sum === target) {
            pairs.push([nums[left], nums[right]]);
            left++; // To avoid duplicate '[b, c]' pairs, skip 'b' if it’s the same as the previous number.
            while (left < right && nums[left] === nums[left - 1]) {
                left++;
            }
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return pairs;
}

public List<List<Integer>> tripletSum(int[] nums) {
    List<List<Integer>> triplets = new ArrayList<>();
    Arrays.sort(nums);
    for (int i = 0; i < nums.length; i++) {
        // 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 && nums[i] == nums[i - 1]) {
            continue;
        }
        // Find all pairs that sum to a target of '-a' ('-nums[i]').
        List<List<Integer>> pairs = pairSumSortedAllPairs(nums, i + 1, -nums[i]);
        for (List<Integer> pair : pairs) {
            triplets.add(Arrays.asList(nums[i], pair.get(0), pair.get(1)));
        }
    }
    return triplets;
}

public List<List<Integer>> pairSumSortedAllPairs(int[] nums, int start, int target) {
    List<List<Integer>> pairs = new ArrayList<>();
    int left = start, right = nums.length - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            pairs.add(Arrays.asList(nums[left], nums[right]));
            left++; // To avoid duplicate '[b, c]' pairs, skip 'b' if it’s the same as the previous number.
            while (left < right && nums[left] == nums[left - 1]) {
                left++;
            }
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return pairs;
}

Complexity Analysis

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

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

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

Space complexity: The space complexity is $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(n^2)$. This is because the pair_sum_sorted_all_pairs function, in the worst case, can add approximately $n$ pairs to the output. Since this function is called approximately $n$ times, the overall space complexity is $O(n^2)$.

Test Cases

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

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

Input: s = 'abc123'
Output: False

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

function isPalindromeValid(s) {
    const isAlnum = (ch) => /[a-zA-Z0-9]/.test(ch);
    let left = 0, right = s.length - 1;
    while (left < right) {
        // Skip non-alphanumeric characters from the left.
        while (left < right && !isAlnum(s[left])) {
            left++;
        }
        // Skip non-alphanumeric characters from the right.
        while (left < right && !isAlnum(s[right])) {
            right--;
        }
        // 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++;
        right--;
    }
    return true;
}

public boolean isPalindromeValid(String s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        // Skip non-alphanumeric characters from the left.
        while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
            left++;
        }
        // Skip non-alphanumeric characters from the right.
        while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
            right--;
        }
        // If the characters at the left and right pointers don’t match, the string is
        // not a palindrome.
        if (s.charAt(left) != s.charAt(right)) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

Complexity Analysis

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

Space complexity: We only allocated a constant number of variables, so the space complexity is $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.

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:

ExampleCopy

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

function largestContainerBruteForce(heights) {
    const n = heights.length;
    let maxWater = 0;
    // Find the maximum amount of water stored between all pairs of lines.
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            const water = Math.min(heights[i], heights[j]) * (j - i);
            maxWater = Math.max(maxWater, water);
        }
    }
    return maxWater;
}

public int largestContainerBruteForce(int[] heights) {
    int n = heights.length;
    int maxWater = 0;
    // Find the maximum amount of water stored between all pairs of lines.
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int water = Math.min(heights[i], heights[j]) * (j - i);
            maxWater = Math.max(maxWater, water);
        }
    }
    return maxWater;
}

Searching through all possible pairs of values takes $O(n^2)$ time, where $n$ 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

function largestContainer(heights) {
    let maxWater = 0;
    let left = 0, right = heights.length - 1;
    while (left < right) {
        // Calculate the water contained between the current pair of lines.
        const water = Math.min(heights[left], heights[right]) * (right - left);
        maxWater = Math.max(maxWater, 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++;
        } else if (heights[left] > heights[right]) {
            right--;
        } else {
            left++;
            right--;
        }
    }
    return maxWater;
}

public int largestContainer(int[] heights) {
    int maxWater = 0;
    int left = 0, right = heights.length - 1;
    while (left < right) {
        // Calculate the water contained between the current pair of lines.
        int water = Math.min(heights[left], heights[right]) * (right - left);
        maxWater = Math.max(maxWater, 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++;
        } else if (heights[left] > heights[right]) {
            right--;
        } else {
            left++;
            right--;
        }
    }
    return maxWater;
}

Complexity Analysis

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

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

Test Cases

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

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]

function shiftZerosToTheEndNaive(nums) {
    const temp = new Array(nums.length).fill(0);
    let i = 0;
    // Add all non-zero elements to the left of 'temp'.
    for (const num of nums) {
        if (num !== 0) {
            temp[i] = num;
            i++;
        }
    }
    // Set 'nums' to 'temp'.
    for (let j = 0; j < nums.length; j++) {
        nums[j] = temp[j];
    }
}

public void shiftZerosToTheEndNaive(int[] nums) {
    int[] temp = new int[nums.length];
    int i = 0;
    // Add all non-zero elements to the left of 'temp'.
    for (int num : nums) {
        if (num != 0) {
            temp[i] = num;
            i++;
        }
    }
    // Set 'nums' to 'temp'.
    for (int j = 0; j < nums.length; j++) {
        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

function shiftZerosToTheEnd(nums) {
    // The 'left' pointer is used to position non-zero elements.
    let left = 0;
    // Iterate through the array using a 'right' pointer to locate non-zero
    // elements.
    for (let right = 0; right < nums.length; right++) {
        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++;
        }
    }
}

public void shiftZerosToTheEnd(int[] nums) {
    // The 'left' pointer is used to position non-zero elements.
    int left = 0;
    // Iterate through the array using a 'right' pointer to locate non-zero
    // elements.
    for (int right = 0; right < nums.length; right++) {
        if (nums[right] != 0) {
            if (right != left) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
            }
            // Increment 'left' since it now points to a position already occupied
            // by a non-zero element.
            left++;
        }
    }
}

Complexity Analysis

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

Space complexity: The space complexity is $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.

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

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

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.

2. Find the rightmost successor to the pivot.

3. Swap the rightmost successor with the pivot to increase the lexicographical order of the suffix.

4. 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)

function nextLexicographicalSequence(s) {
    const letters = s.split('');
    // Locate the pivot, which is the first character from the right that breaks
    // non-increasing order. Start searching from the second-to-last position.
    let pivot = letters.length - 2;
    while (pivot >= 0 && letters[pivot] >= letters[pivot + 1]) {
        pivot--;
    }
    // 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 letters.reverse().join('');
    }
    // Find the rightmost successor to the pivot.
    let rightmostSuccessor = letters.length - 1;
    while (letters[rightmostSuccessor] <= letters[pivot]) {
        rightmostSuccessor--;
    }
    // Swap the rightmost successor with the pivot to increase the lexicographical
    // order of the suffix.
    [letters[pivot], letters[rightmostSuccessor]] = [letters[rightmostSuccessor], letters[pivot]];
    // Reverse the suffix after the pivot to minimize its permutation.
    let left = pivot + 1, right = letters.length - 1;
    while (left < right) {
        [letters[left], letters[right]] = [letters[right], letters[left]];
        left++;
        right--;
    }
    return letters.join('');
}

public String nextLexicographicalSequence(String s) {
    char[] letters = s.toCharArray();
    // Locate the pivot, which is the first character from the right that breaks
    // non-increasing order. Start searching from the second-to-last position.
    int pivot = letters.length - 2;
    while (pivot >= 0 && letters[pivot] >= letters[pivot + 1]) {
        pivot--;
    }
    // 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 new StringBuilder(new String(letters)).reverse().toString();
    }
    // Find the rightmost successor to the pivot.
    int rightmostSuccessor = letters.length - 1;
    while (letters[rightmostSuccessor] <= letters[pivot]) {
        rightmostSuccessor--;
    }
    // Swap the rightmost successor with the pivot to increase the lexicographical
    // order of the suffix.
    char temp = letters[pivot];
    letters[pivot] = letters[rightmostSuccessor];
    letters[rightmostSuccessor] = temp;
    // Reverse the suffix after the pivot to minimize its permutation.
    int left = pivot + 1, right = letters.length - 1;
    while (left < right) {
        char t = letters[left];
        letters[left] = letters[right];
        letters[right] = t;
        left++;
        right--;
    }
    return new String(letters);
}

Complexity Analysis

Time complexity: The time complexity of next_lexicographical_sequence is $O(n)$, where $n$ 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)$ time.

Space complexity: The space complexity is $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.

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)$. 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)$, 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)$, 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.

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

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(n^2)$, where $n$ 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))$ 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(n^2)$ 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)$ 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 []

function pairSumUnsortedTwoPass(nums, target) {
    const numMap = new Map();
    // First pass: Populate the hash map with each number and its index.
    for (let i = 0; i < nums.length; i++) {
        numMap.set(nums[i], i);
    }
    // Second pass: Check for each number's complement in the hash map.
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (numMap.has(complement) && numMap.get(complement) !== i) {
            return [i, numMap.get(complement)];
        }
    }
    return [];
}

public int[] pairSumUnsortedTwoPass(int[] nums, int target) {
    Map<Integer, Integer> numMap = new HashMap<>();
    // First pass: Populate the hash map with each number and its index.
    for (int i = 0; i < nums.length; i++) {
        numMap.put(nums[i], i);
    }
    // Second pass: Check for each number's complement in the hash map.
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (numMap.containsKey(complement) && numMap.get(complement) != i) {
            return new int[]{i, numMap.get(complement)};
        }
    }
    return new int[]{};
}

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 []

function pairSumUnsorted(nums, target) {
    const hashmap = new Map();
    for (let i = 0; i < nums.length; i++) {
        const x = nums[i];
        if (hashmap.has(target - x)) {
            return [hashmap.get(target - x), i];
        }
        hashmap.set(x, i);
    }
    return [];
}

public int[] pairSumUnsorted(int[] nums, int target) {
    Map<Integer, Integer> hashmap = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int x = nums[i];
        if (hashmap.containsKey(target - x)) {
            return new int[]{hashmap.get(target - x), i};
        }
        hashmap.put(x, i);
    }
    return new int[]{};
}

Complexity Analysis

Time complexity: The time complexity of pair_sum_unsorted is $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)$ since the hash map can grow up to $n$ 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.

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:

ExampleCopy

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(n^2)$ 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)$ 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 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

function verifySudokuBoard(board) {
    // Create hash sets for each row, column, and subgrid to keep track of numbers
    // previously seen on any given row, column, or subgrid.
    const rowSets = Array.from({ length: 9 }, () => new Set());
    const columnSets = Array.from({ length: 9 }, () => new Set());
    const subgridSets = Array.from({ length: 3 }, () => Array.from({ length: 3 }, () => new Set()));
    for (let r = 0; r < 9; r++) {
        for (let c = 0; c < 9; c++) {
            const num = board[r][c];
            if (num === 0) {
                continue;
            }
            // Check if 'num' has been seen in the current row, column, or subgrid.
            if (rowSets[r].has(num)) {
                return false;
            }
            if (columnSets[c].has(num)) {
                return false;
            }
            if (subgridSets[Math.floor(r / 3)][Math.floor(c / 3)].has(num)) {
                return false;
            }
            // If we passed the above checks, mark this value as seen by adding it to
            // its corresponding hash sets.
            rowSets[r].add(num);
            columnSets[c].add(num);
            subgridSets[Math.floor(r / 3)][Math.floor(c / 3)].add(num);
        }
    }
    return true;
}

public boolean verifySudokuBoard(int[][] board) {
    // Create hash sets for each row, column, and subgrid to keep track of numbers
    // previously seen on any given row, column, or subgrid.
    List<Set<Integer>> rowSets = new ArrayList<>();
    List<Set<Integer>> columnSets = new ArrayList<>();
    List<List<Set<Integer>>> subgridSets = new ArrayList<>();
    for (int i = 0; i < 9; i++) {
        rowSets.add(new HashSet<>());
        columnSets.add(new HashSet<>());
    }
    for (int i = 0; i < 3; i++) {
        List<Set<Integer>> row = new ArrayList<>();
        for (int j = 0; j < 3; j++) {
            row.add(new HashSet<>());
        }
        subgridSets.add(row);
    }
    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) {
            int num = board[r][c];
            if (num == 0) {
                continue;
            }
            // Check if 'num' has been seen in the current row, column, or subgrid.
            if (rowSets.get(r).contains(num)) {
                return false;
            }
            if (columnSets.get(c).contains(num)) {
                return false;
            }
            if (subgridSets.get(r / 3).get(c / 3).contains(num)) {
                return false;
            }
            // If we passed the above checks, mark this value as seen by adding it to
            // its corresponding hash sets.
            rowSets.get(r).add(num);
            columnSets.get(c).add(num);
            subgridSets.get(r / 3).get(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)$. However, to better understand the efficiency of our algorithm in a broader context, let's use $n$ 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(n^2)$ because we iterate through each cell in the board once, and perform constant-time hash set operations.

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

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\cdot n(m+n))$, where $m \cdot n$ denotes the number of 0s, and ($m+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)$ 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)$ 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

function zeroStripingHashSets(matrix) {
    if (!matrix || matrix.length === 0 || matrix[0].length === 0) {
        return;
    }
    const m = matrix.length, n = matrix[0].length;
    const zeroRows = new Set(), zeroCols = new 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 (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            if (matrix[r][c] === 0) {
                zeroRows.add(r);
                zeroCols.add(c);
            }
        }
    }
    // Pass 2: Set any cell in the matrix to zero if its row index is in 'zeroRows'
    // or its column index is in 'zeroCols'.
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            if (zeroRows.has(r) || zeroCols.has(c)) {
                matrix[r][c] = 0;
            }
        }
    }
}

public void zeroStripingHashSets(int[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return;
    }
    int m = matrix.length, n = matrix[0].length;
    Set<Integer> zeroRows = new HashSet<>();
    Set<Integer> zeroCols = new HashSet<>();
    // Pass 1: Traverse through the matrix to identify the rows and columns
    // containing zeros and store their indexes in the appropriate hash sets.
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (matrix[r][c] == 0) {
                zeroRows.add(r);
                zeroCols.add(c);
            }
        }
    }
    // Pass 2: Set any cell in the matrix to zero if its row index is in 'zeroRows'
    // or its column index is in 'zeroCols'.
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (zeroRows.contains(r) || zeroCols.contains(c)) {
                matrix[r][c] = 0;
            }
        }
    }
}

Complexity Analysis

Time complexity: The time complexity of zero_striping_hash_sets is $O(m\cdot 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)$ 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

function zeroStriping(matrix) {
    if (!matrix || matrix.length === 0 || matrix[0].length === 0) {
        return;
    }
    const m = matrix.length, n = matrix[0].length;
    // Check if the first row initially contains a zero.
    let firstRowHasZero = false;
    for (let c = 0; c < n; c++) {
        if (matrix[0][c] === 0) {
            firstRowHasZero = true;
            break;
        }
    }
    // Check if the first column initially contains a zero.
    let firstColHasZero = false;
    for (let r = 0; r < m; r++) {
        if (matrix[r][0] === 0) {
            firstColHasZero = 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 (let r = 1; r < m; r++) {
        for (let c = 1; c < n; c++) {
            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 (let r = 1; r < m; r++) {
        for (let c = 1; c < n; c++) {
            if (matrix[0][c] === 0 || 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 (firstRowHasZero) {
        for (let c = 0; c < n; c++) {
            matrix[0][c] = 0;
        }
    }
    // If the first column had a zero initially, set all elements in the first column
    // to zero.
    if (firstColHasZero) {
        for (let r = 0; r < m; r++) {
            matrix[r][0] = 0;
        }
    }
}

public void zeroStriping(int[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return;
    }
    int m = matrix.length, n = matrix[0].length;
    // Check if the first row initially contains a zero.
    boolean firstRowHasZero = false;
    for (int c = 0; c < n; c++) {
        if (matrix[0][c] == 0) {
            firstRowHasZero = true;
            break;
        }
    }
    // Check if the first column initially contains a zero.
    boolean firstColHasZero = false;
    for (int r = 0; r < m; r++) {
        if (matrix[r][0] == 0) {
            firstColHasZero = 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 (int r = 1; r < m; r++) {
        for (int c = 1; c < n; c++) {
            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 (int r = 1; r < m; r++) {
        for (int c = 1; c < n; c++) {
            if (matrix[0][c] == 0 || 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 (firstRowHasZero) {
        for (int c = 0; c < n; c++) {
            matrix[0][c] = 0;
        }
    }
    // If the first column had a zero initially, set all elements in the first column
    // to zero.
    if (firstColHasZero) {
        for (int r = 0; r < m; r++) {
            matrix[r][0] = 0;
        }
    }
}

Complexity Analysis

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

• Checking the first row for zeros takes $O(m)$ time, and checking the first column takes $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\cdot n)$ time.
• Finally, we iterate through the first row and first column up to once each, which takes $O(m)$ and $O(n)$ time, respectively.

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

Space complexity: The space complexity is $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.

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

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(n\log (n))$ time, where $n$ 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

function longestChainOfConsecutiveNumbersBruteForce(nums) {
    if (!nums || nums.length === 0) {
        return 0;
    }
    let longestChain = 0;
    // Look for chains of consecutive numbers that start from each number.
    for (const num of nums) {
        let currentNum = num;
        let currentChain = 1;
        // Continue to find the next consecutive numbers in the chain.
        while (nums.includes(currentNum + 1)) {
            currentNum += 1;
            currentChain += 1;
        }
        longestChain = Math.max(longestChain, currentChain);
    }
    return longestChain;
}

public int longestChainOfConsecutiveNumbersBruteForce(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int longestChain = 0;
    // Look for chains of consecutive numbers that start from each number.
    for (int num : nums) {
        int currentNum = num;
        int currentChain = 1;
        // Continue to find the next consecutive numbers in the chain.
        while (contains(nums, currentNum + 1)) {
            currentNum += 1;
            currentChain += 1;
        }
        longestChain = Math.max(longestChain, currentChain);
    }
    return longestChain;
}

private boolean contains(int[] nums, int target) {
    for (int x : nums) {
        if (x == target) {
            return true;
        }
    }
    return false;
}

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

• The outer for-loop iterates through each element, which takes $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)$ 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(n^3)$ to $O(n^2)$.

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(n^2)$ to $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

function longestChainOfConsecutiveNumbers(nums) {
    if (!nums || nums.length === 0) {
        return 0;
    }
    const numSet = new Set(nums);
    let longestChain = 0;
    for (const num of numSet) {
        // If the current number is the smallest number in its chain, search for
        // the length of its chain.
        if (!numSet.has(num - 1)) {
            let currentNum = num;
            let currentChain = 1;
            // Continue to find the next consecutive numbers in the chain.
            while (numSet.has(currentNum + 1)) {
                currentNum += 1;
                currentChain += 1;
            }
            longestChain = Math.max(longestChain, currentChain);
        }
    }
    return longestChain;
}

public int longestChainOfConsecutiveNumbers(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    Set<Integer> numSet = new HashSet<>();
    for (int num : nums) {
        numSet.add(num);
    }
    int longestChain = 0;
    for (int num : numSet) {
        // If the current number is the smallest number in its chain, search for
        // the length of its chain.
        if (!numSet.contains(num - 1)) {
            int currentNum = num;
            int currentChain = 1;
            // Continue to find the next consecutive numbers in the chain.
            while (numSet.contains(currentNum + 1)) {
                currentNum += 1;
                currentChain += 1;
            }
            longestChain = Math.max(longestChain, currentChain);
        }
    }
    return longestChain;
}

Complexity Analysis

Time complexity: The time complexity of longest_chain_of_consecutive_numbers is $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)$: the outer for-loop runs $n$ times, and the inner while-loop runs a total of $n$ times across all iterations, resulting in a combined time complexity of $O(n+n)=O(n)$.

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

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 $\underline{\text{2}}$ (i.e., [1, 1⋅$\underline{\text{2}}$ = 2, 2⋅$\underline{\text{2}}$ = 4]).
• (5, 15, 45): This is a geometric sequence with a ratio of $\underline{\text{3}}$ (i.e., [5, 5⋅$\underline{\text{3}}$ = 15, 15⋅$\underline{\text{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:

ExampleCopy

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(n^3)$, where $n$ 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(n^2)$ 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

function geometricSequenceTriplets(nums, r) {
    // 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.
    const leftMap = new Map();
    const rightMap = new Map();
    let count = 0;
    // Populate 'rightMap' with the frequency of each element in the array.
    for (const x of nums) {
        rightMap.set(x, (rightMap.get(x) || 0) + 1);
    }
    // Search for geometric triplets that have x as the center.
    for (const x of nums) {
        // Decrement the frequency of x in 'rightMap' since x is now being
        // processed and is no longer to the right.
        rightMap.set(x, rightMap.get(x) - 1);
        if (x % r === 0) {
            const leftCount = leftMap.get(x / r) || 0;
            const rightCount = rightMap.get(x * r) || 0;
            count += leftCount * rightCount;
        }
        // Increment the frequency of x in 'leftMap' since it'll be a part of the
        // left side of the array once we iterate to the next value of `x`.
        leftMap.set(x, (leftMap.get(x) || 0) + 1);
    }
    return count;
}

public long geometricSequenceTriplets(int[] nums, int r) {
    // Track frequencies of elements to the left and right of the center element.
    Map<Long, Long> leftMap = new HashMap<>();
    Map<Long, Long> rightMap = new HashMap<>();
    long count = 0;
    // Populate 'rightMap' with the frequency of each element in the array.
    for (int x : nums) {
        rightMap.put((long) x, rightMap.getOrDefault((long) x, 0L) + 1L);
    }
    // Search for geometric triplets that have x as the center.
    for (int x : nums) {
        // Decrement the frequency of x in 'rightMap' since x is now being
        // processed and is no longer to the right.
        rightMap.put((long) x, rightMap.get((long) x) - 1L);
        if (x % r == 0) {
            long leftCount = leftMap.getOrDefault((long) x / r, 0L);
            long rightCount = rightMap.getOrDefault((long) x * r, 0L);
            count += leftCount * rightCount;
        }
        // Increment the frequency of x in 'leftMap' since it'll be a part of the
        // left side of the array once we iterate to the next value of `x`.
        leftMap.put((long) x, leftMap.getOrDefault((long) x, 0L) + 1L);
    }
    return count;
}

Complexity Analysis

Time complexity: The time complexity of geometric_sequence_triplets is $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)$ because the hash maps can grow up to $n$ in size.

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

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

public class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
        this.next = null;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.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.

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

function linkedListReversal(head) {
    let currNode = head, prevNode = null;
    // Reverse the direction of each node's pointer until 'currNode' is null.
    while (currNode) {
        const nextNode = currNode.next;
        currNode.next = prevNode;
        prevNode = currNode;
        currNode = nextNode;
    }
    // 'prevNode' will be pointing at the head of the reversed linked list.
    return prevNode;
}

public ListNode linkedListReversal(ListNode head) {
    ListNode currNode = head, prevNode = null;
    // Reverse the direction of each node's pointer until 'currNode' is null.
    while (currNode != null) {
        ListNode nextNode = currNode.next;
        currNode.next = prevNode;
        prevNode = currNode;
        currNode = nextNode;
    }
    // 'prevNode' will be pointing at the head of the reversed linked list.
    return prevNode;
}

Complexity Analysis

Time complexity: The time complexity of linked_list_reversal is $O(n)$, where $n$ 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)$.

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

function linkedListReversalRecursive(head) {
    // Base cases.
    if (!head || !head.next) {
        return head;
    }
    // Recursively reverse the sublist starting at the next node.
    const newHead = linkedListReversalRecursive(head.next);
    // Connect the reversed sublist to the head node to fully reverse the entire linked list.
    head.next.next = head;
    head.next = null;
    return newHead;
}

public ListNode linkedListReversalRecursive(ListNode head) {
    // Base cases.
    if (head == null || head.next == null) {
        return head;
    }
    // Recursively reverse the sublist starting at the next node.
    ListNode newHead = linkedListReversalRecursive(head.next);
    // Connect the reversed sublist to the head node to fully reverse the entire linked list.
    head.next.next = head;
    head.next = null;
    return newHead;
}

Complexity Analysis

Time complexity: The time complexity of linked_list_reversal_recursive is $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)$ due to the stack space taken up by the recursive call stack, which grows up to $n$ levels deep because $n$ 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.

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

function removeKthLastNode(head, k) {
    // A dummy node to ensure there's a node before 'head' in case we need to remove
    // the head node.
    const dummy = new ListNode(-1);
    dummy.next = head;
    let trailer = dummy, leader = dummy;
    // Advance 'leader' k steps ahead.
    for (let i = 0; i < k; i++) {
        leader = leader.next;
        // If k is larger than the length of the linked list, no node needs to be
        // removed.
        if (!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;
}

public ListNode removeKthLastNode(ListNode head, int k) {
    // A dummy node to ensure there's a node before 'head' in case we need to remove
    // the head node.
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    ListNode trailer = dummy, leader = dummy;
    // Advance 'leader' k steps ahead.
    for (int i = 0; i < k; i++) {
        leader = leader.next;
        // If k is larger than the length of the linked list, no node needs to be
        // removed.
        if (leader == null) {
            return head;
        }
    }
    // Move 'leader' to the end of the linked list, keeping 'trailer' k nodes behind.
    while (leader.next != null) {
        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)$. This is because the algorithm first traverses at most $n$ 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)$.

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

Example:

ExampleCopy

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

function linkedListIntersection(headA, headB) {
    let ptrA = headA, ptrB = headB;
    // Traverse through list A with 'ptrA' and list B with 'ptrB' until they meet.
    while (ptrA !== ptrB) {
        // Traverse list A -> list B by first traversing 'ptrA' and then, upon
        // reaching the end of list A, continue the traversal from the head of list B.
        ptrA = ptrA ? ptrA.next : headB;
        // Simultaneously, traverse list B -> list A.
        ptrB = ptrB ? ptrB.next : headA;
    }
    // At this point, 'ptrA' and 'ptrB' either point to the intersection node or both
    // are null if the lists do not intersect. Return either pointer.
    return ptrA;
}

public ListNode linkedListIntersection(ListNode headA, ListNode headB) {
    ListNode ptrA = headA, ptrB = headB;
    // Traverse through list A with 'ptrA' and list B with 'ptrB' until they meet.
    while (ptrA != ptrB) {
        // Traverse list A -> list B by first traversing 'ptrA' and then, upon
        // reaching the end of list A, continue the traversal from the head of list B.
        ptrA = (ptrA != null) ? ptrA.next : headB;
        // Simultaneously, traverse list B -> list A.
        ptrB = (ptrB != null) ? ptrB.next : headA;
    }
    // At this point, 'ptrA' and 'ptrB' either point to the intersection node or both
    // are null if the lists do not intersect. Return either pointer.
    return ptrA;
}

Complexity Analysis

Time complexity: The time complexity of linked_list_intersection is $O(n+m)$, where $n$ and $m$ 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)$.

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]

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

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:

3. Move a key-value pair to the most recent end of the cache.

4. 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
$\underline{\text{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?

$\underline{\text{Singly vs. doubly linked list}}$

Adding or removing a node from the head of a linked list takes $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)$ 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)$ 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:

$\underline{\text{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)$ 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

class DoublyLinkedListNode {
    constructor(key, val) {
        this.key = key;
        this.val = val;
        this.next = null;
        this.prev = null;
    }
}

public class DoublyLinkedListNode {
    int key;
    int val;
    DoublyLinkedListNode next;
    DoublyLinkedListNode prev;

    public DoublyLinkedListNode(int key, int val) {
        this.key = key;
        this.val = val;
        this.next = null;
        this.prev = null;
    }
}

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

addToTail(node) {
    const prevNode = this.tail.prev;
    node.prev = prevNode;
    node.next = this.tail;
    prevNode.next = node;
    this.tail.prev = node;
}

public void addToTail(DoublyLinkedListNode node) {
    DoublyLinkedListNode prevNode = this.tail.prev;
    node.prev = prevNode;
    node.next = this.tail;
    prevNode.next = node;
    this.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

removeNode(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
}

public void removeNode(DoublyLinkedListNode node) {
    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

class DoublyLinkedListNode {
    constructor(key, val) {
        this.key = key;
        this.val = val;
        this.next = null;
        this.prev = null;
    }
}

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        // A hash map that maps keys to nodes.
        this.hashmap = new Map();
        // Initialize the head and tail dummy nodes and connect them to 
        // each other to establish a basic two-node doubly linked list.
        this.head = new DoublyLinkedListNode(-1, -1);
        this.tail = new DoublyLinkedListNode(-1, -1);
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }

    get(key) {
        if (!this.hashmap.has(key)) {
            return -1;
        }
        // To make this key the most recently used, remove its node and
        // re-add it to the tail of the linked list.
        const node = this.hashmap.get(key);
        this.removeNode(node);
        this.addToTail(node);
        return node.val;
    }

    put(key, value) {
        // If a node with this key already exists, remove it from the
        // linked list.
        if (this.hashmap.has(key)) {
            this.removeNode(this.hashmap.get(key));
        }
        const node = new DoublyLinkedListNode(key, value);
        this.hashmap.set(key, node);
        // Remove the least recently used node from the cache if adding
        // this new node will result in an overflow.
        if (this.hashmap.size > this.capacity) {
            const lruNode = this.head.next;
            this.hashmap.delete(lruNode.key);
            this.removeNode(lruNode);
        }
        this.addToTail(node);
    }

    addToTail(node) {
        const prevNode = this.tail.prev;
        node.prev = prevNode;
        node.next = this.tail;
        prevNode.next = node;
        this.tail.prev = node;
    }

    removeNode(node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
}

class DoublyLinkedListNode {
    int key;
    int val;
    DoublyLinkedListNode next;
    DoublyLinkedListNode prev;

    public DoublyLinkedListNode(int key, int val) {
        this.key = key;
        this.val = val;
        this.next = null;
        this.prev = null;
    }
}

public class LRUCache {
    private int capacity;
    // A hash map that maps keys to nodes.
    private Map<Integer, DoublyLinkedListNode> hashmap;
    private DoublyLinkedListNode head;
    private DoublyLinkedListNode tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.hashmap = new HashMap<>();
        // Initialize the head and tail dummy nodes and connect them to 
        // each other to establish a basic two-node doubly linked list.
        this.head = new DoublyLinkedListNode(-1, -1);
        this.tail = new DoublyLinkedListNode(-1, -1);
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }

    public int get(int key) {
        if (!hashmap.containsKey(key)) {
            return -1;
        }
        // To make this key the most recently used, remove its node and
        // re-add it to the tail of the linked list.
        DoublyLinkedListNode node = hashmap.get(key);
        removeNode(node);
        addToTail(node);
        return node.val;
    }

    public void put(int key, int value) {
        // If a node with this key already exists, remove it from the
        // linked list.
        if (hashmap.containsKey(key)) {
            removeNode(hashmap.get(key));
        }
        DoublyLinkedListNode node = new DoublyLinkedListNode(key, value);
        hashmap.put(key, node);
        // Remove the least recently used node from the cache if adding
        // this new node will result in an overflow.
        if (hashmap.size() > capacity) {
            DoublyLinkedListNode lruNode = head.next;
            hashmap.remove(lruNode.key);
            removeNode(lruNode);
        }
        addToTail(node);
    }

    public void addToTail(DoublyLinkedListNode node) {
        DoublyLinkedListNode prevNode = this.tail.prev;
        node.prev = prevNode;
        node.next = this.tail;
        prevNode.next = node;
        this.tail.prev = node;
    }

    public void removeNode(DoublyLinkedListNode node) {
        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)$ 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)$ time complexity.

Space complexity: The overall space complexity of this solution is $O(n)$, where $n$ is the capacity of the cache. This is because both the doubly linked list and hash map can each occupy $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.

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

Example 1:

ExampleCopy

Output: True

Example 2:

ExampleCopy

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)$ 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

function palindromicLinkedList(head) {
    // Find the middle of the linked list and then reverse the second half of the
    // linked list starting at this midpoint.
    const mid = findMiddle(head);
    const secondHead = reverseList(mid);
    // Compare the first half and the reversed second half of the list
    let ptr1 = head, ptr2 = secondHead;
    let res = true;
    while (ptr2) {
        if (ptr1.val !== ptr2.val) {
            res = false;
        }
        ptr1 = ptr1.next;
        ptr2 = ptr2.next;
    }
    return res;
}

// From the 'Reverse Linked List' problem.
function reverseList(head) {
    let prevNode = null, currNode = head;
    while (currNode) {
        const nextNode = currNode.next;
        currNode.next = prevNode;
        prevNode = currNode;
        currNode = nextNode;
    }
    return prevNode;
}

// From the 'Linked List Midpoint' problem.
function findMiddle(head) {
    let slow = head, fast = head;
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

public boolean palindromicLinkedList(ListNode head) {
    // Find the middle of the linked list and then reverse the second half of the
    // linked list starting at this midpoint.
    ListNode mid = findMiddle(head);
    ListNode secondHead = reverseList(mid);
    // Compare the first half and the reversed second half of the list
    ListNode ptr1 = head, ptr2 = secondHead;
    boolean res = true;
    while (ptr2 != null) {
        if (ptr1.val != ptr2.val) {
            res = false;
        }
        ptr1 = ptr1.next;
        ptr2 = ptr2.next;
    }
    return res;
}

// From the 'Reverse Linked List' problem.
public ListNode reverseList(ListNode head) {
    ListNode prevNode = null, currNode = head;
    while (currNode != null) {
        ListNode nextNode = currNode.next;
        currNode.next = prevNode;
        prevNode = currNode;
        currNode = nextNode;
    }
    return prevNode;
}

// From the 'Linked List Midpoint' problem.
public ListNode findMiddle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

Complexity Analysis

Time complexity: The time complexity of palindromic_linked_list is $O(n)$, where $n$ 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)$.

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.

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

class MultiLevelListNode {
    constructor(val = 0, next = null, child = null) {
        this.val = val;
        this.next = next;
        this.child = child;
    }
}

public class MultiLevelListNode {
    int val;
    MultiLevelListNode next;
    MultiLevelListNode child;

    public MultiLevelListNode(int val) {
        this.val = val;
        this.next = null;
        this.child = null;
    }

    public MultiLevelListNode(int val, MultiLevelListNode next, MultiLevelListNode child) {
        this.val = val;
        this.next = next;
        this.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

function flattenMultiLevelList(head) {
    if (!head) {
        return null;
    }
    let tail = head;
    // Find the tail of the linked list at the first level.
    while (tail.next) {
        tail = tail.next;
    }
    let 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 = null;
            while (tail.next) {
                tail = tail.next;
            }
        }
        curr = curr.next;
    }
    return head;
}

public MultiLevelListNode flattenMultiLevelList(MultiLevelListNode head) {
    if (head == null) {
        return null;
    }
    MultiLevelListNode tail = head;
    // Find the tail of the linked list at the first level.
    while (tail.next != null) {
        tail = tail.next;
    }
    MultiLevelListNode 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 != null) {
        if (curr.child != null) {
            tail.next = curr.child;
            curr.child = null;
            while (tail.next != null) {
                tail = tail.next;
            }
        }
        curr = curr.next;
    }
    return head;
}

Complexity Analysis

Time complexity: The time complexity of flatten_multi_level_list is $O(n)$, where $n$ 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)$.

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.

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:

ExampleCopy

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

function linkedListLoopNaive(head) {
    const visited = new Set();
    let curr = head;
    while (curr) {
        // Cycle detected if the current node has already been visited.
        if (visited.has(curr)) {
            return true;
        }
        visited.add(curr);
        curr = curr.next;
    }
    return false;
}

public boolean linkedListLoopNaive(ListNode head) {
    Set<ListNode> visited = new HashSet<>();
    ListNode curr = head;
    while (curr != null) {
        // Cycle detected if the current node has already been visited.
        if (visited.contains(curr)) {
            return true;
        }
        visited.add(curr);
        curr = curr.next;
    }
    return false;
}

This solution takes $O(n)$ time, where $n$ is the number of nodes in the linked list, since each node is visited once. However, this comes at the cost of $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

function linkedListLoop(head) {
    let slow = head, fast = head;
    // Check both 'fast' and 'fast.next' to avoid null pointer exceptions when we
    // perform 'fast.next' and 'fast.next.next'.
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        if (fast === slow) {
            return true;
        }
    }
    return false;
}

public boolean linkedListLoop(ListNode head) {
    ListNode slow = head, fast = head;
    // Check both 'fast' and 'fast.next' to avoid null pointer exceptions when we
    // perform 'fast.next' and 'fast.next.next'.
    while (fast != null && fast.next != null) {
        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)$ 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)$.

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

Example 1:

ExampleCopy

Output: Node 4

Example 2:

ExampleCopy

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)$ 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

function linkedListMidpoint(head) {
    let slow = head, 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 && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

public ListNode linkedListMidpoint(ListNode head) {
    ListNode slow = head, 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 != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

Complexity Analysis

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

Space complexity: The space complexity is $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.

Input: n = 23
Output: True

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

function happyNumber(n) {
    let slow = n, fast = n;
    while (true) {
        slow = getNextNum(slow);
        fast = getNextNum(getNextNum(fast));
        if (fast === 1) {
            return true;
        // If the fast and slow pointers meet, a cycle is detected. Hence, 'n' is not
        // a happy number.
        } else if (fast === slow) {
            return false;
        }
    }
}

function getNextNum(x) {
    let nextNum = 0;
    while (x > 0) {
        // Extract the last digit of 'x'.
        const digit = x % 10;
        // Truncate (remove) the last digit from 'x' using floor division.
        x = Math.floor(x / 10);
        // Add the square of the extracted digit to the sum.
        nextNum += digit * digit;
    }
    return nextNum;
}

public boolean happyNumber(int n) {
    int slow = n, fast = n;
    while (true) {
        slow = getNextNum(slow);
        fast = getNextNum(getNextNum(fast));
        if (fast == 1) {
            return true;
        // If the fast and slow pointers meet, a cycle is detected. Hence, 'n' is not
        // a happy number.
        } else if (fast == slow) {
            return false;
        }
    }
}

public int getNextNum(int x) {
    int nextNum = 0;
    while (x > 0) {
        // Extract the last digit of 'x'.
        int 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.
        nextNum += digit * digit;
    }
    return nextNum;
}

Complexity Analysis

Time complexity: The time complexity of happy_number is $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)$.

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 $n$ as the result obtained by summing the squares of the digits of $n$.

1) Upper limit for the next number For any number $n$ 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 $n$ has 1 or 2 digits, it’s possible for the next number to be larger than $n$ (e.g., the next number of 99 is 162, which is one digit longer).

• If a number $n$ has 3 or more digits, the next number is always smaller than the original value of $n$. 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 $n$ larger than 243 will have the next number smaller than $n$. 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)$.

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

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

Conclusion When $n$ is less than 243, the time complexity is O(1), and when $n$ is greater than 243, the time complexity is $O(\log(n))$. Therefore, the overall time complexity of the algorithm is $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.

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(n^2)$ time complexity, or worse. When using a sliding window, the subcomponent(s) we’re looking for can usually be found in $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

let left = 0, 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 === fixedWindowSize) {
        // Process the current window.
        result = processCurrentWindow();
        left++;
    }
    right++;
}

int left = 0, 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 == fixedWindowSize) {
        // Process the current window.
        result = processCurrentWindow();
        left++;
    }
    right++;
}

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

let left = 0, right = 0;
while (right < n) {
    // While the condition is violated, the window is invalid, so shrink the window by
    // advancing the left pointer.
    while (conditionIsViolated) {
        left++;
    }
    // Once the window is valid, process it and then expand the window by advancing the
    // right pointer.
    result = processCurrentWindow();
    right++;
}

int left = 0, right = 0;
while (right < n) {
    // While the condition is violated, the window is invalid, so shrink the window by
    // advancing the left pointer.
    while (conditionIsViolated) {
        left++;
    }
    // Once the window is valid, process it and then expand the window by advancing the
    // right pointer.
    result = processCurrentWindow();
    right++;
}

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

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

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

function substringAnagrams(s, t) {
    const lenS = s.length, lenT = t.length;
    if (lenT > lenS) {
        return 0;
    }
    let count = 0;
    const expectedFreqs = new Array(26).fill(0);
    const windowFreqs = new Array(26).fill(0);
    const aCharCode = 'a'.charCodeAt(0);
    // Populate 'expectedFreqs' with the characters in string 't'.
    for (let i = 0; i < lenT; i++) {
        expectedFreqs[t.charCodeAt(i) - aCharCode]++;
    }
    const arraysMatch = (arr1, arr2) => arr1.every((val, idx) => val === arr2[idx]);
    let left = 0, right = 0;
    while (right < lenS) {
        // Add the character at the right pointer to 'windowFreqs' before sliding the
        // window.
        windowFreqs[s.charCodeAt(right) - aCharCode]++;
        // 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 === lenT) {
            if (arraysMatch(windowFreqs, expectedFreqs)) {
                count++;
            }
            // Remove the character at the left pointer from 'windowFreqs' before
            // advancing the left pointer.
            windowFreqs[s.charCodeAt(left) - aCharCode]--;
            left++;
        }
        right++;
    }
    return count;
}

public int substringAnagrams(String s, String t) {
    int lenS = s.length(), lenT = t.length();
    if (lenT > lenS) {
        return 0;
    }
    int count = 0;
    int[] expectedFreqs = new int[26];
    int[] windowFreqs = new int[26];
    // Populate 'expectedFreqs' with the characters in string 't'.
    for (char c : t.toCharArray()) {
        expectedFreqs[c - 'a']++;
    }
    int left = 0, right = 0;
    while (right < lenS) {
        // Add the character at the right pointer to 'windowFreqs' before sliding the
        // window.
        windowFreqs[s.charAt(right) - 'a']++;
        // 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 == lenT) {
            if (Arrays.equals(windowFreqs, expectedFreqs)) {
                count++;
            }
            // Remove the character at the left pointer from 'windowFreqs' before
            // advancing the left pointer.
            windowFreqs[s.charAt(left) - 'a']--;
            left++;
        }
        right++;
    }
    return count;
}

Complexity Analysis

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

• Populating the expected_freqs array takes $O(m)$ time, where m denotes the length of t. Since $m$ is guaranteed to be less than or equal to $n$ 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)$ time.
• Note that at each iteration, the comparison performed between the two frequency arrays (expected_freqs and window_freqs) takes $O(1)$ time because each array contains only 26 elements.

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

Input: s = 'abcba'
Output: 3

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)$ 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(n^2)$ time.

This means the brute force approach would take $O(n^3)$ 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).

2. 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

function longestSubstringWithUniqueChars(s) {
    let maxLen = 0;
    const hashSet = new Set();
    let left = 0, right = 0;
    while (right < s.length) {
        // If we encounter a duplicate character in the window, shrink the window until
        // it’s no longer a duplicate.
        while (hashSet.has(s[right])) {
            hashSet.delete(s[left]);
            left++;
        }
        // Once there are no more duplicates in the window, update 'maxLen' if the
        // current window is larger.
        maxLen = Math.max(maxLen, right - left + 1);
        hashSet.add(s[right]);
        // Expand the window.
        right++;
    }
    return maxLen;
}

public int longestSubstringWithUniqueChars(String s) {
    int maxLen = 0;
    Set<Character> hashSet = new HashSet<>();
    int left = 0, right = 0;
    while (right < s.length()) {
        // If we encounter a duplicate character in the window, shrink the window until
        // it’s no longer a duplicate.
        while (hashSet.contains(s.charAt(right))) {
            hashSet.remove(s.charAt(left));
            left++;
        }
        // Once there are no more duplicates in the window, update 'maxLen' if the
        // current window is larger.
        maxLen = Math.max(maxLen, right - left + 1);
        hashSet.add(s.charAt(right));
        // Expand the window.
        right++;
    }
    return maxLen;
}

Complexity Analysis

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

Space complexity: The space complexity is $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

function longestSubstringWithUniqueCharsOptimized(s) {
    let maxLen = 0;
    const prevIndexes = new Map();
    let left = 0, right = 0;
    while (right < s.length) {
        // If a previous index of the current character is present in the current
        // window, it's a duplicate character in the window.
        if (prevIndexes.has(s[right]) && prevIndexes.get(s[right]) >= left) {
            // Shrink the window to exclude the previous occurrence of this character.
            left = prevIndexes.get(s[right]) + 1;
        }
        // Update 'maxLen' if the current window is larger.
        maxLen = Math.max(maxLen, right - left + 1);
        prevIndexes.set(s[right], right);
        // Expand the window.
        right++;
    }
    return maxLen;
}

public int longestSubstringWithUniqueCharsOptimized(String s) {
    int maxLen = 0;
    Map<Character, Integer> prevIndexes = new HashMap<>();
    int left = 0, right = 0;
    while (right < s.length()) {
        // If a previous index of the current character is present in the current
        // window, it's a duplicate character in the window.
        if (prevIndexes.containsKey(s.charAt(right)) && prevIndexes.get(s.charAt(right)) >= left) {
            // Shrink the window to exclude the previous occurrence of this character.
            left = prevIndexes.get(s.charAt(right)) + 1;
        }
        // Update 'maxLen' if the current window is larger.
        maxLen = Math.max(maxLen, right - left + 1);
        prevIndexes.put(s.charAt(right), right);
        // Expand the window.
        right++;
    }
    return maxLen;
}

Complexity Analysis

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

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

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:

ExampleCopy

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

function longestUniformSubstringAfterReplacements(s, k) {
    const freqs = new Map();
    let highestFreq = 0, maxLen = 0;
    let left = 0, right = 0;
    while (right < s.length) {
        // Update the frequency of the character at the right pointer and the highest
        // frequency for the current window.
        freqs.set(s[right], (freqs.get(s[right]) || 0) + 1);
        highestFreq = Math.max(highestFreq, freqs.get(s[right]));
        // Calculate replacements needed for the current window.
        const numCharsToReplace = (right - left + 1) - highestFreq;
        // 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 (numCharsToReplace > k) {
            // Remove the character at the left pointer from the hash map before
            // advancing the left pointer.
            freqs.set(s[left], freqs.get(s[left]) - 1);
            left++;
        }
        // Since the length of the current window increases or stays the same, assign
        // the length of the current window to 'maxLen'.
        maxLen = right - left + 1;
        // Expand the window.
        right++;
    }
    return maxLen;
}

public int longestUniformSubstringAfterReplacements(String s, int k) {
    Map<Character, Integer> freqs = new HashMap<>();
    int highestFreq = 0, maxLen = 0;
    int left = 0, right = 0;
    while (right < s.length()) {
        // Update the frequency of the character at the right pointer and the highest
        // frequency for the current window.
        char rightChar = s.charAt(right);
        freqs.put(rightChar, freqs.getOrDefault(rightChar, 0) + 1);
        highestFreq = Math.max(highestFreq, freqs.get(rightChar));
        // Calculate replacements needed for the current window.
        int numCharsToReplace = (right - left + 1) - highestFreq;
        // 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 (numCharsToReplace > k) {
            // Remove the character at the left pointer from the hash map before
            // advancing the left pointer.
            char leftChar = s.charAt(left);
            freqs.put(leftChar, freqs.get(leftChar) - 1);
            left++;
        }
        // Since the length of the current window increases or stays the same, assign
        // the length of the current window to 'maxLen'.
        maxLen = right - left + 1;
        // Expand the window.
        right++;
    }
    return maxLen;
}

Complexity Analysis

Time complexity: The time complexity of longest_uniform_substring_after_replacements is $O(n)$, where $n$ 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)$, where $m$ is the number of unique characters in the string stored in the hash map freqs.

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.¹ 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.²

• 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))$, where $n$ 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.

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

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

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

function findTheInsertionIndex(nums, target) {
    let left = 0, right = nums.length;
    while (left < right) {
        const mid = Math.floor((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;
}

public class Solution {
    public int findTheInsertionIndex(int[] nums, int target) {
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + (right - left) / 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))$ because it performs a binary search over a search space of size $n+1$.

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

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

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

function firstAndLastOccurrencesOfANumber(nums, target) {
    const lowerBound = lowerBoundBinarySearch(nums, target);
    const upperBound = upperBoundBinarySearch(nums, target);
    return [lowerBound, upperBound];
}

function lowerBoundBinarySearch(nums, target) {
    let left = 0, right = nums.length - 1;
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return (nums.length > 0 && nums[left] === target) ? left : -1;
}

function upperBoundBinarySearch(nums, target) {
    let left = 0, right = nums.length - 1;
    while (left < right) {
        // In upper-bound binary search, bias the midpoint to the right.
        const mid = Math.floor((left + right) / 2) + 1;
        if (nums[mid] > target) {
            right = mid - 1;
        } else if (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 (nums.length > 0 && nums[right] === target) ? right : -1;
}

public class Solution {
    public int[] firstAndLastOccurrencesOfANumber(int[] nums, int target) {
        int lowerBound = lowerBoundBinarySearch(nums, target);
        int upperBound = upperBoundBinarySearch(nums, target);
        return new int[]{lowerBound, upperBound};
    }

    private int lowerBoundBinarySearch(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return (nums.length > 0 && nums[left] == target) ? left : -1;
    }

    private int upperBoundBinarySearch(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            // In upper-bound binary search, bias the midpoint to the right.
            int mid = left + (right - left) / 2 + 1;
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (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 (nums.length > 0 && nums[right] == target) ? right : -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))$, where $n$ 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))$ because it calls each helper function once.

Space complexity: The space complexity is $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.

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:

ExampleCopy

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

function cuttingWood(heights, k) {
    let left = 0, right = Math.max(...heights);
    while (left < right) {
        // Bias the midpoint to the right during the upper-bound binary search.
        const mid = Math.floor((left + right) / 2) + 1;
        if (cutsEnoughWood(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.
function cutsEnoughWood(H, k, heights) {
    let woodCollected = 0;
    for (const height of heights) {
        if (height > H) {
            woodCollected += (height - H);
        }
    }
    return woodCollected >= k;
}

public class Solution {
    public int cuttingWood(int[] heights, int k) {
        int maxVal = 0;
        for (int h : heights) {
            maxVal = Math.max(maxVal, h);
        }
        int left = 0, right = maxVal;
        while (left < right) {
            // Bias the midpoint to the right during the upper-bound binary search.
            int mid = left + (right - left) / 2 + 1;
            if (cutsEnoughWood(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.
    private boolean cutsEnoughWood(int H, int k, int[] heights) {
        long woodCollected = 0;
        for (int height : heights) {
            if (height > H) {
                woodCollected += (height - H);
            }
        }
        return woodCollected >= k;
    }
}

Complexity Analysis

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

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

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

function findTheTargetInARotatedSortedArray(nums, target) {
    let left = 0, right = nums.length - 1;
    while (left < right) {
        const mid = Math.floor((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.
        } else if (nums[left] <= nums[mid]) {
            if (nums[left] <= target && 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 && 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 (nums.length > 0 && nums[left] === target) ? left : -1;
}

public class Solution {
    public int findTheTargetInARotatedSortedArray(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 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.
            } else if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && 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 && 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 (nums.length > 0 && nums[left] == target) ? left : -1;
    }
}

Complexity Analysis

Time complexity: The time complexity of find_the_target_in_a_rotated_sorted_array is $O(\log(n))$ because we're performing a binary search over an array of length $n$.

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

Input: nums1 = [0, 2, 5, 6, 8], nums2 = [1, 3, 7]
Output: 4.0

Input: nums1 = [0, 2, 5, 6, 8], nums2 = [1, 3, 7, 9]
Output: 5.0

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))$ time where $m$ and $n$ denote the lengths of each array, respectively. This complexity is primarily due to the cost of sorting the merged array of length $m+n$. This approach can be improved to $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: