https://leetcode.com/contest/weekly-contest-312/problems/sort-the-people/
This problem is rather straightforward. We want to sort names by the heights associated with those names. To do so, we can zip the (name,height) pairs and sort that. To sort by height and not name, we make height the first part of the tuple. The problem wants the names in descending order by height, so slap a reversed on it and pull out the name for each tuple and we’re good to go.
from typing import List
class Solution:
def sortPeople(self, names: List[str], heights: List[int]) -> List[str]:
by_height = zip(heights, names)
return [tup[1] for tup in reversed(sorted(by_height))]
https://leetcode.com/contest/weekly-contest-312/problems/longest-subarray-with-maximum-bitwise-and/
This problem starts to get a little tricky. At first I thought that the subarray
required to be at least of length 2, so I zipped adjacent pairs together, and
took the max bitwise AND of any adjacent-value pair. Call this max_and.
From here, the problem becomes more clear. We can run through the list and find
the max subarray in linear time. Iterate through the list with an index i. If
the value at i is in our subarray, then vals[i] & max_and == max_and.
Therefore, if vals[i] & max_and != max_and, we continue and disregard i. For
all i that could be the start of a subarray, we crawl from i until the end
of the list or until we find a value that breaks the subarray.
Record the length of the longest subarray we’ve seen so far and by the time we have crawled the whole list we must have found the longest subarray.
Reading sample problem 2, it became clear that it was not necessary to have a subarray of at least size 2. With this knowledge, it becomes clear that the max AND of a subarray will be the subarray consisting only of the maximum element.
Instead of finding the max AND-pair we find the max value, and the rest of the
code holds even though we could simplify it by using vals[i] == max_val as our
metric and simplify things significantly.
In order for the code to run in time, whenever we consider a subarray we must
skip i to the end of that subarray before continuing our search. The proof
that this is sound is left as an exercise.
class Solution:
def longestSubarray(self, nums: List[int]) -> int:
max_and = max(nums) #([a & b for a, b in zip(nums[:-1], nums[1:])])
i = 0
longest_run = 1
while i < len(nums):
if (nums[i] & max_and) != max_and:
i += 1
continue
j = i
while j+1 < len(nums) and (nums[j+1] & max_and) == max_and:
j += 1
longest_run = max(longest_run, j - i + 1)
i = j + 1
return longest_run
https://leetcode.com/contest/weekly-contest-312/problems/find-all-good-indices/
For this problem, it should become clear rather quickly that we’ll need to track
whether an index is a good index in sublinear time relative to k. n <= 1e5
and k <= n/2, so a naive check forward/backward will be worst case for
non-increasing list nums roughly 1e5 * 5e4 = 5e9 which is just beyond the
limit of what I usually consider feasible. It might work with some lucky-chosen
optimizations, but I chose to find a better solution.
Can we evaluate an index in O(1)? To do so we’d need to know whether the k
preceding and following values meet our criteria with a lookup. A couple ideas
came to my head:
idx we can check whether the run of sorted
numbers up to idx-1 is at least k long with a constant-time lookup to
validate the preceding values. With some reversing to/fro the logic can be
reused for the following.I chose to go with the “running sorted length” approach because it seemed quite clear in my head. I’m curious whether the sliding window of pairs approach could work. Reader, what do you think?
class Solution:
def goodIndices(self, nums: List[int], k: int) -> List[int]:
def good_run(ls):
gr = []
for idx, v in enumerate(ls):
if idx == 0 or ls[idx-1] < ls[idx]:
gr.append(1)
else:
gr.append(gr[-1] + 1)
return gr
fwd = good_run(nums)
bwd = list(reversed(good_run(list(reversed(nums)))))
return [idx for idx in range(len(nums)) if k <= idx < len(nums) - k and fwd[idx-1] >= k and bwd[idx+1] >= k]
https://leetcode.com/contest/weekly-contest-312/problems/number-of-good-paths/
First reading this question, I considered taking the tree at the root and
counting the number of nodes with value val left or right of the root and
multiplying them. Then maybe we could do this for each node, as each path will
have to go through some node to get from left to right?
I then realized that the DAG they give us is NOT necessarily a binary tree. This means we have to toss that previous approach out entirely and think in the world of graphs.
From here I considered starting from a value val and doing a BFS along
potentially good paths until we find nodes to end a path. We’d do this for each
node with value val, but skipping a node if it has already been found by a
previous node. Maybe we could somehow track the perimeter of the BFS as a set
and maintain the count of particular values we’ve seen?
At this point I mapped out a big DAG in my head with several BFSs partially covering the DAG and had a click where I started seeing the separate perimeters as one big Disjoint Sets (Union-Find) object.
For each value val in sorted order, we do the following:
Connect all the nodes with value val to their neighbors <= them. Doing this
with a union operation meets we’ll merge all perimeters of potential good-ness
we’ve found so far into fewer, larger perimeters.
After this step, we know that all nodes of value val belong to the same set as
all nodes they can reach with a good path. We count the number of nodes in each
set by counting the number of times we see the same representative, and do some
math to calculate the number of good paths given the number of nodes in a set.
Summing the number of good paths as we go, by the end we have found them all.
from collections import defaultdict, Counter
class DS:
def __init__(self):
self.parent = defaultdict(lambda: None)
self.rank = defaultdict(int)
# self.count_by_val = defaultdict(lambda x: defaultdict(int, {x: 1}))
def __contains__(self, x):
return x in self.parent
def find(self, x):
if x not in self.parent:
return x
p = self.find(self.parent[x])
self.parent[x] = p
return p
def union(self, a, b):
pa = self.find(a)
pb = self.find(b)
if pa == pb:
return
if self.rank[pa] > self.rank[pb]:
self.parent[pb] = pa
# for k, v in self.count_by_val[pa].items():
# self.count_by_val[pb][k] += v
elif self.rank[pb] < self.rank[pa]:
self.parent[pa] = pb
# for k, v in self.count_by_val[pb].items():
# self.count_by_val[pa][k] += v
else:
self.parent[pb] = pa
self.rank[pa] += 1
# for k, v in self.count_by_val[pa].items():
# self.count_by_val[pb][k] += v
class Solution:
def numberOfGoodPaths(self, vals: List[int], edges: List[List[int]]) -> int:
out_by_idx = defaultdict(list)
for a, b in edges:
out_by_idx[a].append(b)
out_by_idx[b].append(a)
idx_by_val = defaultdict(list)
for idx, val in enumerate(vals):
idx_by_val[val].append(idx)
sorted_vals = sorted(idx_by_val.keys())
ds = DS()
good_paths = len(vals)
for val in sorted_vals:
idx_with_val = idx_by_val[val]
for idx in idx_with_val:
for nxt in out_by_idx[idx]:
if vals[nxt] <= val:
ds.union(idx, nxt)
rep_counts = Counter([ds.find(idx) for idx in idx_with_val])
for v in rep_counts.values():
good_paths += v * (v-1) // 2
# print(val, idx_with_val, rep_counts, good_paths)
return good_paths