Deriving Time Complexity of Top-Down DP

Introduction

Calculating time complexity for recursive Dynamic Programming solutions often feels like a crapshoot. This stems from the fact that top-down recursive solutions aren’t as clean and neat as its bottom-up counterparts.

Well, let’s take the guesswork out of this and follow a framework for calculating the time complexity by walking through a Leetcode problem.

Before starting this tutorial, take a look at 1473. Paint House III and my accompanying solution.

Disclaimer

The goal of this article isn’t to walk through how to solve the problem. We are looking at how to calculate the time…


Have you ever found yourself struggling with a Dynamic Programming question on Leetcode? Yes. Have you ever clicked the Discuss tab to get an explanation on that DP question? Yes. Have you ever gotten MORE frustrated because all the posts are optimized bottom-up solutions with ZERO thoughts behind the code? YES.

This post is my attempt to counter that frustration. I’m not going to show you an optimized tabular solution. I’m going to show you the dirty top-down recursion approach. Because by understanding this, you can actually understand DP.

Today I’ll be covering the Target Sum Leetcode question. …


Before we start, I want to emphasize that the goal of this article is not to teach you how to solve graph patterns. Instead, I will simply be showing you that these subpatterns within graph patterns exist.

Graph problems are a crucial topic that you’ll need to master for technical interviewing. When you read about graphs, articles usually focus on the following:

  1. Representation — Adjacency List vs. Adjacency Matrix
  2. Traversals — BFS vs. DFS

These are core concepts but we need to recognize the different variations that these graph problems ask. Each variation appears to be the same on a…


Introduction

Today we’ll be dissecting the first of two common patterns in Binary Tree problems. I’m extra excited to write this post because Trees were my weakest link. Of course, the best way to improve your weakest link is to focus on it, so I did tons of Tree problems and noticed two recurring patterns. I’ll cover the first pattern here and follow up with a Part 2 later.

I’m going to skip the overview for this topic because there’s a lot to say for trees. …


Introduction

Welcome to the 3rd article in my series, Leetcode is Easy! Today we’ll be covering problems relating to the ‘Interval’ category. I’ll start with an overview, walk through key steps with an example, and then give tips on approaching this problem. As always, I’ll end with a list of questions so you can practice and internalize this patten yourself.

We’ll be following the question Merge Intervals, so open up the link and follow along!

Overview

What is an interval? An Interval is “an intervening period of time”.

Thanks, dictionary.com.

An interval for the purpose of Leetcode and this article is an…


Introduction

Today we’ll be learning about the Sliding Window pattern. I’ll go through an overview, walk through the 3 keys steps with an example, and give you a general set of rules to use. As usual, I’ll leave you with a list of practice questions so you can internalize and master the approach yourself.

Overview

Sliding Window is an extension of the two pointer approach where we use two pointers (left and right) to create a “window”. The problem will ask us to return the maximum or minimum subrange that satisfies a given condition. Thus the “window” in between our left and…


Welcome to the first post in my series, Leetcode is Easy!

Introduction

Today we’ll be learning about the Two Pointer approach. I’ll go through an overview, talk about variations, and teach you how to recognize when to use this technique. Finally, I’ll leave you with a list of practice questions so you can internalize and master the approach yourself.

Let’s get started!

Overview

So, what is a pointer? A pointer is an object that stores the memory address of another object. Inception! In plain English, a pointer references another object. An easy way to remember is a pointer points at another object…


This is the introductory post on my new series, DP is Easy!

Dynamic Programming. Say these 2 words to a software engineer and watch them shriek in pain. DP is a topic that many are scared of. Solutions often seem like black magic. DP is a topic you will almost certainly be tested on if you interview for a FAANG or other large Bay Area tech companies. And whatever context you’re coming across Dynamic Programming for, it is most likely surrounded by negativity.

I’m here to change that. I’m here to convince you that Dynamic Programming is actually easy. DP is a misunderstood child. Once we understand the how’s and why’s behind DP, it becomes our friend.

Dynamic Programming is… Easy!

Tim Park

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store