Practice #008: Leetcode

Leetcode: 1165. Single-Row Keyboard

Problem Statement

Create a map from letter to position in the keyboard and then compute the distance using it. Time and space complexity is \(O(n)\). 

class Solution:
    def calculateTime(self, keyboard: str, word: str) -> int:
        pos = {}
        for i, c in enumerate(keyboard):
            pos[c] = i
        ans = 0
        cur = 0
        for c in word:
            ans += abs(pos[c] - cur)
            cur = pos[c]
        return ans


assert Solution().calculateTime("abcdefghijklmnopqrstuvwxyz", "cba") == 4
assert Solution().calculateTime("pqrstuvwxyzabcdefghijklmno", "leetcode") == 73

Leetcode: 1161. Maximum Level Sum of a Binary Tree

Problem Statement

Do a Breadth-first search keeping the sum of the number in each level. The following implementation uses a special symbol $ to mark the end of each level which is used to update the answer. Time and space complexity is \(O(n)\). 

from collections import deque

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxLevelSum(self, root: Optional[TreeNode]) -> int:
        q = deque()
        best_sum = root.val
        best_level = 1

        sum = 0
        level = 1
        q.append(root)
        q.append("$")

        while len(q) > 0:
            e = q.popleft()
            if e is None:
                continue
            if e == "$":
                if sum > best_sum:
                    best_sum = sum
                    best_level = level
                if len(q) > 0:
                    q.append("$")
                    sum = 0
                    level += 1
                continue
            sum += e.val
            if e.left is not None:
                q.append(e.left)
            if e.right is not None:
                q.append(e.right)

        return best_level

Leetcode: 975. Odd Even Jump

Problem Statement

Retrospective: Saw that the dp was trivial after knowing the next higher and lower for each position. I wrongly tried to use a heap to keep this value, but failed. Then, I wrote a quadratic algorithm to solve the next higher and lower subproblem, but it didn't pass on time. I remember to tell myself "It seems that I can use a stack to compute this values". I failed to ask myself "Can we pre-process the input in a way to make easy to solve the problem?".

We can divide this problem in three problems: (1) Problem: Next smallest greater or equal integer in unsorted array, (2) Problem: Next greatest smaller or equal integer in unsorted array and (3) count the number of good starting indices. The first two problems are important because they solve the problem to compute the next odd-numbered jump and even-numbered jump respectively. After that solved, we have to solve the following recurrence

\begin{equation*} f(i, t)=\begin{cases} 1, & \mbox{if $i = n-1$ \\ f(g(i), E) & \mbox{if $t = O$ and $g(i) \neq False$} \\ f(e(i), O) & \mbox{if $t = E$ and $e(i) \neq False$} \\ False & \mbox{otherwise}. \end{cases} \end{equation*}

which will be \(True\) if starting from the position \(i\) after doing a \(t\) jump type (\(E\) means even-numbered jump and \(O\) odd-numbered jump), and \(False\) otherwise. The problem space is linear and take constant time to be computed if \(g\) and \(e\) is already solved.

The time complexity for the problem is \(O(n \log n)\) since \(O(n)\) to compute \(f\) is dominated by the times to compute \(g\) and \(e\) which is \(O(n \log n)\). The space complexity is \(O(n)\). 

from typing import List


class Solution:
    def oddEvenJumps(self, arr: List[int]) -> int:
        n = len(arr)
        stack = []
        ojump = [None] * n
        for v, i in sorted(zip(arr, range(n))):
            while len(stack) > 0 and stack[-1] < i:
                ojump[stack.pop()] = i
            stack.append(i)

        stack = []
        ejump = [None] * n
        for v, i in sorted(zip(map(lambda v: -v, arr), range(n))):
            while len(stack) > 0 and stack[-1] < i:
                ejump[stack.pop()] = i
            stack.append(i)

        dp = {(n - 1, "o"): True, (n - 1, "e"): True}
        for i in range(n - 2, -1, -1):
            o = ojump[i]
            dp[(i, "e")] = False if o is None else dp[(o, "o")]
            e = ejump[i]
            dp[(i, "o")] = False if e is None else dp[(e, "e")]

        ans = set()
        for k in dp:
            if k[1] == "e" and dp[k] == True:
                ans.add(k[0])
        return len(ans)


assert Solution().oddEvenJumps([10, 13, 12, 14, 15]) == 2
assert Solution().oddEvenJumps([2, 3, 1, 1, 4]) == 3
assert Solution().oddEvenJumps([5, 1, 3, 4, 2]) == 3