Huahua’s Tech Road

花花酱 LeetCode 114. Flatten Binary Tree to Linked List

By zxi on November 27, 2021

Given the root of a binary tree, flatten the tree into a “linked list”:

The “linked list” should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
The “linked list” should be in the same order as a pre-order traversal of the binary tree.

Example 1:

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

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [0]
Output: [0]

Constraints:

The number of nodes in the tree is in the range [0, 2000].
-100 <= Node.val <= 100

Follow up: Can you flatten the tree in-place (with O(1) extra space)?

Solution 1: Recursion

Time complexity: O(n)
Space complexity: O(|height|)

Python3

# Author: Huahua

class Solution:

def flatten(self, root: Optional[TreeNode]) -> None:

"""

Do not return anything, modify root in-place instead.

"""

def solve(root: Optional[TreeNode]):

if not root: return None, None

if not root.left and not root.right: return root, root

l_head = l_tail = r_head = r_tail = None

if root.left:

l_head, l_tail = solve(root.left)

if root.right:

r_head, r_tail = solve(root.right)

root.left = None

root.right = l_head or r_head

if l_tail:

l_tail.right = r_head

return root, r_tail or l_tail

return solve(root)[0]

Solution 2: Unfolding

Time complexity: O(n)
Space complexity: O(1)

Python3

# Author: Huahua

class Solution:

def flatten(self, root: Optional[TreeNode]) -> None:

while root:

if root.left:

prev = root.left

while prev.right: prev = prev.right

prev.right = root.right

root.right = root.left

root.left = None

root = root.right

花花酱 LeetCode 2088. Count Fertile Pyramids in a Land

By zxi on November 27, 2021

A farmer has a rectangular grid of land with m rows and n columns that can be divided into unit cells. Each cell is either fertile (represented by a 1) or barren (represented by a 0). All cells outside the grid are considered barren.

A pyramidal plot of land can be defined as a set of cells with the following criteria:

The number of cells in the set has to be greater than 1 and all cells must be fertile.
The apex of a pyramid is the topmost cell of the pyramid. The height of a pyramid is the number of rows it covers. Let (r, c) be the apex of the pyramid, and its height be h. Then, the plot comprises of cells (i, j) where r <= i <= r + h - 1 and c - (i - r) <= j <= c + (i - r).

An inverse pyramidal plot of land can be defined as a set of cells with similar criteria:

The number of cells in the set has to be greater than 1 and all cells must be fertile.
The apex of an inverse pyramid is the bottommost cell of the inverse pyramid. The height of an inverse pyramid is the number of rows it covers. Let (r, c) be the apex of the pyramid, and its height be h. Then, the plot comprises of cells (i, j) where r - h + 1 <= i <= r and c - (r - i) <= j <= c + (r - i).

Some examples of valid and invalid pyramidal (and inverse pyramidal) plots are shown below. Black cells indicate fertile cells.

Given a 0-indexed m x n binary matrix grid representing the farmland, return the total number of pyramidal and inverse pyramidal plots that can be found in grid.

Example 1:

Input: grid = [[0,1,1,0],[1,1,1,1]]
Output: 2
Explanation:
The 2 possible pyramidal plots are shown in blue and red respectively.
There are no inverse pyramidal plots in this grid. 
Hence total number of pyramidal and inverse pyramidal plots is 2 + 0 = 2.

Example 2:

Input: grid = [[1,1,1],[1,1,1]]
Output: 2
Explanation:
The pyramidal plot is shown in blue, and the inverse pyramidal plot is shown in red. 
Hence the total number of plots is 1 + 1 = 2.

Example 3:

Input: grid = [[1,0,1],[0,0,0],[1,0,1]]
Output: 0
Explanation:
There are no pyramidal or inverse pyramidal plots in the grid.

Example 4:

Input: grid = [[1,1,1,1,0],[1,1,1,1,1],[1,1,1,1,1],[0,1,0,0,1]]
Output: 13
Explanation:
There are 7 pyramidal plots, 3 of which are shown in the 2nd and 3rd figures.
There are 6 inverse pyramidal plots, 2 of which are shown in the last figure.
The total number of plots is 7 + 6 = 13.

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 1000
1 <= m * n <= 10⁵
grid[i][j] is either 0 or 1.

Solution: DP

Let dp[i][j] be the height+1 of a Pyramid tops at i, j
dp[i][j] = min(dp[i+d][j – 1], dp[i + d][j + 1]) + 1 if dp[i-1][j] else grid[i][j]

Time complexity: O(mn)
Space complexity: O(mn)

Python

# Author: Huahua

class Solution:

def countPyramids(self, grid: List[List[int]]) -> int:

m = len(grid)

n = len(grid[0])

ans = 0

@cache

def dp(i: int, j: int, d: int) -> int:

if grid[i][j] and 0 <= i + d < m and 0 < j < n - 1 and grid[i + d][j]:

return min(dp(i + d, j - 1, d), dp(i + d, j + 1, d)) + 1

return grid[i][j]

for i, j in product(range(m), range(n)):

ans += max(0, dp(i, j, 1) - 1)

ans += max(0, dp(i, j, -1) - 1)

return ans

花花酱 LeetCode 2087. Minimum Cost Homecoming of a Robot in a Grid

By zxi on November 27, 2021

There is an m x n grid, where (0, 0) is the top-left cell and (m - 1, n - 1) is the bottom-right cell. You are given an integer array startPos where startPos = [start_row, start_col] indicates that initially, a robot is at the cell (start_row, start_col). You are also given an integer array homePos where homePos = [home_row, home_col] indicates that its home is at the cell (home_row, home_col).

The robot needs to go to its home. It can move one cell in four directions: left, right, up, or down, and it can not move outside the boundary. Every move incurs some cost. You are further given two 0-indexed integer arrays: rowCosts of length m and colCosts of length n.

If the robot moves up or down into a cell whose row is r, then this move costs rowCosts[r].
If the robot moves left or right into a cell whose column is c, then this move costs colCosts[c].

Return the minimum total cost for this robot to return home.

Example 1:

Input: startPos = [1, 0], homePos = [2, 3], rowCosts = [5, 4, 3], colCosts = [8, 2, 6, 7]
Output: 18
Explanation: One optimal path is that:
Starting from (1, 0)
-> It goes down to (2, 0). This move costs rowCosts[2] = 3.
-> It goes right to (2, 1). This move costs colCosts[1] = 2.
-> It goes right to (2, 2). This move costs colCosts[2] = 6.
-> It goes right to (2, 3). This move costs colCosts[3] = 7.
The total cost is 3 + 2 + 6 + 7 = 18

Example 2:

Input: startPos = [0, 0], homePos = [0, 0], rowCosts = [5], colCosts = [26]
Output: 0
Explanation: The robot is already at its home. Since no moves occur, the total cost is 0.

Constraints:

m == rowCosts.length
n == colCosts.length
1 <= m, n <= 10⁵
0 <= rowCosts[r], colCosts[c] <= 10⁴
startPos.length == 2
homePos.length == 2
0 <= start_row, home_row < m
0 <= start_col, home_col < n

Solution: Manhattan distance

Move directly to the goal, no back and forth. Cost will be the same no matter which path you choose.

ans = sum(rowCosts[y1+1~y2]) + sum(colCosts[x1+1~x2])

Time complexity: O(m + n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int minCost(vector<int>& startPos, vector<int>& homePos, vector<int>& rowCosts, vector<int>& colCosts) {

int dx = homePos[1] > startPos[1] ? 1 : (homePos[1] < startPos[1] ? -1 : 0);

int dy = homePos[0] > startPos[0] ? 1 : (homePos[0] < startPos[0] ? -1 : 0);

int ans = 0;

while (homePos[1] != startPos[1]) ans += colCosts[startPos[1] += dx];

while (homePos[0] != startPos[0]) ans += rowCosts[startPos[0] += dy];

return ans;

}

};

花花酱 LeetCode 2086. Minimum Number of Buckets Required to Collect Rainwater from Houses

By zxi on November 27, 2021

You are given a 0-indexed string street. Each character in street is either 'H' representing a house or '.' representing an empty space.

You can place buckets on the empty spaces to collect rainwater that falls from the adjacent houses. The rainwater from a house at index i is collected if a bucket is placed at index i - 1 and/or index i + 1. A single bucket, if placed adjacent to two houses, can collect the rainwater from both houses.

Return the minimum number of buckets needed so that for every house, there is at least one bucket collecting rainwater from it, or -1 if it is impossible.

Example 1:

Input: street = "H..H"
Output: 2
Explanation:
We can put buckets at index 1 and index 2.
"H..H" -> "HBBH" ('B' denotes where a bucket is placed).
The house at index 0 has a bucket to its right, and the house at index 3 has a bucket to its left.
Thus, for every house, there is at least one bucket collecting rainwater from it.

Example 2:

Input: street = ".H.H."
Output: 1
Explanation:
We can put a bucket at index 2.
".H.H." -> ".HBH." ('B' denotes where a bucket is placed).
The house at index 1 has a bucket to its right, and the house at index 3 has a bucket to its left.
Thus, for every house, there is at least one bucket collecting rainwater from it.

Example 3:

Input: street = ".HHH."
Output: -1
Explanation:
There is no empty space to place a bucket to collect the rainwater from the house at index 2.
Thus, it is impossible to collect the rainwater from all the houses.

Example 4:

Input: street = "H"
Output: -1
Explanation:
There is no empty space to place a bucket.
Thus, it is impossible to collect the rainwater from the house.

Example 5:

Input: street = "."

Output: 0

Explanation:

There is no house to collect water from.

Thus, 0 buckets are needed.

Constraints:

1 <= street.length <= 10⁵
street[i] is either'H' or '.'.

Solution: Greedy

Try to put a bucket after a house if possible, otherwise put it before the house, or impossible.

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int minimumBuckets(string street) {

const int n = street.size();

int ans = 0;

for (int i = 0; i < n; ++i)

if (street[i] == 'H')

if (i - 1 >= 0 and street[i - 1] == 'B')

continue;

else if (i + 1 < n and street[i + 1] == '.')

street[i + 1] = 'B', ++ans;

else if (i - 1 >= 0 and street[i - 1] == '.')

street[i - 1] = 'B', ++ans;

else

return -1;

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 114. Flatten Binary Tree to Linked List

Solution 1: Recursion

Python3

Python3

花花酱 LeetCode 109. Convert Sorted List to Binary Search Tree

Solution 1: Recursion w/ Fast + Slow Pointers

C++

花花酱 LeetCode 2088. Count Fertile Pyramids in a Land

Solution: DP

Python

花花酱 LeetCode 2087. Minimum Cost Homecoming of a Robot in a Grid

Solution: Manhattan distance

C++

花花酱 LeetCode 2086. Minimum Number of Buckets Required to Collect Rainwater from Houses

Solution: Greedy

C++