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