A. The Employee That Worked on the Longest Task (opens new window)

Count the longest task for each worker.

DETAILS

def hardestWorker(self, n: int, logs: List[List[int]]) -> int:
        T = [0] * n
        for i, log in enumerate(logs):
            w, t = log
            if i == 0:
                T[w] = t
            else:
                T[w] = max(T[w], t - logs[i - 1][1])
        ans = max(T)
        for i in range(n):
            if T[i] == ans:
                return i

B. Find The Original Array of Prefix Xor (opens new window)

XOR is self-inverting, commutative and associative:

• a ^ a = 0
• a ^ b = b ^ a
• a ^ b ^ c = a ^ (b ^ c)

DETAILS

def findArray(self, pref: List[int]) -> List[int]:
        ans = [pref[0]]
        for i in range(1, len(pref)):
            ans.append(pref[i] ^ pref[i - 1])
        return ans

C. Using a Robot to Print the Lexicographically Smallest String (opens new window)

String p is actually a stack, we add or remove character by its end.

We can print the last character ch in stack, ONLY WHEN ch is smaller than all the characters in s.

Therefore, we can build a suffix smallest character array suf.

DETAILS

def robotWithString(self, S: str) -> str:
        ans, st, n = "", [], len(S)
        counter = [0] * 26
        for ch in S:
            counter[ord(ch) - ord('a')] += 1
            
        suf = [26] * (n + 1)
        suf[-2] = ord(S[-1]) - ord('a')
        for i in range(n - 2, -1, -1):
            suf[i] = min(suf[i + 1], ord(S[i]) - ord('a'))
        
        for i, ch in enumerate(S):
            pos = ord(ch) - ord('a')
            st.append(pos)
            while st and st[-1] <= suf[i + 1]:
                ans += chr(st[-1] + ord('a'))
                st.pop()
        
        return ans

D. Paths in Matrix Whose Sum Is Divisible by K (opens new window)

3d DP.

DETAILS

def numberOfPaths(self, A: List[List[int]], k: int) -> int:
        m, n, mod = len(A), len(A[0]), 10 ** 9 + 7
        for i in range(m):
            for j in range(n):
                A[i][j] %= k
                
        dp = [[[0] * k for _ in range(n)] for _ in range(m)]
        dp[0][0][A[0][0]] = 1

        for i in range(m):
            for j in range(n):
                if i == 0 and j == 0:
                    continue
                if i > 0:
                    for kk in range(k):
                        dp[i][j][(kk + A[i][j]) % k] += dp[i - 1][j][kk]
                if j > 0:
                    for kk in range(k):
                        dp[i][j][(kk + A[i][j]) % k] += dp[i][j - 1][kk]

        return dp[-1][-1][0] % mod