0%

Weekly Contest 196

Ranking: 133 / 14301 😋😋😋

Q1. 1502. Can Make Arithmetic Progression From Sequence

Given an array of numbers arr. A sequence of numbers is called an arithmetic progression if the difference between any two consecutive elements is the same.

Return true if the array can be rearranged to form an arithmetic progression, otherwise, return false.

Note

Was not clear about the description at the very beginning.
The question is easy after fully understand the description.

1
2
3
4
5
class Solution:
def canMakeArithmeticProgression(self, A: List[int]) -> bool:
A = sorted(A)
dis = A[0] - A[1]
return all(a-b==dis for a, b in zip(A, A[1:]))

Q2. 1503. Last Moment Before All Ants Fall Out of a Plank

We have a wooden plank of the length n units. Some ants are walking on the plank, each ant moves with speed 1 unit per second. Some of the ants move to the left, the other move to the right.

When two ants moving in two different directions meet at some point, they change their directions and continue moving again. Assume changing directions doesn’t take any additional time.

When an ant reaches one end of the plank at a time t, it falls out of the plank imediately.

Given an integer n and two integer arrays left and right, the positions of the ants moving to the left and the right. Return the moment when the last ant(s) fall out of the plank.

Note

Again, spend a while to understand the description.

Key observation

When two ants moving in two different directions meet at some point, they change their directions and continue moving again.

This is a trap. The rule is a redundant, which can be ignore.
Once we understand this point, the answer is very straight forward.
Be careful about the corner case where left or right is empty.

1
2
3
class Solution:
def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:
return max(max(left+[0]), n - min(right+[n]))

Q3. 1504. Count Submatrices With All Ones

Given a rows * columns matrix mat of ones and zeros, return how many submatrices have all ones.

Example 1:

Input: mat =
[[1,0,1],
[1,1,0],
[1,1,0]] .
Output: 13
Explanation:
There are 6 rectangles of side 1x1.
There are 2 rectangles of side 1x2.
There are 3 rectangles of side 2x1.
There is 1 rectangle of side 2x2.
There is 1 rectangle of side 3x1.
Total number of rectangles = 6 + 2 + 3 + 1 + 1 = 13.

Intuition

This looks like a DP problem at first glance.
But I was not able to define a clear state transformation formula.
End up as a greedy solution.

Very similar to 85. Maximal Rectangle

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def numSubmat(self, M: List[List[int]]) -> int:
if not M or not M[0]: return 0
m, n = len(M), len(M[0])
ret, height = 0, [0] * n
for i in range(m):
for j in range(n):
height[j] = 1 + height[j] if M[i][j] else 0
peak = m
for k in range(j, -1, -1):
if height[k] == 0: break
peak = min(height[k], peak)
ret += peak
return ret

Q4. 1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits…

Given a string num representing the digits of a very large integer and an integer k.
You are allowed to swap any two adjacent digits of the integer at most k times.
Return the minimum integer you can obtain also as a string.
E.g. num = “4321”, k = 4 ->>>> “1342”
E.g. Input: num = “100”, k = 1 ->>>>> “010”

Intuition

Key observation

You can move a digit k steps with k time of adjacent swapping.

With that in mind, we start from the most significant digit (left most). Find smallest digit within the range of K and move it the the beginning.

Repeat the above algo and update K until K == 0, we will find the answer.

Naive solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# O(N^2)
class Solution:
def minInteger(self, num: str, k: int) -> str:
num = list(num)
if k >= len(num)**2 / 2: return ''.join(sorted(num))
ready = []
while k > 0 and num:
val = min(num[:k+1])
idx = num.index(val)
if idx == 0:
ready.append(num.pop(0))
continue
num[:idx+1] = num[:idx]
k -= idx
ready.append(val)

return ''.join(ready + num)

Binary Index Tree

Wikipedia: A Fenwick tree or binary indexed tree is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class BIT:
def __init__(self, size):
self.arr = [0] * size

def add(self, x, delta):
while x < len(self.arr):
self.arr[x] += delta
x += self._lowbit(x)

def sum(self, x):
ret = 0
while x:
ret += self.arr[x]
x -= self._lowbit(x)
return ret

def _lowbit(self, x):
return x & (-x)

class Solution:
def minInteger(self, num: str, k: int) -> str:
if k >= len(num)**2 / 2: return ''.join(sorted(num))
ret, digits = '', defaultdict(deque)
for i, c in enumerate(num):
digits[c].append(i)
# Binary Index Tree: Log(N)
bit = BIT(len(num)+10)
for i in range(len(num)): bit.add(i+1, 1)

for _ in range(len(num)):
for c in string.digits:
if digits[c] and bit.sum(digits[c][0]) <= k:
ret += c
bit.add(digits[c][0] + 1, -1)
k -= bit.sum(digits[c].popleft())
break
return ret

Self Balanced Tree in Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from sortedcontainers import SortedList
class Solution:
def minInteger(self, num: str, k: int) -> str:
digits = defaultdict(deque)
for i, c in enumerate(num):
digits[c].append(i)
ret, moved = '', SortedList()
for _ in range(len(num)):
for c in string.digits:
if digits[c]:
idx = digits[c][0]
real_idx = idx - moved.bisect(idx)
if real_idx <= k:
k -= real_idx
ret += c
moved.add(digits[c].popleft())
break
return ret

Summary

  • Binary Index Tree is not that hard to remember and implement.
  • from sortedcontainers import SortedList is the counter part of C++’s multiset in Python