https://leetcode.com/contest/weekly-contest-520/
I’ve been joining for the contests again with a little regularity. This was my first all-cleared in a while! I think the problems were a bit on the easier side compared to other recent contests but there were certainly some edge cases that bit me.
https://leetcode.com/problems/number-of-intersecting-interval-pairs-i/description/
intervals.length <= 100 makes this fairly trivial, a brute force worked just fine.
Remembering the right way to check for interval intersections took a fair bit of time. A trick to remember this is that both must start before the other has finished, if there is to be any intersection… helped me. 🤷🏻♂️
class Solution:
def countIntersectingIntervals(self, intervals: list[list[int]]) -> int:
# a[0] a[1]
# b[0] b[1]
#
#
# a[0] a[1]
# b[0] b[1]
#
#
# a[0] a[1]
# b[0] b[1]
#
#
# a[0] a[1]
# b[0] b[1]
#
#
# a[0] a[1]
# b[0] b[1]
#
#
# a[0] a[1]
# b[0] b[1]
#
def isects(a, b) -> bool:
# Do both start before the other finishes?
return a[0] <= b[1] and b[0] <= a[1]
# reminder: sum of bools -> count where True
return sum(
isects(intervals[a], intervals[b])
for a in range(len(intervals))
for b in range(a+1, len(intervals)) )
https://leetcode.com/problems/number-of-intersecting-interval-pairs-ii/description/
I wasted a submission here checking that brute doesn’t work, I probably should have just assumed.
I feel a bit lucky that I’ve done some similar sliding window problems lately, so I was able to quickly wrap my head around “keep a heap and slide the window”, utilizing a structure that has worked pretty well:
window = ... # structure that can quickly surface the most "rejectable" thing
for item of list:
# reject undesired items from the window
while window is not empty and window has rejectable item:
reject from window
# at this point, each item in window represents a "starting point"
# to match the current item's "finishing point"
add size of window to # possibilities
add item to window
class Solution:
def countIntersectingIntervals(self, intervals: list[list[int]]) -> int:
def isects(a, b): return a[0] <= b[1] and b[0] <= a[1]
# sliding window: slide over intervals sorted by starts
# keep "finishing times" of still-potential-collisions in heap
h = []
t = 0
for i_st, i_fn in sorted(intervals):
while h and i_st > h[0]:
heapq.heappop(h)
t += len(h)
heapq.heappush(h, i_fn)
return t
https://leetcode.com/problems/maximum-pulse-value-after-one-subarray-rotation/description/
For this problem, I didn’t compute the number of possibilities because I quickly identified an opportunity for reusing work dynamically, but for the sake of exercise:
There are two possibilities:
There is only 1 way to do the first case, and for the second… how many ways can we choose:
for the window from the array? N choose 2 / C(N, 2) which is P(N, 2)/2! which is N * (N - 1) / 2, or roughly N**2, giving us about 10**10 possible paths to follow in the worst case. A bit more than we can chew.
For my dynamic approach, I made a series of functions to represent a series of subproblems. It’s easier to explain working backwards:
h(idx) - Compute the best pulse value, starting from idx, assuming we have already used up our sliding window.g(idx) - Compute the best pulse value, starting from idx, assuming that idx is within the sliding window.f(idx) - Compute the best pulse value, starting from idx, assuming that idx is before the sliding window.If we have these helpers, the answer is trivially f(0).
These helpers can be defined in terms of each other, but there’s an edge case I didn’t see until submitting – a sliding window of size 1 doesn’t actually flip the polarity of its index. Furthermore, if we slide an even number of elements they flip quite predictably but with an odd number of elements the first element doesn’t flip.
abc = +a -b +c
+-+
bca = +a +b -c
+-+ ^ a didn't change because odd size of rotate!
To account for this, I split g into two functions:
ge(idx) - we’re in a sliding subarray, and the number of remaining elements in the sliding subarray will be even. (possibly zero!)go(idx) - we’re in a sliding subarray, and the number of remaining elements in the sliding subarray will be odd. (which implies this is not the end!)Slap @cache on these functions and we only have to compute each of the functions once for each possible idx. Four functions times N elements yields O(N).
class Solution:
def maxValue(self, nums: List[int]) -> int:
@cache
def f(i):
if i == len(nums):
return 0
p = (-1) ** (i % 2)
return max(
+p * nums[i] + f(i+1),
# if even run after here, sign doesn't actually flip
+p * nums[i] + ge(i+1),
# if odd run after here, sign does actually flip
-p * nums[i] + go(i+1),
)
@cache
# g, in a run, with even # spaces in the run afterward
def ge(i):
if i == len(nums):
return 0
p = (-1) ** (i % 2)
return max(
# keep flipping, swap parity of ge/go
-p * nums[i] + go(i+1),
# end here, 0 is a possible even run
+p * nums[i] + h(i+1),
)
@cache
# g, in a run, with odd # spaces in the run afterward
def go(i):
# cant have an odd run of nothing
if i == len(nums):
return -inf
p = (-1) ** (i % 2)
return -p * nums[i] + ge(i+1)
@cache
def h(i):
if i == len(nums):
return 0
p = (-1) ** (i % 2)
return +p * nums[i] + h(i+1)
return f(0)
https://leetcode.com/problems/lexicographically-largest-power-array/description/
This question is marked hard, but it feels on the softer side to me. It’s pretty apparent what you have to do: just greedily sort the array, and measure the power after! Certainly easier said than done.
At first I tried using radix sort (sorted by lowest bit, then up to highest) to sort with highest precedence in the higher bits, thinking I could adapt with a bitmask of the considered bits, but hit a few snags. Then I considered sorting by highest bit first, then keeping a bitmask of which bits are in use, as elements that have their highest bit not in the mask should be discarded to the end, but…
Then I realized that the prefixes do not all end in the same place. After the first partition we will have two groups that can be freely rearranged, but we can’t move between the groups. The key realization from here was that when we consider the next bit, we should partition again as much as possible on a prefix of these groups – and if a group gets split then we split it in our representation.
It’s tricky to visualize in raw markdown, and I’m sure others have better writeups for this approach, but here’s my implementation:
class Solution:
def largestPower(self, nums: list[int]) -> list[int]:
# "working set" of groups:
# nums partitioned into runs that can be rearranged
# without invalidating the higher-precedence bits
w = [nums]
for i in range(15):
# sweep from bit 1<<14 to 1
bit = 1 << (14 - i)
for g in range(len(w)):
group = w[g]
# buckets = partition members of this group into:
# [
# [], <- are 0 at the selected bit position
# [], <- are 1 at the selected bit position
# ]
buckets = [[], []]
for i in group:
buckets[(i & bit) > 0].append(i)
if buckets[1] and not buckets[0]:
continue
if buckets[0] and not buckets[1]:
break
w = w[:g] + [buckets[1], buckets[0]] + w[g+1:]
break
# I realized that this could be computed as part of the
# partitioning process, but I already had this implemented
# from a previous, failed approach so just kept it like this.
def power(a):
o = []
for i in range(15):
b = 1 << (14 - i)
j = 0
while j < len(a) and a[j] & b > 0:
j += 1
o.append(j)
return o
return power(list(chain.from_iterable(w)))