# Matthew Merrill

#### Full Stack Software Developer

Index | Projects | Slides### Table of Contents

# 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];
}
}
```