June LeetCoding Challenge 2021

Day 1 & Day 2
Day 3: Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts
Day 4: Open the Lock

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.

Note that I don’t plan to spend more than 45 minutes per day on this so my solution can look harsh.

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 $O(N \log N + M \log M)$ , where $N$ and $M$ 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 $O(N + M)$ , 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. Stuff in deadends are like walls which indicate nodes cannot be visited. 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.

June LeetCoding Challenge 2021

Table of Contents

Day 1 & Day 2

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

Day 4: Open the Lock