0%

Biweekly Contest 28

Ranking: 678 / 8571

Q1. 1475. Final Prices With a Special Discount in a Shop

Given the array prices where prices[i] is the price of the ith item in a shop. There is a special discount for items in the shop, if you buy the ith item, then you will receive a discount equivalent to prices[j] where j is the minimum index such that j > i and prices[j] <= prices[i], otherwise, you will not receive any discount at all.
Return an array where the ith element is the final price you will pay for the ith item of the shop considering the special discount.

Solved it by using brute force in contest. O(N^2)

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def finalPrices(self, prices: List[int]) -> List[int]:
rst = []
for i, price in enumerate(prices):
for j in range(i+1, len(prices)):
if prices[j] <= price:
rst.append(price-prices[j])
break
else:
rst.append(price)
return rst

Intuition

  1. Subtract each value by next smaller number
  2. Equivalent to subtract each value from all its previous greater number
  3. Monotonic stack !!!
1
2
3
4
5
6
7
8
9
class Solution:
def finalPrices(self, prices: List[int]) -> List[int]:
# Next smaller num
stack = []
for i, v in enumerate(prices):
while stack and prices[stack[-1]] >= v:
prices[stack.pop()] -= v
stack.append(i)
return prices

Q2. 1476. Subrectangle Queries

Implement the class SubrectangleQueries which receives a rows x cols rectangle as a matrix of integers in the constructor and supports two methods:

  1. updateSubrectangle(int row1, int col1, int row2, int col2, int newValue)
    Updates all values with newValue in the subrectangle whose upper left coordinate is (row1,col1) and bottom right coordinate is (row2,col2).
  2. getValue(int row, int col)
    Returns the current value of the coordinate (row,col) from the rectangle.

Solved it by using brute force in contest.

1
2
3
4
5
6
7
8
9
10
11
class SubrectangleQueries:

def __init__(self, rectangle: List[List[int]]):
self.M = rectangle

def updateSubrectangle(self, row1: int, col1: int, row2: int, col2: int, newValue: int) -> None:
for i in range(row1, row2+1):
self.M[i][col1:col2+1] = [newValue] * (col2-col1+1)

def getValue(self, row: int, col: int) -> int:
return self.M[row][col]

Intuition

  1. Value updates -> Snapshot search
  2. Share the same idea with 1146. Snapshot Array
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class SubrectangleQueries:

def __init__(self, rectangle: List[List[int]]):
self.M = copy.deepcopy(rectangle)
self.snapshot = []

def updateSubrectangle(self, row1: int, col1: int, row2: int, col2: int, newValue: int) -> None:
self.snapshot.append((row1, col1, row2, col2, newValue))

def getValue(self, row: int, col: int) -> int:
for snapshot in self.snapshot[::-1]:
row1, col1, row2, col2, newValue = snapshot
if row1 <= row <= row2 and col1 <= col <= col2:
return newValue
return self.M[row][col]

Q3. 1477. Find Two Non-overlapping Sub-arrays Each With Target Sum

Given an array of integers arr and an integer target.
You have to find two non-overlapping sub-arrays of arr each with sum equal target. There can be multiple answers so you have to find an answer where the sum of the lengths of the two sub-arrays is minimum.
Return the minimum sum of the lengths of the two required sub-arrays, or return -1 if you cannot find such two sub-arrays.

Intuition

  1. Easy to find the shortest subarray with target sum
  2. Iterate through each index and find the smallest length of valid subarray from left and right side
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
class Solution:
def minSumOfLengths(self, arr: List[int], target: int) -> int:
if len(arr) < 2: return -1
len_l, len_r = [math.inf] * len(arr), [math.inf] * len(arr)
# left
l, r, cur_sum, min_len = 0, 0, 0, math.inf
while r < len(arr):
cur_sum += arr[r]
r += 1
while cur_sum > target:
cur_sum -= arr[l]
l += 1
if cur_sum == target:
min_len = min(min_len, r-l)
len_l[r-1] = min_len
# right
l, r, cur_sum, min_len = len(arr)-1, len(arr)-1, 0, math.inf
while l >= 0:
cur_sum += arr[l]
l -= 1
while cur_sum > target:
cur_sum -= arr[r]
r -= 1
if cur_sum == target:
min_len = min(min_len, r-l)
len_r[l] = min_len
rst = min(len_l[i]+len_r[i] for i in range(0, len(arr)-1))
return rst if rst != math.inf else -1

Cleaner code

Add some DP thinking here.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def minSumOfLengths(self, arr: List[int], target: int) -> int:
prefix = {0: -1}
best, bests, rst = math.inf, [math.inf] * len(arr), math.inf
cur = 0
for i, v in enumerate(arr):
cur += v
if cur - target in prefix:
begin = prefix[cur-target]
if begin > -1:
rst = min(rst, i-begin + bests[begin])
best = min(best, i-begin)
bests[i] = best
prefix[cur] = i
return rst if rst != math.inf else -1

Q4. [FAILED] 1478. Allocate Mailboxes

Directly heading to 3D DP during contest which end up as Time Limit Exceeded.

3D DP -> TLE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def minDistance(self, H: List[int], k: int) -> int:
def solve_it(l, r):
idx = H[(l+r)//2]
return sum(abs(H[i]-idx) for i in range(l, r))
if k >= len(H): return 0
H = sorted(H)
import functools
@functools.lru_cache(None)
def dp(l, r, box): # return cost
if l >= r-1: return 0
if box == 1: return solve_it(l, r)
rst = math.inf
for i in range(1, box):
for j in range(l+1, r):
cost = dp(l, j, i) + dp(j, r, box-i)
rst = min(rst, cost)
return rst
return dp(0, len(H), k)

2D DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def minDistance(self, H: List[int], k: int) -> int:
import functools
@functools.lru_cache(None)
def solve_it(l, r):
idx = H[(l+r)//2]
return sum(abs(H[i]-idx) for i in range(l, r))
if k >= len(H): return 0
H = sorted(H)
import functools
@functools.lru_cache(None)
def dp(r, box): # return cost
if r <= 0: return 0
if box == 1: return solve_it(0, r)
return min(dp(i, box-1) + solve_it(i, r) for i in range(r))
return dp(len(H), k)

Summary

  1. Try monotonic stack / queue when its related to next/prev greater/smaller element.
  2. Try to record less status when a higher dimension DP is too slow.