While working on my LeetCode project last year, I started a list of general practice notes. Not notes on specific problems, though those are essential, but notes on the LeetCode practice process in general. My plan for this year is to turn those into a short LeetCode practice tip each week.

« Continue »

Programming puzzles like those on LeetCode may have clear specifications and short solutions compared to real-world computer programs, but that doesn’t make them easy. Something about the math and algorithms required to solve them makes them challenging for the average programmer (and many above-average programmers!) This year, once again, I allocated some time each day to work on the LeetCode Daily Problem, both to keep my problem-solving muscles in shape and to find effective problem-solving techniques.

As I wrote in last year’s end-of-year review and in my How to LeetCode post in the LeetCode discussions this year, the foundation for learning LeetCode-style problems is spaced repetition. While solving the daily problem and reading the discussions helps expose you to new problems and solutions, it’s far from enough. Solving a problem the first time provides an introduction to that problem and its associated concepts. But you have to solve a problem repeatedly to really understand it.

One benefit of spaced repetition is the repetition part. But it’s not just a matter of solving the same problem five times in a row. While that type of repetition might help you remember it the next day, it won’t do much for remembering it a week or a month later. That’s where the spaced part comes in. Gradually increasing the time between repetitions helps transfer the solution into long-term memory, where it’s more useful when you need to retrieve it during an interview.

To wrap up this year, I’d like to explore a specific goal of spaced repetition: learning a solution at multiple levels of abstraction.

Model Solutions

In my How to LeetCode post, I explained why it’s useful to write a detailed model solution before investing in spaced repetition practice for a problem. I said this was a way to “polish the solution before you learn it.” In the comments, a reader thought this was backwards. His objection: “I would have thought you’d have to learn it first, and then polish it.”

I think both options can be correct. It’s important to create the best solution you can before you start practicing it. If you’re going to invest time in learning a solution, you want it to be as good as you can make it. But it’s also true that practicing a solution can illuminate parts of it that you didn’t notice when you first studied it. So it’s a virtuous cycle: as you practice a solution, you learn more about it, which helps you understand it better, which makes it easier to remember, which makes future practice more effective, which allows you to see new aspects of the problem that you can incorporate into your practice.

Levels of Abstraction

A model solution works best when it expresses the solution to a problem at different levels of abstraction, from most general to most specific: Begin with a summary of the problem and the overall solution approach. Then explain the algorithm step by step in natural language, without any code or pseudocode. (Though variable names may be useful at this point to make the explanation clearer). Next, write the algorithm in pseudocode, avoiding any language-specific details. Finally, write a real implementation that compiles, runs, and passes all the test cases.

This multi-layered approach helps you understand the solution better, and therefore remember it better. Each level of abstraction explains the problem from a different point of view. At the top level, learning the problem and solution summary for multiple problems helps you recognize problem types and remember which algorithms or techniques are required to solve them. At the next level is the natural language description, which is the core of the solution. It’s how you’ll describe the solution to an interviewer so they can approve what you’re about to implement. After that, you have the pseudocode solution, which a detailed description of the algorithm itself. Then, since the purpose of a coding interview is to prove that you can actually write code, you have to take the process a step farther and actually implement the pseudocode in a real programming language. (It’s worth noting that at least one well-known algorithm textbook doesn’t bother with this step, and just sticks with pseudocode).

Forgetting the Answer

The spaced repetition process can help you discover how well you know a solution, as measured by how much time elapses before you forget it. For example, if you practice a solution one day, and you can still successfully reproduce it the next day, that gives you some information about how well you know it. The next step is to increase the length of time between repetitions. So you might practice it again in 3 days and successfully reproduce it again, but then find that you’re unable to reproduce it 7 days after that. So the appropriate repetition time based on your current level of understanding is greater than 3 days but less than 7 days. According to learning theory, you’ll get the best results by practicing again during that interval.

In addition to narrowing down the appropriate practice interval, spaced repetition can also narrow down what part of the solution needs the most practice. To do this, ask yourself after an unsuccessful solution attempt what part of the solution you forgot. If you tried to solve the problem with the wrong algorithm, then you need to start from the beginning and learn the high-level summary. If you knew the general approach but couldn’t make much progress on the details, you can study the natural language solution. If you have a fairly good understanding of the solution details, but you missed a few steps, studying the pseudocode can help. And if you can write a pseudocode solution but have trouble translating it into a programming language, it might be best to review language syntax and common idioms used in LeetCode-type solutions.

Improving Your Model Solution

Spaced repetition practice can give you very specific feedback about your model solution. I was recently practicing LeetCode 227: Basic Calculator II, which I wrote about at the beginning of this year. At the time I wrote the article, I had practiced the solution at a few different time intervals, and it seemed fairly clear to me. But coming back to it late in the year, I noticed that I didn’t know exactly how the prev and result variables were related. If I was updating the model solution now, I might explain it like this: We need two variables because the problem defines two priorities for operator precedence: multiplication/division (higher priority) and addition/subtraction (lower priority). Since addition/subtraction is the lowest priority, we can update result immediately after any addition/subtraction operation. To account for the higher priority of multiplication/division, we need a separate variable prev that only gets updated after those operations.

No doubt that explanation can still be improved. But you don’t have to guess about when your solution needs to be updated. By keeping track of which parts of the problem you find difficult during spaced repetition practice, you can improve your model solution and remember it better the next time around. As long as you continue practicing a problem, you can keep polishing the model solution, making gradual adjustments to improve its effectiveness as a study tool. The only time a model solution should stop changing is when you know a solution well enough that you can reproduce it on demand whenever you need to.

A detailed solution for LeetCode 1818: Minimum Absolute Sum Difference.

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

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.