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.

Problem

LeetCode 227: Basic Calculator II (Medium)

Problem statement: Evaluate a valid arithmetic expression containing only numbers, spaces, and the operators +, -, *, and /.

This is almost as simple as an arithmetic expression evaluator can be. It’s simpler than the first Basic Calculator problem, which includes parentheses. The only trick in this version is respecting the order of operations, which in this case is just MDAS since there are no parentheses or exponents.

This solution variation doesn’t use a stack, so it relies on processing the input string character by character (one pass) and setting each variable at the correct point in the process.

Solution

This solution is based on the official LeetCode solution (available without a subscription), Approach 2: Optimized approach without the stack.

Variables

• s: The input string
• i: The position in the input string. We need to know the position because there’s a special case for the last character.
• c: The current character in the input string. Each character is either a digit or an operator.
• result: The final result. This variable also stores the intermediate result after an addition or subtraction operation, but is unchanged after a multiplication or division operation.
• num: An integer operand from the input string.
• prev: After a multiplication or division operation, this stores the intermediate (previous) result. After an addition or subtraction operation, it is initialized to the current num (or -num) value, so it can be used in an upcoming multiplication or division.
• op: The most recent operator, set at the end of the previous iteration. It is initialized to +, since the first operand is always positive.

Algorithm

• Remove all spaces from the input string s, so the only remaining characters are digits and operators.
• Process each character c of s.
• If c is a digit, append it to the current integer operand, num.
• If c is not a digit or c is the last character in s, do the steps below. The “last character” special case is required because the input string doesn’t contain an “evaluate expression” operator like =.

Evaluation steps:

• op always contains the current operator: + when the program starts, or the most recent operator seen in the input.
• If op is + or -, add prev to result. This is equivalent to popping any pending multiplication or division operation in the stack version of this algorithm. Then set prev to num if op is + or -num if op is -. This sets the intermediate result that any future operations will operate on.
• If op is *, multiply prev (the intermediate result) by num (the next operand).
• If op is /, divide prev (the intermediate result) by num (the next operand).
• Set op (the next operation) to c.
• Set num to 0 so we start with a fresh number when we encounter the next digit.

Pseudocode

remove all spaces from s
for each char c in input string
    if c is a digit, append it to num
    if c is not a digit or c is the last character in s
        if op is + or -
            add prev to result
            if op is +, set prev to num
            else set prev to -num
        if op is *, multiply prev by num
        if op is /, divide prev by num
        op = c
        num = 0
add prev to result
return result

Code

Basic Calculator II on GitHub.

LeetCode Model Solutions

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

In late March of this year, the coding interview preparation site LeetCode announced a 30-Day LeetCoding Challenge. Each day during the month of April, they selected one of the coding problems from their archive and challenged developers to solve it within 24 hours. Newly locked-down developers throughout the world took up the challenge, earning LeetCoins and the chance to win LeetCode swag. (Not to mention practicing their coding interview skills).

As one of those suddenly home office-based developers, I thought this sounded like a good daily habit, so I set a reminder to check the site every day for the new problem. By the end of the month, the challenge was popular enough that LeetCode decided to continue it in May, then in June, and so on. Now here we are in December, and it’s still going strong.

As I worked on these daily problems, I took a lot of notes about specific algorithms and techniques, and also about the general process of learning LeetCode problems. I won’t be able to fit everything into this one article, but I’ll summarize some key lessons from my experience this year.

Some Preliminary Claims

Having read a lot of Quora discussions about coding interviews, LeetCode, competitive programming, and similar topics, I know these can be contentious subjects among developers. So let’s get a couple of things out of the way before moving on to the good stuff:

• Claim #1: When interviewing for a job, software developers are often required to solve coding problems similar to those found on LeetCode. The interview consists of more than just those kinds of problems, but coding problems can take up a significant fraction of the interview.

• Claim #2: Developers at all experience levels often find that their previous experience and education have left them underprepared for LeetCode-style interview questions. Consequently, a site like LeetCode is important for targeted preparation.

The Goal

Assuming you accept those claims, here’s what I would propose as the ultimate goal of LeetCoding:

The goal of practicing LeetCode problems is to reach a level of proficiency where you can solve a LeetCode-style problem that you haven’t seen before in 20-40 minutes under interview conditions.

Let’s break this down:

• LeetCode-style problem: LeetCoding is good for practicing algorithmic programming problems. Other types of interview questions — questions about past projects, Amazon Leadership Principals questions, system design questions — require different types of practice.

• That you haven’t seen before: The goal is not to memorize answers with the goal of regurgitating them during an interview. There are too many possible questions, and memorization isn’t a good approach for coding problems. So this study process only succeeds if it helps with new problems. Fortunately, there are a limited number of patterns used by coding interview problems, so even “new” problems will seem familiar after a while because they will remind you of problems you have solved.

• 20-40 minutes: Coding interviews usually come in two sizes: 1) Short interviews, often used for preliminary screening. Those are on the order of 30 minutes and usually take place online or by phone. 2) Long interviews that last closer to 60 minutes, which are used to make the final hiring decision. During non-pandemic times, these often take place in person. Interview lengths aren’t standardized, and you won’t get the full interview for coding, since the interviewer will use some of it for other questions. Also, sometimes an interview will have two problems, usually an easier one followed by a harder one. So you can’t count on a specific amount of time to solve a problem. But if you can solve easier problems in around 20 minutes and harder problems in around 40 minutes, with medium problems somewhere in between, that should cover most scenarios. One difference in an interview situation as compared to the LeetCode experience is that the interviewer can help get you unstuck or guide you towards a good solution approach. So if you shoot for 20-40 minutes unassisted, that also gives you some buffer when you have a person helping you out.

• Interview conditions: This refers to a high-stakes test situation that could mean the difference between employment and unemployment. Also, coding on the whiteboard without autocomplete or Google, and an interviewer who may be reading email during the interview. LeetCode can’t simulate most of these conditions (though LeetCode contests can help produce a feeling of time pressure), so it’s best to do some mock interviewing in addition to problem practice.

How to Reach the Goal

The benefit of maintaining an unbroken streak in the LeetCoding Challenge is that you’re exposed to one new problem every day, and you get to practice solving a problem that you may not know how to approach. Since there’s an active discussion board for every problem, you can always look up information on the solution, whether or not you can solve it on your own. So at a minimum, you get a problem and a solution every day.

But what benefit does this really give you for The Goal? Let’s say you get lucky and, in a day-long series of interviews, every problem you get is one that you recognize from the LeetCoding Challenge. This will probably make you feel well-prepared, at least when you first hear the problem. But how well will it meet the requirements of the goal as stated above? My prediction is that it won’t help much. If you doubt this, you can try your own test: Pick a LeetCode problem that you have already solved but haven’t looked at in a while, and see if you can solve it in the required timeframe. If you can, and you can do this for several problems, then you may be in good shape. If not, another approach is needed.

If you log in to LeetCode, open the user menu at the top right corner of the page, and click on your user name, you’ll get a dashboard of information about your LeetCode usage. One of the sections is Problems Solved, and it includes the total number of problems, how many are in each difficulty level (Easy, Medium, Hard), and your acceptance rate. But one statistic that you won’t see on this page is how many of these previously solved problems you can currently solve quickly. This is a key metric to track for interview preparedness.

Spaced Repetition

Since The Goal is to perform well on new problems, a direct way to approach that goal would be to practice only new problems. That’s the default mode of using LeetCode, and it’s what the LeetCoding Challenge is set up for. Although working on new problems is more effective preparation than not working on any problems, it’s not a great way to prepare for interviews. The drawback of this approach is that it’s too slow. Although every new problem gives you a small benefit, you might need to solve hundreds of problems to become at all competent, and thousands of problems to reach an expert skill level.

Rather than focusing on increasing your total problem count, which just shows how many problems you solved at some point, I recommend instead focusing on how many problems you can currently solve without any help. Here’s a process you can use to do that:

• Find a source of new problems. The daily challenge is one source, and it can be a motivating way to solve a new problem every day. But you can also find suggested problems in the LeetCode discussions, or on the Problems tab.

• After you solve a new problem, think about whether it’s worth spending more time on (i.e., whether it’s a useful problem). I like to put each problem in one of the following categories:

  • Too easy: I can already solve it well enough when I first see it, so it’s not worth spending any more time on.
  • Too specialized: It may be a good problem for its own sake, but it’s not applicable to other problems.
  • Too similar: I’m already learning a problem like this.
  • For future practice: It’s a good quality problem that I want to learn.
  • Currently practicing: I’m practicing this problem on a schedule.
  • Mastered: I practiced this problem enough that I know it well, so I don’t need to spend any more time on it.

• When you start each practice session, select a problem from your currently practicing list. Keep track of when you practice it (date and time), how long it takes you to solve it (minutes and seconds), whether you can solve it on the first try (without repeatedly running and debugging it), and any other notes about how the practice session went.

• Based on how well you solved the problem, pick a date to practice it next. When you’re first learning a problem, you might practice it every day, or even multiple times per day. Over time, increase that to every few days, then once per week, then every few weeks. Once you’re doing well with daily practice on Problem A, add a Problem B to the mix, and increase the repetition delay for Problem A. Eventually, you’ll be able to quickly solve problems that you haven’t seen in weeks or months. This process is known as the spaced repetition technique.

Learning Algorithms

You may be suspicious about the process described above because it sounds like an attempt to learn programming through memorization. And there is a risk of using this process to simply memorize code without understanding the underlying concepts. But that’s not an effective way to do well on new problems, which is the ultimate goal. If you just memorize solutions, you probably won’t be able to adapt them when the problem details change.

The purpose of using spaced repetition on LeetCode problems is to learn the limited set of algorithms, data structures, and techniques required for interview problems, and learn to recognize which problems to apply them to. While you shouldn’t memorize code, you do have to learn to quickly implement binary search, BFS, DFS, tree traversal, and the other standard algorithms and data structures. It’s convenient to use LeetCode problems for that purpose because the online judge will tell you if your implementation has bugs, and because it’s better for interview preparation purposes to learn these algorithms in the context of relevant problems.

So those are my recommendations from practicing the 2020 daily challenges. It still takes a lot of practice to reach the point where you can confidently approach most problems that an interviewer throws your way. But if that’s your goal, this process is an efficient way to get there.