# [Leetcode] #1008 Construct Binary Search Tree from Preorder Traversal(C++/Tree/Medium)

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”`. …

# [Algorithm] Leetcode #91 Decode Ways (DP/Medium/C++) — How to solve ANY DP

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…

# [Algorithm] Longest Common Substring (C++/DP/Medium)

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)

# [Algorithm]0–1 Knapsack (C++/DP)

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…

# [Sorting] Bubble Sort (Full Implementation/C++)

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.

# [Algorithm] Making List Values Equal(Array/C++)

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…

# [Algorithm] Tree Traversal (Array/C++)

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)

# [Algorithm] Longest Repeating Subarray after K Updates(Array/C++)

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 “`subsequence`doesn’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. …

# [Data Structure] Hash Map(Full Implementation/C++)

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. …

# [Algorithm] Invert Tree (Tree/C++)

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