Hello! Today, we’ll look at a tree question on Leetcode.

Our goal is to find the proper BST from the given preorder traversal. Before diving into the solution, there are two intuitions we should catch.

  1. Given the root, all nodes of the left-subtree have smaller values than the root and all nodes of the right-subtree have greater values than the root.
  2. Preorder: Using the property of preorder-traversal = (print)(Left-Subtree)(Right-Subtree), the first node of each divided group is the “root node”. …


Unsplash

Problem Link: https://leetcode.com/problems/decode-ways/

Hello! Today we’ll be looking at a dynamic programming question: Decode Ways. I found out that many people find this question hard. I will be demonstrating my thought process as well as the detailed explanation.

Before getting into the explanation, I really want to talk about the crux of Dynamic Programming: “How to solve any DP problem?”. I, of course, cannot solve every single DP question out there but I’ve got much better than before by understanding the core concept of DP.

Before you start writing codes, set up a clear recurrence relation(top-down)

As you’ve seen in…


Problem Link: https://binarysearch.com/problems/Longest-Common-Substring

Hello! Today we’ll be looking at another typical dynamic programming problem: Longest Common Substring. Notice that this is different from “Longest Common Subsequence”. A substring is a contiguous chunk of subarray while a subsequence is a subarray whose elements need not be adjacent to each other.

Longest Common Substring can be solved with a slight variation of the Longest Common Subsequence.

Let dp[i][j] = The length of the longest common substring ending at [i,j].

There are TWO important intuitions to form a recurrence relation

  1. If s[i]!=t[j], then dp[i][j]=0 (definition of dp[i][j])
  2. If s[i]==t[j], then dp[i][j] = dp[i-1][j-1] + 1

Code

Time Complexity: O(n*m)


Problem Link: https://binarysearch.com/problems/0-1-Knapsack

Hello! Today, we’ll be looking at one of the most popular dynamic programming questions: 0–1 Knapsack.

This question can brush up on your fundamental dynamic programming skills as it clearly shows how dynamic programming works so make sure you fully understand this question! Assuming you have fully read and tried this problem, I will go straight to the point.

We have two arrays as input: weights and values. Also, we have the capacity of a “knapsack” into which we want to put items to maximize the total value(profit) of the items in the knapsack.

We can come…


Hello! Today, we’ll be looking at bubble sort. Bubble sort is a sorting algorithm that behaves like “bubbles” and takes O(n²) time complexity. The key point of bubble sort is that “For each iteration, we drag the greatest element to the end(decrement by 1 each time) by each consecutive pair”. Let’s take an example.

  1. [5,3,1] -> [3,5,1] -> [3,1,5]
  2. [3,1,5] -> [1,3,5]

Notice that for each iteration, the last element is replaced by the greatest element. Therefore, decrement the searching range of the array by 1 for each iteration.

A slight optimization can be done. If nothing happens for an iteration, then it means the array is already sorted so pause it.

Implementation


Problem Link: https://binarysearch.com/problems/Making-List-Values-Equal

Hello! Today’s we’ll be looking at an array question. Although it’s an “easy” question, it might be quite tricky to approach. As we can select multiple elements and increment them by 1 at the same time, there’s one thing you need to catch

Since there is no “decrement”, we eventually have to make all the elements to the “maximum element”.

Let’s take an example. Consider [1,7,7,9]. Then we need to make 1,7,7 to 9. Notice that a straight-up solution would be to increment each element by [9-element]. However, as we can operate on multiple items at the…


Problem Link: https://binarysearch.com/problems/Tree-Traversal

Hello! Today we’ll be looking at a tree traversal problem. This can be solved quite simply once you know how to traverse to the right child, left child, and “parent”. Traversing to the right and left child is trivial but how can we jump to the parent? It can be solved using the hash map. First, we traverse from the root to the leaf nodes and save each node’s parent into the hash map. Then, perform the particular instructions given in the question.

Implementation

Time Complexity: O(n)


Link: https://binarysearch.com/problems/Longest-Repeating-Sublist-After-K-Updates

Hello! Today we’ll be looking at an array question. You’re given one operation which is to change any element in the array to any value. Then, you need to perform K operations to create the longest repeating subarray. Keep in mind that “subarray” is contiguous while “subsequencedoesn’t have to be adjacent to each other.

This question is categorized as “easy” but might seem quite tricky to come up with a solution. Let me take an example test case. …


Hash map is an associative data structure which implements an associative array data type. The concept of hash map is quite simple. Hash map stores data as a (key,value) pair. For instance, in (“Jason”,”HKU”), “Jason” is the key and “HKU” is the value.

When the hash map takes a key-value input, hash function is used to convert the key to the appropriate hash code. There are many hash functions but in this particular case, we will be using the hash function where you add up all the characters(int) and perform modular operation by the hash map’s size. …


Problem Link: https://binarysearch.com/problems/Invert-Tree

Do you know how to invert a tree? If you don’t this is your time to learn!

It’s actually quite simple to invert a tree. Let’s look directly at the code.

inverTree.cpp

The key point here is that you call swapTree(root->left) and swapTree(root->right) BEFORE the swap operation.

Changjin

Never stop learning.

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