LeetCode has been running a writing contest during February and March of this year. Here’s what I submitted:

How to LeetCode: What I Learned from a Year of LeetCoding Challenge Problems.

Problem

LeetCode 322: Coin Change (Medium)

Problem Statement: You are given a set of coin denominations (integers) and an amount of change to make using only these coins. Return an integer representing the smallest number of coins sufficient to make the given amount of change. You may use as many coins of each denomination as you want. If the amount of change is impossible to make using the given coins, return -1.

Solution

This is based on a solution by Stefan Pochmann.

Coin Change is a classic dynamic programming problem. As usual for DP problems, we’ll store earlier results in an array and use them to efficiently calculate later results.

Let amount be the amount of change we need to make. Define an integer array dp[amount+1]. For each amount a, dp[a] is the minimum number of coins sufficient to make a using the coins we have checked so far. We’ll make a pass through dp for each coin denomination, updating it if we get a better result by including that coin.

The base case is dp[0] = 0, since zero coins of any denomination are sufficient to make zero dollars. For every other amount dp[i], we’ll initialize the array with dp[i] = amount+1. This is just an out-of-range value (coin values are integers no smaller than 1, so we’ll never need more than amount of them). When we’re done, the return value will be stored in dp[amount]. If dp[amount] == amount+1, there is no possible answer, so we return -1.

Once the array is initialized, we’ll update it using each coin value. Consider a coin with value c. To make an amount c, we need only one coin with that value, so dp[c] = 1. To make an amount 2c using only that coin, we need two copies of the coin, so dp[2c] = 2, and so on. Continue until the end of the array. At this point, dp stores the minimum number of c coins necessary to make each amount from 0 to amount, if it’s possible to make that amount using only c. Amounts that aren’t possible still have the initialized value, amount+1.

Now consider a second coin with value d, where c != d. To make the amount c+d using these two coins, the best we can do is use one c coin and one d coin, so dp[c+d] = 2. But making the amount c+2d doesn’t necessarily require three coins. For example, if c = 2 and d = 1, then we can make the amount 4 using just two c coins, which is a better result. To ensure that each dp[i] always contains the best result we have found so far, we need to store the smaller of these two coin counts at each step:

• Count 1: the value already in dp[i], which is the minimum coin count calculated so far for amount i.
• Count 2: dp[i-c] + 1. The current minimum count for amount i-c, plus one more coin of value c, gives us an amount i and a new count for dp[i].

Since we store the minimum value at each step and we only check one coin at at time, it doesn’t matter what order we check the coins in. We’ll get the same result when we’re done with the whole coin list regardless of whether we process the coins in sorted order, reverse sorted order, or any other order.

Pseudocode

Inputs:

• coins: an array of integers.

• amount: the target amount

  define an integer array dp of size amount+1
  initialize each element of dp to amount+1
  initialize dp[0] to 0
  
  for each coin c
      for each i from c to amount
          set dp[i] to the minimum of dp[i] and dp[i-c] + 1
  
  if dp[amount] is amount+1, return -1
  else return dp[amount]
  

Code

Coin Change on GitHub

LeetCode Model Solutions

I’m posting some LeetCode model solutions this year. For more about this, see A Project for 2021.

Problem

LeetCode 152: Maximum Product Subarray (Medium)

Problem Statement: Given an array of integers, return the largest possible product of a contiguous subarray.

Some notes:

• A contiguous subarray is a range of values [i..j], where i and j are positions in the input array. For this problem, the subarray must contain at least one value (which would mean i==j). You’re not allowed to pick the subarray [] and calculate the product as 0. The one exception is when the input array is empty, in which case the correct answer is 0.
• The input values are 32-bit integers (positive, negative, or zero), but they’re guaranteed to be small enough that the solution will fit in a 32-bit integer.

Solution

This is based on a solution by lee215.

The problem requires us to multiply elements of an array, so there are a few rules of multiplication to think about:

• If there’s a 0 value anywhere in the subarray, the entire product is zero. So we generally want to avoid including zeros, unless the only other alternative is a negative product.
• We’ll rarely be forced to settle for a negative product. If there’s only one negative element in the array, we can always exclude it unless the array only has one element. If there are two or more, we can include an even number of negative elements.

There are $O(n^2)$ contiguous subarrays in an array of length $n$. We could find the one with the largest product by checking every range [i..j] in the array, where $i \leq j$. But the rules above suggest a more efficient process:

• If we’re checking all ranges that start at i and we arrive at a range [i..j] whose product is zero, there’s no reason to check any further ending j values, since the product will stay at zero forever.
• If we keep track of the maximum product found so far, there are no special cases for negative elements. If the product of a range [i..j] becomes negative, then either it will become positive again when we encounter the next negative element, or if there are no negative elements remaining, we’ll just use the maximum product before we encountered the negative element.

So the key idea is: Rather than checking every starting position i and every ending position j, we can just start i at position 0 and maintain the maximum product, only moving i when the product becomes zero. That means we only need a single pass through the array. At each new j position, the product will either increase (when a[j] is positive), reset to zero (when a[j] is zero), or become negative (when a[j] is negative). In the first case, we’ll just increase the stored maximum. In the second case, we need to restart the product after the zero element. In the third case, we can just continue multiplying in case there’s another negative value coming up.

But this approach doesn’t quite work. What if our input array is [1,-2,3]? The products will be $1$, $1 \times -2 = -2$, and $-2 \times 3 = -6$. So the algorithm would return $1$ as the maximum, when it should return $3$ (for the range [2,2]).

A simple way to fix this problem is to maintain a left product that starts at position 0 and checks to the right, and a right product that starts at position len-1 and checks to the left. The answer will the maximum value found for either of these products.

Pseudocode

Variables:

• a: the input array
• len: the length of a
• max: the maximum product
• left: the product starting at the beginning of the array and moving right

• right: the product starting at the end of the array and moving left

  for i from 0 to len-1
      if left is 0, set it to a[i]
      else set it to left*a[i]
  
      if right is 0, set it to a[len-1-i]
      else set it to right*a[len-1-i]
  
      if left or right exceeds max, update max
  
  return max
  

Code

Maximum Product Subarray on GitHub

LeetCode Model Solutions

I’m posting some LeetCode model solutions this year. For more about this, see A Project for 2021.

Problem

LeetCode 856: Score of Parentheses (Medium)

Problem Statement: You are given a string containing only the characters ( and ). The parentheses are guaranteed to be balanced (as in syntactically valid source code). Calculate a score using the following rules:

• () has a score of 1.
• AB has a score of A + B, where A and B are balanced strings of parentheses.
• (A) has a score of 2 * A, where A is a balanced string of parentheses.

Solution

In the problem LeetCode 20: Valid Parentheses, we have to check if a string of parentheses is balanced. In this problem, the input is guaranteed to be balanced, so we don’t need to verify that condition. But some of the techniques used to verify balance are also useful in this problem.

Given the recursive definition in the problem statement, it seems like the problem might lend itself to a recursive solution. The free official solution uses a recursive function in Approach 1, which requires $O(n^2)$ time and $O(n)$ space. Balanced parentheses problems can also generally be solved using a stack, which is how it’s done in Approach 2. That solution reduces the time requirement to $O(n)$. I’m going to explain Approach 3, which uses no stack or other data structures, and requires only $O(1)$ space.

Solution idea

Define a core as the substring (). A core has a score of 1. When a core is surrounded by parentheses, each set of surrounding parentheses multiplies what’s inside by 2. So () is 1, (()) is 2, ((())) is 4, and so on. If two or more substrings are arranged side by side, their scores are added together. So ()() is $1+1=2$, ()()() is $1+1+1=3$, and (())(())(()) is $2+2+2=6$. Because of these rules, the total score can always be expressed as the sum of powers of two.

Next, define the balance of a substring as the number of opening parentheses in the substring minus the number of closing parentheses. The balance of the full input string is always 0. But if we iterate through the input string character by character, we can increment the balance at each ( and decrement it at each ), and the balance at each step will be a non-negative integer that we can use to calculate a running score.

Here’s the key idea: Whenever we see () (a core), we increase the current score by $2^b$, where $b$ is the current balance. This works because $b$ is the number of parentheses the core is contained in, and each of those parentheses multiplies the core value by $2$. So for (()), we’ll have $b=1$ when we encounter the core, so we’ll correctly evaluate the score as $2^1=2$. For (())(())(()), we’ll have $b=1$ at each core, so we’ll add $2$ to the score three times.

A quick note on code syntax: 1 << b means start with 1 and shift it left b times. So it’s the same as $2^b$ or Math.Pow(2, b).

Pseudocode

Variables (both ints, initialized to zero):

• score: the problem result

• balance: the current balance of parentheses

  for each char c in input string
      if c is a left paren, increment balance
      else
          decrement balance
          if the previous char was a left paren
              increment score by 2^balance
  return score
  

As described in the solution idea, we iterate through the input one character at a time, incrementing the current balance when we see ( and decrementing it when we see ). Also, when we see (), we increase the result by 2 raised to the power of the current balance.

Code

Score of Parentheses on GitHub

LeetCode Model Solutions

I’m posting some LeetCode model solutions this year. For more about this, see A Project for 2021.

Problem

LeetCode 11: Container With Most Water (Medium)

Problem Statement: In the coordinate plane, consider $n$ vertical lines starting at points $(1, 0), (2, 0), …, (n, 0)$ and ending at points $(1, h_1), (2, h_2), …, (n, h_n)$, where each $h_i$ is a non-negative integer. We can construct a rectangle whose sides are the $x$-axis, two of these vertical lines, and a horizontal line connecting $(i, h_i)$ and $(j, h_i)$ for some $i$ and $j$ where $h_i < h_j$. Return the maximum possible area of such a rectangle.

The statement above is an alternate way of expressing the original problem, which is described in terms of a container filling with water. For a visual representation, see the problem page on LeetCode.

Solution

This problem can be solved using a simple $O(n)$ algorithm, as explained by several people in the discussions, including Stefan Pochmann. But finding that algorithm and understanding why it’s correct isn’t as simple. Let’s take it step by step.

We’re trying to maximize the area of a rectangle, $A = height \times width$. To get the maximum width, we would need to use the first and last vertical lines, at $x$ coordinates $1$ and $n$. This gives us a width of $w = n-1$ and a height of $h = min(h_1, h_n)$. If $h$ happens to be the maximum height, then we’re done. But there’s no way to know that without checking smaller widths.

The only way to get a larger rectangular area with a smaller width is to increase the height. Consider two line heights, $h_i$ and $h_j$, where $h_i < h_j$. The area of the rectangle that uses these two lines is $A = h_i \times |j-i|$, since we’re required to use the smaller of the two heights.

To use a longer line, we have to discard either $h_i$ or $h_j$. Which one should we discard? As long as we include $h_i$ in our rectangle, we can’t get an area any larger than $A$, since the rectangle height will be at most $h_i$, regardless of which line we pair it with. Therefore, the only way to find a larger area is to discard $h_i$ and keep $h_j$. (In the case where $h_i = h_j$, we can discard either one).

This is the key idea for the algorithm: At each step, discard the smaller line and keep the larger one. If we start with a left pointer $i=1$ and a right pointer $j=n$, then at each step we either increment $i$ or decrement $j$, depending on which line is smaller. When the pointers meet, we have checked all $n$ lines, and no line has been checked more than once, so we have an $O(n)$ algorithm.

Pseudocode

For the pseudocode, we’ll switch to 0-based indexing, since that’s how the input data is stored.

Variables:

• height[]: Input data, consisting of $n$ integer heights
• i: Left pointer, starting at $0$
• j: Right pointer, starting at $n-1$
• minh: The smaller of the two heights
• area: The current area

• max: The maximum area found so far

  while i < j
      minh = minimum of height[i] and height[j]
      area = minh * j-i
      if area > max, update max
  
      if height[i] < height[j] then i++
      else j--
  
  return max
  

The algorithm: As long as the pointers haven’t crossed, we calculate the current area and see if we have a new maximum. Then we either increment the left pointer or decrement the right pointer, depending on the relative heights. Once we make it through the input, we return the maximum area found.

Code

Container With Most Water on GitHub

LeetCode Model Solutions

I’m posting some LeetCode model solutions this year. For more about this, see A Project for 2021.

Problem

LeetCode 47: Permutations II (Medium)

Problem Statement: Given a list of integers that may contain duplicates, return all possible unique permutations of those integers, in any order.

A permutation is an arrangement of elements. For example, the three elements [1,2,3] can be arranged into $3!=6$ unique permutations: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1]. For this problem, the input list can have duplicate elements (that’s the extra requirement compared to the previous problem, LeetCode 46: Permutations), but the answer must not have any duplicate permutations.

Solution

The canonical algorithm for finding permutations is recursive backtracking, so we’ll take that approach.

Pseudocode

The solution uses two functions: the main function, which sets up the recursion and returns the result, and the recursive backtracking function.

The main function accepts a list of integers. The first step is to sort this input array. This is a simple way to avoid duplicate permutations. Then we call the recursive function and return the result. The 0 argument in the backtrack call means start the process at position 0 in nums (the input list).

sort the input list (nums)
backtrack(nums, 0)
return result

In the backtrack function, we’ll need four variables, the first three of which are passed as parameters:

• result: The list of permutations
• nums: One unique permutation of the input list
• i: The starting position in the current permutation
• j: The current position in the current permutation

For the recursive base case, we check if our starting position is past the end of the current permutation. If it is, the current permutation is done, so we can add it to our list of results, and return:

if i is past the end of the current permutation
    add the current permutation to the result
    return

Now the real work begins. We’ll use a combination of iteration and recursion. The iteration loop on j goes from i (the starting position) to the end of the current permutation, nums. For each j (the current position), we’ll check the values at nums[i] and nums[j]. If they’re different, we swap them and recursively start the process again at the next starting position i+1. As a special case, we also make the recursive call when i==j. To keep the code simple, we also do the swap in this case, though it has no effect since we’re swapping an element with itself.

for each j from i to end of nums
    if nums[i] and nums[j] are different or i==j
        swap nums[i] and nums[j]
        backtrack(copy of nums, i+1)

One implementation detail: When we make the recursive call, we need to send a copy of nums, not just a reference to nums. This is how we generate new permutations. If we sent a reference, we would overwrite the result of previous swaps.

Why does this process work? Since permutations are arrangements of the input values, it makes sense that we could generate these arrangements by swapping. The key is to make sure we use all possible swap positions (except where the swap would have no effect because the source and destination elements are the same). Notice that i covers every position in nums from 0 to the last element. And j covers every position from i to the last element. So (ignoring duplicates), we swap position 0 with positions 0, 1, …, n-1, position 1 with 1, 2, …, n-1, and so on until i==n. So it seems reasonable that this would cover every possible swap.

As with last week’s recursive problem, instrumentation can help illuminate the flow of control in a recursive algorithm. Here’s what happens when the input is 1,1,2. Note that some swaps are skipped in this example, since the input contains a duplicate 1 element:

i=0, j=0
1 1 2 
i=1, j=1
1 1 2 
i=2, j=2
1 1 2 
i=3, adding to result:
--> 1 1 2 
Returned from backtrack at i=2, j=2
Returned from backtrack at i=1, j=1
i=1, j=2
1 2 1 
i=2, j=2
1 2 1 
i=3, adding to result:
--> 1 2 1 
Returned from backtrack at i=2, j=2
Returned from backtrack at i=1, j=2
Returned from backtrack at i=0, j=0
i=0, j=2
2 1 1 
i=1, j=1
2 1 1 
i=2, j=2
2 1 1 
i=3, adding to result:
--> 2 1 1 
Returned from backtrack at i=2, j=2
Returned from backtrack at i=1, j=1
Returned from backtrack at i=0, j=2

Code

Permutations II on GitHub

LeetCode Model Solutions

I’m posting some LeetCode model solutions this year. For more about this, see A Project for 2021.

Problem

LeetCode 897: Increasing Order Search Tree (Easy)

Problem Statement: Given a binary search tree (BST), rearrange it (preserving the BST order) so that the lowest node is at the root and each node only has a right child. The result is like a sorted linked list.

The problem doesn’t mention any space requirements, and the tree has at most 100 nodes, so it’s easy to traverse the BST in order, save the values in a list, and build a new BST that meets the requirements. This is Approach 1 in the official solution. For a more challenging solution, we can save space by rearranging the tree in place, as in the official Approach 2. That’s the solution I’ll use.

Solution

The solution described here is based on this solution by lee215. It’s similar to the official Approach 2 solution, but the code is more concise without sacrificing readability.

In-order traversal

Since the goal is to rearrange the BST into a sorted list, the appropriate technique is in-order traversal. Here are the canonical steps for in-order binary tree traversal:

• Recursively traverse the left subtree
• Take an action on the current node
• Recursively traverse the right subtree

Based on the problem statement, we know that we’ll have to remove the left node in the middle step. But before we remove it, we have to save it somewhere, or we’ll lose all the nodes in the left subtree.

Tree traversal is commonly implemented using a recursive function. For example, we could implement a function to print a BST in sorted order using this in-order traversal algorithm:

if node is null, return
traverse(node.left)
print node value
traverse(node.right)

This function works by following left child links to the smallest node. Then it prints that node’s value. Then it follows that node’s right subtree using the same process. When it gets back to the root, it traverses the root’s right subtree using the same process. The call stack keeps track of where we are in the tree.

For the Increasing Order Search Tree problem, we can use the same pattern, but we’ll need some extra steps.

Pseudocode

The default code for this problem defines a function IncreasingBST that accepts a tree node (the root node) and returns a tree node (the root of the rearranged tree). Let’s create a recursive function with the same name and a second tree node parameter next that refers to the node to process after we’re done processing node. So the recursive function is:

TreeNode IncreasingBST(TreeNode node, TreeNode next)

To kick off the recursion, we’ll use return IncreasingBST(root, null): we’re at the root, and there’s no next node to process (once we process the root’s two subtrees, we’re done).

Here is a line-by-line explanation of the (pseudocode) function.

if node is null, return next

If the node parameter is null, it means we have followed a left or right child that is null. There’s nothing we can do with a null node, so we return the next node, which is the next node to process. In the case where the root is null, we’ll correctly return null, since next is null on the first call.

result = IncreasingBST(node.left, node)

Since we’re doing in-order traversal, we need to process the left subtree first, so we pass node.left as the first parameter. For the next parameter, we pass the current node, since a node in a BST follows its left child (if it has one) in ascending order. We’ll also save the result of this call to use later.

node.left = null

Now that we have followed the left child and saved the result, we can remove the left child, as required by the problem statement and the BST order.

node.right = IncreasingBST(node.right, next)

In in-order traversal, the right subtree is processed after the left subtree. Once we do this, we’re done with the parent node’s two subtrees, so the next parameter is the next value that was passed in.

return result

At the end of the function, we return the result that we saved in the first step. This is the result of the left subtree traversal, since the left subtree occurs first in BST order.

Example

It can take some work to follow the steps in a recursive algorithm. One technique that can help is to instrument the algorithm by writing to stdout at each step. This lets you see the program flow during the recursive calls.

Consider a BST that looks like this (root node 3 and only left children):

         3
        /
       2
      /
     1

We want to transform it into this (root node 1 and only right children):

     1
      \
       2
        \
         3

Here’s the output of the algorithm above running with instrumentation:

At root 3  
Recursive call with node=3, node.left=2  
Recursive call with node=2, node.left=1  
Recursive call with node=1, node.left=null  
Node is null; returning next=1  
Saving result 1  
Recursive call with node=1, node.right=null, next=2  
Node is null; returning next=2  
New node.right=2  
Returning result 1  
Saving result 1  
Recursive call with node=2, node.right=null, next=3  
Node is null; returning next=3  
New node.right=3  
Returning result 1  
Saving result 1  
Recursive call with node=3, node.right=null, next=null  
Node is null; returning next=null  
New node.right=null  
Returning result 1

Code

Increasing Order Search Tree on GitHub

LeetCode Model Solutions

I’m posting some LeetCode model solutions this year. For more about this, see A Project for 2021.

Problem

LeetCode 394: Decode String (Medium)

Problem Statement: Decode a string that has been encoded in a specified format.

In the encoded string, k[str] means decode the string str and repeat the result k times. The input encoding is always valid: k is always a positive integer, there is no extra whitespace, the square brackets match, etc. str may contain more letters, integers and brackets, following the same format rules. However, the decoded string will consist only of lowercase letters (no digits, brackets, or other characters).

Solution

The solution described here is based on this solution by bluedawnstar.

We will implement a recursive function, DecodeString. The solution strategy is to process the input string character by character in one pass, taking different actions based on whether the current character is a digit, a letter, or a closing bracket. Here are the three cases:

Digit

If the character is a digit, we know that this part of the string is an integer followed by an opening bracket, a substring, and a closing bracket. We can process this section using three steps:

• Read all the digits before the opening bracket and interpret them as an integer n. This is the number of times to repeat the string inside the brackets.

• Recursively call DecodeString on the string inside the brackets. That string may contain more digits, letters, and brackets, so there may be further recursive calls.

• Append n copies of the result to the output string.

Letter

Append the letter to the output string.

Closing bracket

A closing bracket means a substring is complete, so return the result.

Pseudocode

for each character c in the input string
    if c is a digit
        convert consecutive digits to an integer n
        recursively call DecodeString
        append n copies of the result to the output string
    else if c is a letter, append it to the output string
    else if c is ']', return the current output string

One implementation detail: It simplifies the recursive function if we store the current input string position as a class-level variable. Since we’re always moving forward in the input string, this means a recursive call can just continue from the current position and doesn’t have to return how many input characters it processed. We can just initialize the position to 0 when the program starts, and increment it whenever we process a character. It doesn’t matter whether we’re in the first call to DecodeString or ten recursive calls deep.

Code

Decode String on GitHub

LeetCode Model Solutions

I’m posting some LeetCode model solutions this year. For more about this, see A Project for 2021.

Problem

LeetCode 1022: Sum of Root To Leaf Binary Numbers (Easy)

Problem statement: Given a binary tree where each node contains a binary digit, interpret each path from the root to a leaf as a binary number, with the root value as the high-order bit. Return the sum of these numbers.

Solution

This problem is rated Easy, but it’s a good way to practice two useful techniques:

• Converting a sequence of binary digits to an integer value.
• Traversing the nodes of a binary tree in the correct sequence.

The solution described here is based on this solution by lee215, who also made an appearance last week.

Binary to decimal conversion

Consider the sequence of base-10 digits $3, 2, 1$. If we received them in that order, how would we construct the base-10 value $321$? We could use following algorithm:

result = 0
for each digit d
    result *= 10
    result += d

For the digit sequence above, result would take the following values: 0, 3, 30, 32, 320, and 321. For each iteration, multiplying by 10 shifts the result left, leaving a 0 value in the units place. The addition operation replaces the 0 value with the next digit in the sequence.

This algorithm works for any base. For binary, we just multiply by 2 instead of 10. So for the sequence $1, 0, 1, 0$, the result would take the values 0 (multiply), 1 (add), 2 (multiply), 2 (add), 4 (multiply), 5 (add), 10 (multiply), and 10 (add). For each iteration, we multiply by 2 (shift left) and then add either 0 or 1.

Tree traversal

Binary tree traversal comes up a lot in LeetCode problems, and an easy problem like this one is a good way to learn some fundamentals. It’s standard to use a recursive algorithm when traversing a tree, and that’s what I’ll do here. Consider a function that accepts a tree node and an the current sum, and returns a new sum. We can kick off the recursion with the root node and a sum of 0, then use the following logic for each recursive call:

if the node is null, return 0
append the current binary digit to the sum using the conversion algorithm
if the node is a leaf node, return the current sum
otherwise, return:
    the value of the left subtree plus the value of the right subtree

Here’s how each line works:

if the node is null, return 0

This is the base condition. To avoid infinite recursion, we need a condition where no more recursive calls are made. If we keep following left or right pointers, we’ll eventually reach a null pointer. In this case, we don’t want to affect the sum (since we’re not on a node), so we return zero before any recursive calls happen.

append the current binary digit to the sum using the conversion algorithm

The recursive function could return an array of binary digits and the main function could convert them to decimal. But it’s cleaner to do the conversion on the fly. The binary to decimal conversion section above explains how to do that as we encounter each digit.

if the node is a leaf node, return the current sum

A leaf node is a node where both the left and right children are null. According to the problem statement, this defines the end of a binary number, so there’s nothing more to add to the sum. We can just return it.

otherwise, return:
    the value of the left subtree plus the value of the right subtree

This is the “magic” step in the recursive function. Consider the situation at the root. We have already appended the root’s digit to the current sum. Now we need to incorporate the rest of the tree. But we’re at the root, so the rest of the tree is just the left and right subtrees. And each of these subtrees can have their own subtrees, and so on. The recursive design takes care of processing the left and right subtrees with minimal code. We just pass the left node and the current sum to the recursive function (call 1), pass the right node and the current sum to the recursive function (call 2), add the results together, and return the total.

Code

Sum of Root To Leaf Binary Numbers on GitHub

LeetCode Model Solutions

I’m posting some LeetCode model solutions this year. For more about this, see A Project for 2021.

Problem

LeetCode 1288: Remove Covered Intervals (Medium)

Problem statement: Given a list of intervals, return the number of intervals that are not covered by another interval in the list.

For this problem, think of an interval as a segment of the number line with integer starting and ending points. For example, the interval $(-1, 1)$ is a segment of length $2$ centered at $0$.

Interval $(c,d)$ covers interval $(a,b)$ iff $c \leq a$ and $b \leq d$. Intuitively, this means that no point on $(a,b)$ is outside of the range covered by $(c,d)$.

Note that if one interval’s end point is the same as another interval’s start point, neither interval covers the other. For example, intervals $(0,2)$ and $(2,4)$ would contribute two intervals to the count. But $(0,2)$ and $(1,2)$ would only contribute one interval to the count, since the first interval covers the second. In a third case, $(0,2)$ and $(1,3)$ would count as two intervals. Although the intervals overlap, neither interval completely covers the other.

Solution

The solution described here is based on this solution by lee215, a well-known contributor to the LeetCode discussion forums.

Algorithm

• Sort the intervals by start position. This allows us to make one pass through the list without backtracking or using any data structure besides an array.
• Maintain a comparison interval $(c,d)$ that stores the most recent interval that is not covered by another interval. Note that $(c,d)$ is not necessarily an interval in the input list.
• For each interval $(a,b)$ in the input list:
  • If $a > c$ and $b > d$, then some of $(a,b)$ is to the right of comparison interval $(c,d)$, and some of comparison interval $(c,d)$ is to the left of $(a,b)$. This means neither interval completely covers the other. Therefore, we can increment the interval count by one. We also need to let $c=a$ to advance the comparison interval start point.
  • Let $d=\max(d,b)$ to advance the comparison interval end point.
• Return the interval count.

Notes

One way to see why this algorithm works is to consider all the ways that interval $(a,b)$ and comparison interval $(c,d)$ can be positioned relative to each other. For the starting endpoints of each interval, the possibilities are $a<c$, $a=c$, and $a>c$. Similarly, for the ending endpoints, we have $b<d$, $b=d$, and $b>d$. Since there are three possibilities for each of the two endpoints, there are a total of $3 \times 3 = 9$ combinations.

But because we start the algorithm by sorting the intervals by start point, we can eliminate $a<c$, since each interval must start at least even with the previous interval (i.e., the start points are nondecreasing). This means there are only $2 \times 3 = 6$ cases that can occur. Here are those cases:

(1) $a>c$ and $b>d$

    c ---------- d
    a   ---------- b

This is the configuration detected by the if statement in the algorithm. Neither interval covers the other, so we increment count and $(a,b)$ becomes the new comparison interval.

(2) $a>c$ and $b=d$

    c ---------- d
    a   -------- b

$(a,b)$ is completely covered by $(c,d)$, so we skip it without incrementing count.

(3) $a>c$ and $b<d$

    c ---------- d
    a   ------   b

This is a similar configuration to (2). $(a,b)$ is completely covered.

(4) $a=c$ and $b>d$

    c ---------- d
    a ------------ b

As with the other cases, we don’t go into the if block so we don’t increment count for this case. But this time it’s because the new interval $(a,b)$ covers the comparison interval $(c,d)$ (the reverse of cases (2) and (3)). This is why it’s important to set $d=\max(d,b)$ outside the if block. Even when there’s not a new interval to count, we need the right endpoint of the comparison interval to be as far right as possible.

(5) $a=c$ and $b=d$

    c ------------ d
    a ------------ b

The new interval is identical to the comparison interval, so we don’t count it.

(6) $a=c$ and $b<d$

    c ------------ d
    a ----------   b

This is similar to (3) and (4). $(a,b)$ is completely covered, so we don’t count it.

After considering all six cases, we can see that we only need to count a new interval in one case, the first one. In the other cases, all we need to do is possibly adjust the right endpoint of the comparison interval.

Code

Remove Covered Intervals on GitHub

LeetCode Model Solutions

I’m posting some LeetCode model solutions this year. For more about this, see A Project for 2021.