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.

- 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. - Preorder: Using the property of
**preorder-traversal**=`(print)(Left-Subtree)(Right-Subtree)`

, the**first node**of each divided group is the`“root node”`

. …

**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

- If
`s[i]!=t[j]`

, then`dp[i][j]=0`

(definition of dp[i][j]) - If
`s[i]==t[j]`

, then`dp[i][j] = dp[i-1][j-1] + 1`

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

- [
**5**,**3**,1] -> [3,**5,1**] -> [3,1,5] - [
**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.

**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 makeall the elementsto 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.

**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 “`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. …

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.

The key point here is that you call `swapTree(root->left)`

and `swapTree(root->right)`

**BEFORE** the `swap`

operation.

Never stop learning.