# June LeetCoding Challenge 2021

## Table of Contents

Some people start their day by doing exercise,
hackers too, but with *coding exercises*.
So I’m decided to join the June LeetCoding Challenge 2021,
for which I will solve a coding question to start my day.

I also want to take the chance to get familiar with a new language. Here I decide to learn a bit TypeScript as I thought it makes JavaScript less ugly. I will be using the Learn X in Y minutes page for TypeScript and for JavaScript as regular syntax references.

## Day 1 & Day 2

I started this blog after the first two days. Not so excited to recall what happened ðŸ˜…

## Day 3: Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts

Question description can be found at this link.

The problem looks quite easy. The maximum area must be the one with maximum horizontal and vertical lengths. So the task is to find both of them. This can be done by sorting the cuts first and compute the diff for every two consecutive cuts. Some care on the starting and ending needs to be taken.

Here is my solution.

function maxArea( h: number, w: number, horizontalCuts: number[], verticalCuts: number[] ): number { function maxDiff(cuts: number[], edge: number): number { // You have to pass the comparison function manually // since JavaScript by default thinks 0 < 10 < 2 😲 cuts.sort((n1, n2) => n1 - n2); cuts.unshift(0); cuts.push(edge) let diffMax: number = 0 for (let i = 0; i < cuts.length - 1; i ++) { let diff: number = cuts[i+1] - cuts[i] if (diff > diffMax) { diffMax = diff } } return diffMax } return (maxDiff(horizontalCuts, h) * maxDiff(verticalCuts, w)) % (1e9 + 7) };

As I use sorting here, which I assume is quick sort, the complexity would be , where and are the number of horizontal and vertical cuts respectively. I think this problem is suitable for stuff like bucket sort, which will improve the complexity to , but I’m too lazy to dig into this.

## Day 4: Open the Lock

Question description can be found at this link.

The problem can be formulated as graph search for which we start with the node `"0000"`

and want to find the shortest path to `target`

.
I in fact misread the problem initially: I though deadends are *per wheel* based, which is not the case.

The solution is straightforward. I simply implement a breath first search to solve it.

function openLock(deadendsArr: string[], target: string): number { // 0 -> 1, 1 -> 2, ..., 8 -> 9, 9 -> 0 function turnUp(wheel: string): string { if (wheel == "9") { return "0"; } else { return (parseInt(wheel) + 1).toString(); } } // 9 -> 8, 8 -> 7, ..., 1 -> 0, 0 -> 9 function turnDown(wheel: string): string { if (wheel == "0") { return "9"; } else { return (parseInt(wheel) - 1).toString(); } } // Find next possible locks function neighbours(lock: string): Set<string> { let ns: Set<string> = new Set(); for (let i = 0; i < lock.length; i++) { let lockUp: Array<string> = lock.split(""); let lockDown: Array<string> = lock.split(""); lockUp[i] = turnUp(lockUp[i]); lockDown[i] = turnDown(lockDown[i]); ns.add(lockUp.join("")); ns.add(lockDown.join("")); } return ns; } // Convert deadends to a set for O(1) check let deadends = new Set(deadendsArr); // Check if the starting lock is dead if (deadends.has("0000")) return -1; // BFS let toVisit = [{lock: "0000", numTurns: 0}]; let toVisitSet = new Set(["0000"]); // for O(1) check let visited = new Set(); while (toVisit.length > 0) { let visiting = toVisit.pop(); // pop from right let lock = visiting.lock; let numTurns = visiting.numTurns; visited.add(lock); if (lock == target) return numTurns; for (let nextLock of neighbours(lock)) { if (!(deadends.has(nextLock) || visited.has(nextLock) || toVisitSet.has(nextLock))) { toVisit.unshift({lock: nextLock, numTurns: numTurns + 1}); // add to left toVisitSet.add(nextLock); } } } // If not found return -1; };

A few thoughts

- I could implement BFS from both sides to make this much faster.
- Handling
`deadends`

while visiting can simplify the code a bit as we don’t need to check`"0000"`

as a special case. - I was giving up writing proper types in the end (for the BFS part) as I was not so sure how to type
`toVisit`

. - Does deconstruction deal with types properly? It seems tricky to me that there is not typed tuple as in Julia to properly handle this.