Last week, we looked at a problem involving a subarray. A subarray is a contiguous sequence of elements from an array, meaning we can’t skip any elements when building the answer. A subsequence, on the other hand, allows us to skip elements, though the elements in the subsequence still need to stay in their original order.

LeetCode 300: Longest Increasing Subsequence says:

Given an integer array nums, return the length of the longest strictly increasing subsequence.

So we’re allowed to skip elements, but we can’t change the order of the elements, and for this problem, the elements in the solution must be strictly increasing.

« Continue »

The maximum subarray problem is famous enough to have its own Wikipedia page, and a named algorithm you can use to solve it (Kadane’s Algorithm). But rather than looking up the algorithm, we’ll derive the solution to LeetCode 53: Maximum Subarray using principles of dynamic programming.

The problem statement is simple. Here’s the LeetCode version:

Given an integer array nums, find the subarray with the largest sum, and return its sum.

A subarray is a contiguous and non-empty sequence of elements from the input array. So we’re looking for the largest sum of all values from nums[i] to nums[j] (inclusive), where i <= j.

« Continue »

Using what we have covered so far, you can analyze a dynamic programming problem and solve it using DP techniques and concepts. But after solving a few problems, you might still feel like you have to invent a new solution each time. In the introduction to this year’s project, I promised to explain a process for designing Dynamic Programming algorithms. This week, I’ll fill in a few details that make solving DP problems more of a repeatable process.

« Continue »

Last week, we looked at a dynamic programming problem for the Jump Game problem. If you implement that solution and run it on LeetCode, you’ll notice that your runtime and memory scores are very low compared to other users. Let’s see why that is.

« Continue »

Let’s solve LeetCode problem 55 (Jump Game) using dynamic programming. Next week, we’ll consider a sneaky aspect of this problem.

The problem:

You are playing a game on a number line where the aim is to reach position n-1 starting from position 0. As input, you get an array nums of size n containing non-negative integers. From position i, you can move forward any distance between 0 and nums[i] (inclusive). Can you reach the last position to win the game?

« Continue »

To solve a problem using dynamic programming, you have to break it into subproblems, solve those subproblems, and use the results to solve the original problem. So the first step in solving a dynamic programming problem is defining what subproblems you need to solve.

« Continue »

To see how the elements of dynamic programming come together in a real problem, let’s explore the classic dynamic programming problem Coin Change (LeetCode 322).

« Continue »

Binary search is an algorithm. It provides step-by-step instructions for efficiently finding a value in a sorted list. A hash table is a data structure. It provides an efficient way to map keys to values. Dynamic programming is an algorithmic technique, or more formally, an algorithmic paradigm. Like divide and conquer, backtracking, or greedy, it refers to a class of algorithms, not a specific algorithm.

Although the term “dynamic programming” doesn’t refer to a specific algorithm, dynamic programming solutions use algorithms and data structures. To solve a LeetCode problem using dynamic programming, you have to write an algorithm to process the input, and you need a data structure to store intermediate results. But the specific algorithm and data structure are not identified for you. This differs from solving a problem tagged as binary search or hash table, where the algorithm or data structure is in the tag. However, dynamic programming problems have some similarities with each other. We will learn about strategies, guidelines, and patterns for solving them.

Dynamic programming (the word programming refers not to coding, but to mathematical optimization) allows us to efficiently solve certain types of problems that can be broken down into subproblems. If you find when solving a problem that you are repeatedly calculating the same value or passing the same parameters to the same function, that’s a sign that dynamic programming may apply. The efficiency of dynamic programming comes from retrieving the results of previous calculations rather than recalculating them.

In technical terms, we say that dynamic programming is a good choice when a problem has these two characteristics:

• Overlapping subproblems: When you break the problem into subproblems, you find the same subproblems coming up repeatedly.

• Optimal substructure: You can use the optimal solution to the subproblems to find the optimal solution to the overall problem.

Some problems have only overlapping subproblems or only optimal substructure. Dynamic programming is only efficient when a problem has both.

Our goal in studying dynamic programming this year is to learn to solve most Easy and Medium LeetCode problems tagged with that topic. To reach that goal, we will:

• Understand the elements of dynamic programming.

• Apply that understanding to solve specific LeetCode problems.

• Use the model problem/solution approach to select model dynamic programming problems, write model solutions for them, and use spaced repetition to understand and remember what we learn.

Reference: Introduction to Algorithms (CLRS) Chapter 14 covers dynamic programming.

(Image credit: DALL·E 3. The knapsack problem can be solved using dynamic programming.)

For an introduction to this year’s project, see A Project for 2024.

During 2023, I published 50 tips for effective LeetCode practice.

The tips cover LeetCode practice fundamentals, ideas for fine-tuning the practice process, and how results from learning research can apply to learning algorithms. I think they cover all the ideas you would need to create a detailed, personalized learning plan.

The fundamental tips are organized around a model problem/solution process. The basic process: find a good problem; write a detailed explanation and a code solution for that problem; and use the solution as a model for solving similar problems.

When you’re first learning the model problem/solution process, you might rely too much on applying a solution template to solve problems. That’s fine for Easy and Easy-Medium problems, which are straightforward knowledge tests. But it can break down on harder problems, which require more creativity.

To address this, I suggested in Tip 40 that studying dynamic programming is a way to learn the process of finding the solution rather than just learning the solution. Unlike other LeetCode algorithm topics, Dynamic Programming is a process for designing algorithms, not a step-by-step process for finding a solution.

So we’ll start the year with an overview of Dynamic Programming, and in the coming weeks, we’ll cover the background required to solve DP problems. Our goal will be to learn enough about Dynamic Programming to solve most Easy and Medium problems, and to practice the tips with specific problems from the LeetCode problem library.

(Image credit: DALL·E 3)

Let’s review the 50 LeetCode tips from the past year.

Fundamentals of LeetCode Practice

Coding interviews

Many software companies use a coding interview as part of their hiring process. Candidates are asked to solve algorithmic coding problems on the fly. Since this isn’t something programmers practice much in their jobs, or even in school, practice is required. LeetCode provides the right kinds of problems, along with learning materials, an active community, and an easy-to-use online judge.

Topics

Each LeetCode problem is associated with one or more topics, such as hash tables, sorting, and binary search. Learning about the topics helps you solve the problems, and practicing the problems helps you understand the topics. Our first goal is, given a topic, to learn how to solve LeetCode problems for that topic.

Model problems

To learn how to solve problems for a topic, I suggest the model problem/solution approach. Rather than learning a topic in isolation, pick a problem that uses that topic and learn every detail required to solve that problem. A model problem is right for this purpose if it focuses primarily on the topic you’re learning and has the appropriate difficulty for your current skill level. Learn enough model problems for each topic that you cover the key ideas for that topic.

Model solutions

For each of your model problems, create a model solution containing your best solution for that problem, based on your own attempts and other solutions that you find in your research. Explain your model solution using code, code comments, written explanations, and diagrams. If you have trouble during a practice session, take that as a sign that you should make a part of your model solution clearer. To ensure that you include all the relevant details in each model solution, use a template to write it.

Spaced repetition

No matter how carefully you select your model problem and write up your model solution, you will only be able to solve it on demand (as in a coding interview) if you practice solving it from scratch. The best way to practice is spaced repetition. This means practicing a problem, waiting for an interval, practicing it again, and repeating that process until you master it. After each repetition, decide based on your performance whether you should increase or decrease the repetition interval, and by how much. An exponential series (1 day, 2 days, 4 days, 8 days, etc.) works well as a rule of thumb for repetition interval lengths.

Although spaced repetition is often associated with memorization, that isn’t its purpose when you use it for problem-solving practice. Instead, during each repetition, think about updating your model solution so it’s more useful for your practice, fine-tuning the repetition interval, focusing on learning a difficult part of a problem, switching to a more appropriate problem, understanding every detail of the problem, and developing solution building blocks for solving other problems.

Using the correct interval length is key to making the spaced repetition process work. After each repetition, determine the most appropriate interval length for your current level of mastery for that problem.

Daily practice

LeetCode supports daily practice through the Daily LeetCoding Challenge problem, streak tracking, and other gamification mechanisms. But because the daily problem is the same for everyone, it may not be the best problem for each person given their current learning goal. If you take part in the daily challenge, use it to get exposed to new problems. But maintain your own list of model problems and practice them using your own daily schedule based on the spaced repetition process.

To get the most out of your customized daily practice process, maintain a practice journal. This journal will help you keep track of what to work on next and what specific aspects of each problem you need to focus on.

One way to think of daily practice is as the process of learning general skills using specific problems. Rather than learning about binary search in the abstract, or writing a general binary search implementation, use the specific scenarios provided in your model problems. By practicing these problems repeatedly, you will learn to associate scenarios with the algorithms and data structures you’re learning. The specific components of each scenario will act as cues that make it easier to remember how to use the algorithms and data structures when you need them for new problems.

Problem lists

Topic-wise practice, where you learn topics by solving several problems from each topic, is the best way to choose LeetCode problems during the beginning and intermediate stages of your study. You can use LeetCode’s topic tags to find appropriate problems. There are also sites like Tech Interview Handbook and NeetCode that offer curated problem lists. These offer the most useful problems from all available problems in a tag and suggest the best order in which to solve them.

Syntax and libraries

Since the model problem/solution process is based on implementing runnable solutions that you can submit to LeetCode, it requires learning the parts of a programming language that are most useful for algorithmic problem solving. This is more about depth than breadth. You only need to learn certain parts of the language, but you need to learn them well. You can divide these parts into two main categories: language syntax and language libraries.

Fine-Tuning the Learning Process

Remembering and understanding

To solve LeetCode problems, you need to know how to implement and adapt specific algorithms and data structures. But there are too many problem variations to memorize every solution. So you need to find a balance between remembering enough of the material to retrieve it quickly, while understanding it well enough that you can apply it to new problems.

Learning algorithms and data structures using the model problem/solution approach promotes a virtuous cycle. As you learn more about these topics, you get better at solving related problems. And solving problems reinforces what you’re learning.

By writing your own model solutions, you can make them memorable for you, not just for the general reader. Techniques for making your solutions memorable include explaining them in multiple ways, using diagrams, picking good identifier names, writing hints, making notes about which parts are hard to remember, using automatic logging, understanding multiple levels of abstraction, dividing your solution into chunks, and re-writing your solution as you gain experience. As you build up a library of model solutions, you can think of them as an algorithmic and data structures textbook that is customized for you.

Practice

You can’t practice for a coding interview just by doing your regular job. Although there is some overlap with regular programming work, LeetCode problem-solving practice requires a different mindset from coding real-world software or studying computer science. This mindset is encapsulated in the principles of deliberate practice.

Learn to find the solution

When you first learn a LeetCode topic, the goal is to learn the coding patterns required to solve Easy and Easy-Medium problems in that topic. But solving Medium-Hard and Hard problems requires a deeper understanding of the topic. One way to approach this after you master an implementation is to learn the steps that would be required to find the implementation, from the perspective of someone inventing an algorithm from scratch.

Solving dynamic programming (DP) problems is a good way to practice adapting a solution to each problem, since DP is an algorithmic design paradigm rather than a single algorithm. Once you know the basics of dynamic programming, learn how to identify problems that DP is good for and how to apply the DP framework. Then practice LeetCode problems that are tagged with dynamic programming.

Problem-solving

Model solutions give you a head start on similar problem types. But you should also practice using a problem-solving process that works even when you can’t directly apply a model solution. For harder problems that require more creativity, you can try techniques developed by problem-solving experts to get un-stuck.

Learning sub-problems

The fundamental unit of LeetCode practice is a single problem. But sometimes that isn’t granular enough, and it’s better to isolate the specific part of a problem that is giving you trouble. With a minor adjustment, you can also use the LeetCode platform to practice these sub-problems. A Jupyter Notebook is another useful tool for learning and documenting blocks of code that are smaller than a full solution.

Time management

One advantage of a well-designed practice process is minimizing how much time you spend on each problem. By practicing concepts and problems in the right order, you can focus on learning what you need to know rather than spending hours on a problem that you don’t have the background for. It’s good to spend as much time as necessary to understand a concept, but only once you have mastered the prerequisite concepts.

Debugging

Just as LeetCode coding differs from real-world coding, debugging your LeetCode solution differs from debugging real-world software. With LeetCode, you can assume that the official tests are valid and comprehensive. And you can limit the time you spend debugging since you always have the option to consult a working solution.

If you decide that your solution is mostly correct and just needs a few bug fixes, a few techniques can make debugging more effective. You can try rewriting a problematic section to be easier to understand, checking loop invariants to verify that variables have expected values at certain points, and writing your own minimal test cases to narrow down the problem.

Debugging a LeetCode problem requires learning how to write LeetCode test cases. When you submit your solution, the LeetCode online judge runs it on a variety of test cases designed to expose bugs. But to understand a solution, it’s best to also design your own test cases. Doing this makes you think about how your solution processes different types of data.

Advice from Learning Research

Skill transfer

One of the main challenges when learning anything is how to transfer what you learn in one context so you can apply it to a different context. This is more likely to happen when the two contexts have some overlap, when you have a fundamental understanding of what you are trying to transfer, when you use good practice techniques, and when you focus on the basics of the skills that you’re trying to transfer.

Learning plateaus

Learning a new skill is fast in the beginning, and then progress levels out. To avoid getting stuck on a learning plateau, you need to master the fundamentals, unlearn any habits that are holding you back, spend more time writing your own original solutions, and consider what you actually need to know to accomplish your goals.

The zone of optimal improvement

You will learn more efficiently if you practice problems at the right difficulty level. LeetCode offers Easy, Medium, and Hard problems. Within those categories, problems can be easier or harder depending on what problem types you have experience with. But you can also adjust any problem’s difficulty level by adjusting the time between repetitions, adjusting the number of different topics you practice together, and trying to solve a problem without looking at any reference materials.

Getting advice from books

Books can describe algorithms and data structures, but they can also provide more general advice by telling you how to avoid bad choices, giving you ideas to choose from, encourage useful patterns of thinking, acting as expert coding buddies, and occasionally giving you a critical insight that helps you in a job or an interview.

Memory

If you stop practicing LeetCode for a while, it may seem like you forget how to do that type of programming. Fortunately, these skills don’t disappear completely. Although they may get rusty, refreshing them is much less work than learning them in the first place (as long as you really learned them the first time around).

Improving through practice

Although practicing is necessary for improvement, it isn’t sufficient. If you only practice what you already know, you won’t improve. Use your practice journal to find areas for improvement that you can work on in your daily practice.

Focus on the problem

Each LeetCode problem is a test of how well you can apply the algorithms and data structures that apply to that problem. But it’s not enough just to apply a cookbook approach. Problems at the Medium level and higher contain tricky parts that can trip up a basic solution. The key is to know the algorithm well enough that you can focus on the problem and its unique challenges.

Wrapping Up

Beyond model solutions

These tips focus on the model problem/model solution approach because it’s the best way to learn the required topics. But the ultimate goal of LeetCode practice is to learn to solve problems you haven’t seen before. The way to get better at that is just to follow the standard advice: practice more problems.

Glossary

These tips use some specialized terms. You can find definitions in the glossary.

Summary

As a summary of these tips, I would give two suggestions:

1. If you have trouble learning a concept, break it into pieces and start by learning one piece.
2. If you have trouble remembering a concept, find a problem or part of a problem and practice that concept using spaced repetition.

(Image credit: DALL·E 3)