Recently, I haven't been solving problems for a long time due to illness. This morning, I started a Leetcode weekly contest and decided to write a solution. I was in decent shape this morning. By the way, I will participate in the weekly contests every week from now on and strive to write solutions.
Leetcode 1341. The K Weakest Rows in a Matrix#
Description:
Given a m * n matrix mat of ones (representing soldiers) and zeros (representing civilians), return the indexes of the k weakest rows in the matrix ordered from the weakest to the strongest.
A row i is weaker than row j if the number of soldiers in row i is less than the number of soldiers in row j, or they have the same number of soldiers but i is less than j. Soldiers always stand in the frontier of a row, that is, always ones may appear first and then zeros.
Example 1:
Input: mat =
[[1,1,0,0,0],
[1,1,1,1,0],
[1,0,0,0,0],
[1,1,0,0,0],
[1,1,1,1,1]],
k = 3
Output: [2,0,3]
Explanation:
The number of soldiers for each row is:
row 0 -> 2
row 1 -> 4
row 2 -> 1
row 3 -> 2
row 4 -> 5
Rows ordered from the weakest to the strongest are [2,0,3,1,4]
The problem is quite simple; it actually involves binary processing, and in Python, a brute force approach works wonders.
from typing import List
class Solution:
def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
if not mat:
return []
number = []
for i in range(len(mat)):
number.append((int("".join([str(x) for x in mat[i]]), 2), i))
number.sort()
return [x for _, x in number[0:k]]
1342. Reduce Array Size to The Half#
Description:
Given an array arr. You can choose a set of integers and remove all the occurrences of these integers in the array.
Return the minimum size of the set so that at least half of the integers of the array are removed.
Input: arr = [3,3,3,3,5,5,5,2,2,7]
Output: 2
Explanation: Choosing {3,7} will make the new array [5,5,5,2,2] which has size 5 (i.e equal to half of the size of the old array).
Possible sets of size 2 are {3,5},{3,2},{5,2}.
Choosing set {2,7} is not possible as it will make the new array [3,3,3,3,5,5,5] which has size greater than half of the size of the old array.
This problem is also quite simple. Given an array, you need to choose a set of numbers to remove, ensuring that the size of the remaining array is less than or equal to half of the original size. The goal is to find the minimum number of numbers needed to achieve this.
Using a hash table, the O(N) approach is as follows:
from typing import List
class Solution:
def minSetSize(self, arr: List[int]) -> int:
if not arr:
return 0
counter = {}
for i in arr:
counter[i] = counter.setdefault(i, 0) + 1
counter = {k: v for k, v in sorted(counter.items(), key=lambda item: item[1], reverse=True)}
total_count = 0
result_count = 0
for i, count in counter.items():
total_count += count
result_count += 1
if total_count >= len(arr) / 2:
break
return result_count
1343. Maximum Product of Splitted Binary Tree#
Description:
Given a binary tree root. Split the binary tree into two subtrees by removing 1 edge such that the product of the sums of the subtrees are maximized.
Since the answer may be too large, return it modulo 10^9 + 7.
Example 1:
Input: root = [1,2,3,4,5,6]
Output: 110
Explanation: Remove the red edge and get 2 binary trees with sum 11 and 10. Their product is 110 (11*10)
This problem is also quite simple. Given a binary tree with values, you need to remove an edge to split it into two new binary trees and find the maximum product of their sums.
Initially, many people might be intimidated by this problem, but it essentially involves traversing a binary tree. Regardless of whether it's a pre-order, in-order, or post-order traversal, you first traverse the binary tree to calculate the total sum of the node values, as well as the sums of the left and right subtrees.
Then, traverse again to calculate result=max((total_sum-left_sum)*left_sum),(total_sum-right_sum)*right_sum),result) for a brute force solution.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def maxProduct(self, root: TreeNode) -> int:
total_sum = self.sum_node(root)
result = 0
stack = []
node = root
while node or stack:
while node:
stack.append(node)
result = max(result, ((total_sum - node.left_sum) * node.left_sum))
result = max(result, ((total_sum - node.right_sum) * node.right_sum))
node = node.left
node = stack.pop()
node = node.right
if node:
result = max(result, ((total_sum - node.right_sum) * node.right_sum))
result = max(result, ((total_sum - node.left_sum) * node.left_sum))
return result % (10 ** 9 + 7)
def sum_node(self, root: TreeNode) -> int:
if not root:
return 0
left_sum = self.sum_node(root.left)
right_sum = self.sum_node(root.right)
root.left_sum = left_sum
root.right_sum = right_sum
return left_sum + right_sum + root.val
By the way, the type hinting in this code is somewhat problematic; I modified it after the competition.
from typing import Optional, Tuple, List
class TreeNode:
val: int
left: Optional["TreeNode"]
right: Optional["TreeNode"]
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class TreeNodeWithSum:
val: int
left: Optional["TreeNodeWithSum"]
right: Optional["TreeNodeWithSum"]
left_sum: int
right_sum: int
def __init__(
self,
x: int,
left: Optional["TreeNodeWithSum"],
right: Optional["TreeNodeWithSum"],
left_sum: int,
right_sum: int,
):
self.val = x
self.left = left
self.right = right
self.left_sum = left_sum
self.right_sum = right_sum
class Solution:
def maxProduct(self, root: TreeNode) -> int:
total_sum, new_root = self.sum_node(root)
result = 0
stack: List[TreeNodeWithSum] = []
node = new_root
while node or stack:
while node:
stack.append(node)
result = max(result, ((total_sum - node.left_sum) * node.left_sum))
result = max(result, ((total_sum - node.right_sum) * node.right_sum))
node = node.left
node = stack.pop()
node = node.right
if node:
result = max(result, ((total_sum - node.right_sum) * node.right_sum))
result = max(result, ((total_sum - node.left_sum) * node.left_sum))
return result % (10 ** 9 + 7)
def sum_node(
self, root: Optional[TreeNode]
) -> Tuple[int, Optional[TreeNodeWithSum]]:
if not root:
return 0, None
left_sum, new_left_node = self.sum_node(root.left)
right_sum, new_right_node = self.sum_node(root.right)
return (
left_sum + right_sum + root.val,
TreeNodeWithSum(
root.val, new_left_node, new_right_node, left_sum, right_sum
),
)
By the way, this problem requires taking modulo 10^9+7 due to large data, and I forgot to take the modulo, resulting in two wrong answers and penalties. I really need to improve...
1344. Jump Game V#
Description:
Given an array of integers arr and an integer d. In one step you can jump from index i to index:
i + x where: i + x < arr.length and 0 < x <= d.
i - x where: i - x >= 0 and 0 < x <= d.
In addition, you can only jump from index i to index j if arr[i] > arr[j] and arr[i] > arr[k] for all indices k between i and j (More formally min(i, j) < k < max(i, j)).
You can choose any index of the array and start jumping. Return the maximum number of indices you can visit.
Notice that you cannot jump outside of the array at any time.
Input: arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2
Output: 4
Explanation: You can start at index 10. You can jump 10 --> 8 --> 6 --> 7 as shown.
Note that if you start at index 6 you can only jump to index 7. You cannot jump to index 5 because 13 > 9. You cannot jump to index 4 because index 5 is between index 4 and 6 and 13 > 9.
Similarly, you cannot jump from index 3 to index 2 or index 1.
The problem states that you have an array with several values, and you can start jumping from any position. You can only jump one step at a time, and you must satisfy the following rules: assuming you jump from index i, the range of each jump is x, and you must satisfy:
-
i+x < arr.length and 0<x<=d
-
i-x >=0 and 0<x<=d
Additionally, if you jump from i to j, you must ensure that arr[i]>arr[j] and every element between i and j satisfies arr[j]<x<arr[i]. The goal is to find the maximum number of elements you can jump to.
Initially, I thought this problem could be solved with a two-headed DP approach, but I found it tedious to write. However, after the competition, I realized that it can actually be solved with a single DP approach. Since we can only jump from high to low, we can sort the elements first and then iterate through them. The formula can be expressed as dp[i]=max(dp[i]+dp[j]+1) where j is the index value reachable from i. The DP part has a complexity of O(DN), but since sorting is required beforehand, the overall time complexity is O(logN+DN).
from typing import List
class Solution:
def maxJumps(self, arr: List[int], d: int) -> int:
length = len(arr)
dp = [1] * length
for a, i in sorted([a, i] for i, a in enumerate(arr)):
for di in [-1, 1]:
for j in range(i + di, i + d * di + di, di):
if not (0 <= j < length and arr[j] < arr[i]):
break
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
Summary#
I haven't solved problems for a long time, so I'm a bit rusty. I spent time on the first few sign-in questions and made some basic mistakes. Therefore, I must stick to solving problems in the future. By the way, I felt that the problems in this week's contest were quite simple, as if they were backup problems after a leak. That's it for now; I will continue to rest and recover from my illness.