Leetcode 2021-04-13
🟢 783.minimum-distance-between-bst-nodes
#tree #depth-first-search #recursion

Given the root of a Binary Search Tree (BST), return the minimum difference between the values of any two different nodes in the tree.

Input: root = [4,2,6,1,3]
Output: 1

Leetcode 2021-04-14
🟡 208.implement-trie-prefix-tree
#design #trie

A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True

Leetcode 2021-04-15
🟡 213.house-robber-ii
#dynamic-programming

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.

Input: nums = [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.

Leetcode 2021-04-16
🔴 87.scramble-string
#string #dynamic-programming

We can scramble a string s to get a string t using the following algorithm:

Input: s1 = "great", s2 = "rgeat"
Output: true
Explanation: One possible scenario applied on s1 is:
"great" --> "gr/eat" // divide at random index.
"gr/eat" --> "gr/eat" // random decision is not to swap the two substrings and keep them in order.
"gr/eat" --> "g/r / e/at" // apply the same algorithm recursively on both substrings. divide at ranom index each of them.
"g/r / e/at" --> "r/g / e/at" // random decision was to swap the first substring and to keep the second substring in the same order.
"r/g / e/at" --> "r/g / e/ a/t" // again apply the algorithm recursively, divide "at" to "a/t".
"r/g / e/ a/t" --> "r/g / e/ a/t" // random decision is to keep both substrings in the same order.
The algorithm stops now and the result string is "rgeat" which is s2.
As there is one possible scenario that led s1 to be scrambled to s2, we return true.

Leetcode 2021-04-17
🟡 220.contains-duplicate-iii
#sort #ordered-map

Given an integer array nums and two integers k and t, return true if there are two distinct indices i and j in the array such that abs(nums[i] - nums[j]) <= t and abs(i - j) <= k.

Input: nums = [1,2,3,1], k = 3, t = 0
Output: true

Leetcode 2021-04-18
🟢 26.remove-duplicates-from-sorted-array
#array #two-pointers

Given a sorted array nums, remove the duplicates in-place such that each element appears only once and returns the new length.

// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

Leetcode 2021-04-19
🟢 27.remove-element
#array #two-pointers

Given an array nums and a value val, remove all instances of that value in-place and return the new length.

// nums is passed in by reference. (i.e., without making a copy)
int len = removeElement(nums, val);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

Leetcode 2021-04-19
🟢 27.remove-element

1️⃣ Tags
#array #two-pointers

2️⃣ Description
Given an array nums and a value val, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means a modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeElement(nums, val);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

3️⃣ Example

// nums is passed in by reference. (i.e., without making a copy)
int len = removeElement(nums, val);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

Leetcode 2021-04-20
🟢 28.implement-strstr

1️⃣ Tags
#two-pointers #string

2️⃣ Description
Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().

3️⃣ Example

Input: haystack = "hello", needle = "ll"
Output: 2

Leetcode 2021-04-21
🟡 91.decode-ways

1️⃣ Tags
#string #dynamic-programming

2️⃣ Description
A message containing letters from A-Z can be encoded into numbers using the following mapping:

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:


"AAJF" with the grouping (1 1 10 6)
"KJF" with the grouping (11 10 6)


Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".

Given a string s containing only digits, return the number of ways to decode it.

The answer is guaranteed to fit in a 32-bit integer.

3️⃣ Example

Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

Leetcode 2021-04-22
🔴 363.max-sum-of-rectangle-no-larger-than-k

1️⃣ Tags
#binary-search #dynamic-programming #queue

2️⃣ Description
Given an m x n matrix matrix and an integer k, return the max sum of a rectangle in the matrix such that its sum is no larger than k.

It is guaranteed that there will be a rectangle with a sum no larger than k.

3️⃣ Example

Input: matrix = [[1,0,1],[0,-2,3]], k = 2
Output: 2
Explanation: Because the sum of the blue rectangle [[0, 1], [-2, 3]] is 2, and 2 is the max number no larger than k (k = 2).

Leetcode 2021-04-23
🟡 368.largest-divisible-subset

1️⃣ Tags
#math #dynamic-programming

2️⃣ Description
Given a set of distinct positive integers nums, return the largest subset answer such that every pair (answer[i], answer[j]) of elements in this subset satisfies:


answer[i] % answer[j] == 0, or
answer[j] % answer[i] == 0


If there are multiple solutions, return any of them.

3️⃣ Example

Input: nums = [1,2,3]
Output: [1,2]
Explanation: [1,3] is also accepted.

Leetcode 2021-04-24
🟡 377.combination-sum-iv

1️⃣ Tags
#dynamic-programming

2️⃣ Description
Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.

The answer is guaranteed to fit in a 32-bit integer.

3️⃣ Example

Input: nums = [1,2,3], target = 4
Output: 7
Explanation:
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.

Leetcode 2021-04-25
🟢 897.increasing-order-search-tree

1️⃣ Tags
#tree #depth-first-search #recursion

2️⃣ Description
Given the root of a binary search tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only one right child.

3️⃣ Example

Input: root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

Leetcode 2021-04-26
🟡 1011.capacity-to-ship-packages-within-d-days

1️⃣ Tags
#array #binary-search

2️⃣ Description
A conveyor belt has packages that must be shipped from one port to another within D days.

The ith package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.

Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within D days.

3️⃣ Example

Input: weights = [1,2,3,4,5,6,7,8,9,10], D = 5
Output: 15
Explanation: A ship capacity of 15 is the minimum to ship all the packages in 5 days like this:
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10

Note that the cargo must be shipped in the order given, so using a ship of capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed.

Leetcode 2021-04-27
🟢 938.range-sum-of-bst

1️⃣ Tags
#tree #depth-first-search #recursion

2️⃣ Description
Given the root node of a binary search tree, return the sum of values of all nodes with a value in the range [low, high].

3️⃣ Example

Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32

Leetcode 2021-04-28
🟡 633.sum-of-square-numbers

1️⃣ Tags
#math

2️⃣ Description
Given a non-negative integer c, decide whether there're two integers a and b such that a2 + b2 = c.

3️⃣ Example

Input: c = 5
Output: true
Explanation: 1 * 1 + 2 * 2 = 5

Leetcode 2021-04-29
🔴 403.frog-jump

1️⃣ Tags
#dynamic-programming

2️⃣ Description
A frog is crossing a river. The river is divided into some number of units, and at each unit, there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.

Given a list of stones' positions (in units) in sorted ascending order, determine if the frog can cross the river by landing on the last stone. Initially, the frog is on the first stone and assumes the first jump must be 1 unit.

If the frog's last jump was k units, its next jump must be either k - 1, k, or k + 1 units. The frog can only jump in the forward direction.

3️⃣ Example

Input: stones = [0,1,3,5,6,8,12,17]
Output: true
Explanation: The frog can jump to the last stone by jumping 1 unit to the 2nd stone, then 2 units to the 3rd stone, then 2 units to the 4th stone, then 3 units to the 6th stone, 4 units to the 7th stone, and 5 units to the 8th stone.

Leetcode 2021-04-30
🟡 137.single-number-ii

1️⃣ Tags
#bit-manipulation

2️⃣ Description
Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.

3️⃣ Example

Input: nums = [2,2,3,2]
Output: 3