# Matthew Merrill

#### Full Stack Software Developer

Index | Projects | Slides### Table of Contents

# LeetCode Weekly Contest 312 #

## Sort the People #

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))]
```

## Longest Subarray With Maximum Bitwise AND #

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
```

## Find All Good Indices #

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:

- A sliding window where we count the adjacent pairs that meet our criteria. We can increment/decrement depending on the values that come in/out and build a list for whether an index met the criteria going forward, and then repeat the process with the list reversed. Then AND the two lists to know if an index is a good index.
- Build a cumulative list of how many items before it/including it represent a
sorted index. Then, for an index
`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]
```

## Number of Good Paths #

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
```