Matthew Merrill

Full Stack Software Developer

Index | Projects | Slides

LeetCode Weekly Contest 314 #


6200. The Employee That Worked on the Longest Task #

https://leetcode.com/contest/weekly-contest-314/problems/the-employee-that-worked-on-the-longest-task/

For a problem #1, this one took me longer than expected – about a full ten minutes. I was trying to do things quickly and golf-y, but eventually had to cut my time losses and implement it a more straightforward way.

We assume the task 0 is best, then process each of the other logs calculating the duration spent on that task as dur. If dur is longer than our currently known longest duration, we replace our “best so far” and continue. If dur is equal, we also want to replace our “best so far” if the employee id is lower (this is specified in the problem statement.)

from typing import List
class Solution:
    def hardestWorker(self, n: int, logs: List[List[int]]) -> int:

        mx = logs[0][1]
        mxidx = logs[0][0]

        for idx in range(1, len(logs)):
            dur = logs[idx][1] - logs[idx-1][1]
            if dur > mx or (dur == mx and logs[idx][0] < mxidx):
                mx = dur
                mxidx = logs[idx][0]

        return mxidx

6201. Find The Original Array of Prefix Xor #

https://leetcode.com/contest/weekly-contest-314/problems/find-the-original-array-of-prefix-xor/

This problem look daunting at first, but it’s rather simple once you see the trick.

The value at index idx in output pref is the xor of everything arr[0:idx] so get the original value of arr[idx] we can do arr[0:idx] ^ arr[0:(idx-1)] (where arr[a:b] is the xor of everything in that slice.) The second value is pref[idx-1].

from typing import List
class Solution:
  def findArray(self, pref: List[int]) -> List[int]:
    return [pref[0]] + [ pref[idx-1] ^ pref[idx] for idx in range(1, len(pref))]

6202. Using a Robot to Print the Lexicographically Smallest String #

https://leetcode.com/contest/weekly-contest-314/problems/using-a-robot-to-print-the-lexicographically-smallest-string/

I found this problem to be more difficult than problem #4, so skipped it and came back to it after completing #4. It took me 9 submissions to get the answer correct, but did not get any TLE.

My original thinking was:

  • find the smallest char in s. That needs to be emitted first, so grab everything in s up to that char and emit that substring reversed
  • then find the next smallest char

We can do this efficiently by sweeping backwards through s, adding an index to a stack/list/deque when the char at current index is less than (or equal to! but I didn’t realize this until a later submission failed) the previous item added to the stack/list/deque. Then we process the items off the deque backwards, to process the smallest item first, then the next smallest thing that was after that one, etc.

This works for the sample cases, but after submitting found test cases where it does not work. For these, we have to consider using the buffer t to store particularly high characters and not emitting them until the right time while processing later chunks.

This can be done with the while t... loop while we process the chunks. It’s a bit messy so I won’t elaborate, and I’m not fully convinced it’s sound but it passed all the cases and was accepted.

from collections import deque

class Solution:
  def robotWithString(self, s: str) -> str:
    t = ''
    r = ''

    nextchoice = deque([])
    nextchoice.append(len(s)-1)

    idx = len(s)-2
    while idx >= 0:
      if s[idx] <= s[nextchoice[-1]]:
        nextchoice.append(idx)
      idx -= 1

    # print(nextchoice)
    prv = 0
    for idx in reversed(nextchoice):
      while t and t[0] <= s[idx]:
        r += t[0]
        t = t[1:]
        # print(s, r, t)
      t = s[prv:idx][::-1] + t
      r += s[idx]
      prv = idx + 1

    return r + t

6203. Paths in Matrix Whose Sum Is Divisible by K #

https://leetcode.com/contest/weekly-contest-314/problems/paths-in-matrix-whose-sum-is-divisible-by-k/

Reading this question, I recalled a similar problem from an ICPC contest at CSUS asking to count the number of paths going right/down with obstacles on certain tiles.

The solution for that one was to set the # of ways on the target position to 1, and then bubble out from there with bottom-up dynamic programming to “push” the “way” out by adding down/right cell values to current cell value until we’ve processed everywhere. Then, we can just look at the source cell knowing it represents all the ways.

This problem requires a similar approach, but I decided that each tile needs k values – tile t has array of size k where the value with index v on that array represents the number of ways possible to get from t to that target with a path that has value v (done modulus k.)

I used java for the convenient allocation of a 3-dimensional array.

class Solution {

  private static final int MOD = 1_000_000_000 + 7;

  public int numberOfPaths(int[][] grid, int k) {
    int rows = grid.length;
    int cols = grid[0].length;

    int[][][] dp= new int[grid.length][grid[0].length][k];
    dp[rows-1][cols-1][grid[rows-1][cols-1] % k] = 1;

    for (int r = rows-1; r >= 0; r -= 1) {
      for (int c = cols-1; c >= 0; c -= 1) {
        int val = grid[r][c];
        // If we're not at the bottom, add the values for tile below us
        if (r < rows-1) {
          for (int nxtval = 0; nxtval < k; nxtval += 1) {
            int newval = (val + nxtval) % k;
            dp[r][c][newval] += dp[r+1][c][nxtval];
            dp[r][c][newval] %= MOD;
          }
        }
        // If we're not at the right, add the values for tile to right of us
        if (c < cols-1) {
          for (int nxtval = 0; nxtval < k; nxtval += 1) {
            int newval = (val + nxtval) % k;
            dp[r][c][newval] += dp[r][c+1][nxtval];
            dp[r][c][newval] %= MOD;
          }
        }
      }
    }
    return dp[0][0][0];
  }
}

Matthew Merrill 2021
www.mattmerr.com EMail | Keys | LinkedIn | GitHub | Dark Mode Light Mode