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

Leetcode 2021-05-01
🟢 690.employee-importance

1️⃣ Tags
#hash_table #depth_first_search #breadth_first_search

2️⃣ Description
You are given a data structure of employee information, which includes the employee's unique id, their importance value and their direct subordinates' id.

For example, employee 1 is the leader of employee 2, and employee 2 is the leader of employee 3. They have importance value 15, 10 and 5, respectively. Then employee 1 has a data structure like [1, 15, [2]], and employee 2 has [2, 10, [3]], and employee 3 has [3, 5, []]. Note that although employee 3 is also a subordinate of employee 1, the relationship is not direct.

Now given the employee information of a company, and an employee id, you need to return the total importance value of this employee and all their subordinates.

3️⃣ Example

Input: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1
Output: 11
Explanation:
Employee 1 has importance value 5, and he has two direct subordinates: employee 2 and employee 3. They both have importance value 3. So the total importance value of employee 1 is 5 + 3 + 3 = 11.

Leetcode 2021-05-02
🟡 554.brick-wall

1️⃣ Tags
#hash_table

2️⃣ Description
There is a rectangular brick wall in front of you with n rows of bricks. The ith row has some number of bricks each of the same height (i.e., one unit) but they can be of different widths. The total width of each row is the same.

Draw a vertical line from the top to the bottom and cross the least bricks. If your line goes through the edge of a brick, then the brick is not considered as crossed. You cannot draw a line just along one of the two vertical edges of the wall, in which case the line will obviously cross no bricks.

Given the 2D array wall that contains the information about the wall, return the minimum number of crossed bricks after drawing such a vertical line.


3️⃣ Example

Input: wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]
Output: 2

Leetcode 2021-05-03
🟢 7.reverse-integer

1️⃣ Tags
#math

2️⃣ Description
Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-231, 231 - 1], then return 0.

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

3️⃣ Example

Input: x = 123
Output: 321

Leetcode 2021-05-04
🔴 1473.paint-house-iii

1️⃣ Tags
#dynamic_programming

2️⃣ Description
There is a row of m houses in a small city, each house must be painted with one of the n colors (labeled from 1 to n), some houses that have been painted last summer should not be painted again.

A neighborhood is a maximal group of continuous houses that are painted with the same color.


For example: houses = [1,2,2,3,3,2,1,1] contains 5 neighborhoods [{1}, {2,2}, {3,3}, {2}, {1,1}].


Given an array houses, an m x n matrix cost and an integer target where:


houses[i]: is the color of the house i, and 0 if the house is not painted yet.
cost[i][j]: is the cost of paint the house i with the color j + 1.


Return the minimum cost of painting all the remaining houses in such a way that there are exactly target neighborhoods. If it is not possible, return -1.

3️⃣ Example

Input: houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
Output: 9
Explanation: Paint houses of this way [1,2,2,1,1]
This array contains target = 3 neighborhoods, [{1}, {2,2}, {1,1}].
Cost of paint all houses (1 + 1 + 1 + 1 + 5) = 9.

Leetcode 2021-05-05
🟡 740.delete-and-earn

1️⃣ Tags
#dynamic_programming

2️⃣ Description
Given an array nums of integers, you can perform operations on the array.

In each operation, you pick any nums[i] and delete it to earn nums[i] points. After, you must delete every element equal to nums[i] - 1 or nums[i] + 1.

You start with 0 points. Return the maximum number of points you can earn by applying such operations.

3️⃣ Example

Input: nums = [3,4,2]
Output: 6
Explanation: Delete 4 to earn 4 points, consequently 3 is also deleted.
Then, delete 2 to earn 2 points.
6 total points are earned.

Leetcode 2021-05-06
🟢 1720.decode-xored-array

1️⃣ Tags
#bit_manipulation

2️⃣ Description
There is a hidden integer array arr that consists of n non-negative integers.

It was encoded into another integer array encoded of length n - 1, such that encoded[i] = arr[i] XOR arr[i + 1]. For example, if arr = [1,0,2,1], then encoded = [1,2,3].

You are given the encoded array. You are also given an integer first, that is the first element of arr, i.e. arr[0].

Return the original array arr. It can be proved that the answer exists and is unique.

3️⃣ Example

Input: encoded = [1,2,3], first = 1
Output: [1,0,2,1]
Explanation: If arr = [1,0,2,1], then first = 1 and encoded = [1 XOR 0, 0 XOR 2, 2 XOR 1] = [1,2,3]

Leetcode 2021-05-07
🟢 1486.xor-operation-in-an-array

1️⃣ Tags
#array #bit_manipulation

2️⃣ Description
Given an integer n and an integer start.

Define an array nums where nums[i] = start + 2*i (0-indexed) and n == nums.length.

Return the bitwise XOR of all elements of nums.


3️⃣ Example

Input: n = 5, start = 0
Output: 8
Explanation: Array nums is equal to [0, 2, 4, 6, 8] where (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8.
Where "^" corresponds to bitwise XOR operator.