0%

Weekly Contest 193

Ranking: 2148 / 13794 😭

Q1. 5453. Running Sum of 1d Array

Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]).
Return the running sum of nums.

Equivalent to compute prefix-sum.

1
2
3
4
5
6
class Solution:
def runningSum(self, nums: List[int]) -> List[int]:
rst = [0] * (len(nums)+1)
for i, v in enumerate(nums):
rst[i+1] = rst[i] + v
return rst[1:]

Q2. 5454. Least Number of Unique Integers after K Removals

Given an array of integers arr and an integer k. Find the least number of unique integers after removing exactly k elements.

Start removal from element with least frequency. The will maximum the unique characters we can remove.

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
c = Counter(arr)
rst = len(c)
for i in sorted(c.keys(), key=lambda x: c[x]):
if c[i] > k:
break
else:
k -= c[i]
rst -= 1
return rst

Q3.[FAILED] 5455. Minimum Number of Days to Make m Bouquets

click header to review question

Note

  1. Spent a lot of time to understand the question.
  2. Did not catch the requirement of adjacent flowers at the beginning.

Use binary search to guess answer when

  1. Answer is in a known range.
  2. Easy to determine the correctness of a guess.
  3. Each guess can reduce the range of answer. Most likely, the range looks like [False, False, False, True, True].
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def minDays(self, B: List[int], m: int, k: int) -> int:
def ok(day):
fl, cnt = 0, 0
for d in B:
fl = fl + 1 if day >= d else 0
if fl >= k:
cnt += 1
fl = 0
return cnt >= m

l, r = min(B), max(B)+1
while l < r:
mid = (l+r) // 2
if ok(mid):
r = mid
else:
l = mid + 1
return l if l <= max(B) else -1

Q4. [FAILED] 5456. Kth Ancestor of a Tree Node

You are given a tree with n nodes numbered from 0 to n-1 in the form of a parent array where parent[i] is the parent of node i. The root of the tree is node 0.
Implement the function getKthAncestor(int node, int k) to return the k-th ancestor of the given node. If there is no such ancestor, return -1.
The k-th ancestor of a tree node is the k-th node in the path from that node to the root.

[NEW TECHNIQUE] Binary Lifting

Binary Lifting is a dynamic programming approach where we pre-compute an array memo[1, log(n)][1, n] where memo[i][j] contains 2^i-th ancestor of node j.

Binary Lifting can also be used to solve Lowest Common Ancestor of two nodes in a tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class TreeAncestor:
MAX_HEIGHT = 16
def __init__(self, n: int, parent: List[int]):
A, B = parent, [-1] * len(parent)
self.memo = [A]
for i in range(self.MAX_HEIGHT):
for num in range(len(parent)):
if A[num] != -1:
B[num] = A[A[num]]
A, B = B, [-1] * len(parent)
self.memo.append(A)

def getKthAncestor(self, node: int, k: int) -> int:
for level in range(self.MAX_HEIGHT)[::-1]:
if (1 << level) <= k:
if node == -1: return -1
node = self.memo[level][node]
k -= (1 << level)
return node

Summary

  1. Ready question more carefully. Catch all requirement before coding.
  2. Be more clear on when will binary search can be applied to guess and find answer. Be familiar with this tool.
  3. Learnt new technique - Binary Lifting