DEV Community: Minh Le

200. Number of Islands

Minh Le — Mon, 11 Mar 2024 22:07:16 +0000

PROBLEM

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

REASONING

Suppose that we are given this grid:

grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]

Let's draw a diagram of the grid:

The gray cells are land. I give them numbered labels to easily to make reference to in the explanation. In the code, they are referenced to by the row and column they are in. I defined a Cell interface for this particular purpose:

interface Cell {
    row: number;
    col: number;
}

My initial approach was, first, use an array to store all the land-cells, then use union-find algorithm to group all the neighboring cells together into 1 category, then count and return the number of category.

Let's sketch out the plan:

Create an array cells, then go over all cells of the grid, when encounter a cell whose value is "1", add it to cells. The code should look like this:

     const cells:Cell[] = [];
     
     for(let r = 0; r < grid.length; r++){
        for(let c = 0; c < grid[r].length; c++){
           if(grid[r][c] === "1")
               cells.push({
                  row: r,
                  col: c
               });
            }
     }

After step 1, the array cells should look like this:

Create a union-find class that encompasses the union-find algorithm:

class UF {

    private roots:number[];    

    private counts:number[];

    private numCats:number;



    constructor(size:length) {
        this.roots = new Array(size).fill(0).map((o,i) => o + i);
        this.counts = new Array(size).fill(1);
        this.numCats = size;
    }


    union(i:number, j:number) {
        const rootI = this.findRoot(i), rootJ = this.findRoot(j);

        if(rootI === rootJ) return;

        if(this.counts[rootI] > this.counts[rootJ]){
            this.roots[rootJ] = rootI;
        }
        else {
            this.roots[rootI] = rootJ;
        }

        const totalCounts = this.counts[rootI] + this.counts[rootJ];
        this.counts[rootI] = totalCounts;
        this.counts[rootJ] = totalCounts;
        
        this.numCats--;
    }



    getNumCats():number {
        return this.numCats;
    }



    private findRoot(i:number) {
        if(this.roots[i] === i) return i;

        this.roots[i] = this.findRoot(this.roots[i]);

        return this.roots[i];
    }
}

This is the typical way to implement a union-find class, so I won't spend too much time on that. If you want to learn more, you can read about it on leetcode or geeksforgeeks

For each element in the array cells, pair them with each of all other elements in the array cells. If they are neighbor, use union-find to group them into 1 category. The code should look like this:

const uF = new UF();

for(let i = 0; i < cells.length; i++){
    for(let j = 0; j < cells.length - 1; j++){
        if(//cells[i] and cells[j] are neighbors){
            uF.union(i,j);
        }
    }
}

Now, all the cells in cells are grouped into categories like this:

Our remained job now is just return the number of categories.

However, for this problem, I made a small modification. I moved the array cells to the union-find class then add a new method add to the class.

class UF {
    private cells:Cell[];
    // the rest of the variables

   add(cell:Cell) {}

   // the rest of the class
}

What add does is to get a cell, put it into the array cells, then go over all of the cells that are already in cells to check if each of them should be in the same category with the new cell. If it is, union them together. So, the function add should look like this:

 add(cell:Cell) {
        // push cell to cells
        this.cells.push(cell);
        
        // now we have 1 more new category, which is the one that has only 1 newly added cell.
        this.numCats++;

        // ... and this new category only has 1 element, which is the newly added cell
        this.counts.push(1);
        
        // ... the root of this category is its only element.
        this.roots.push(this.roots.length);


        // get the index of the new cell on the array cells
        const newCellI = this.cells.length - 1;


        // go over each element that is already in the array cells
        for(let i = 0; i < newCellI; i++) {

            if(// this.cells[newCellI] and this.cells[i] should be in the same category) {
                // union them!
                this.union(newCellI, i);

            }

        }

    }

Notice the condition inside the for loop:

for(let i = 0; i < newCellI; i++) {

    if(// this.cells[newCellI] and this.cells[i] should be in the same category) {
        // union them!
        this.union(newCellI, i);

    }

}

To check if this.cells[newCellI] and this.cells[i] should be in the same category, we need to know if they are neighboring each other. To check if they're neighboring each other, we need to know their coordinates in the grid, the information that is not available in the UF class. So, why don't we just delegate the checking to the main function, which is the place where the coordinates information available?

We can do that by define the checking function inside the main function numIslands:

function numIslands(grid: string[][]): number {

    const isNeighbors = (cell1: Cell, cell2:Cell):boolean => {

        const {row:iRow, col:iCol} = cell1;
        const {row:jRow, col:jCol} = cell2;

        if((iCol === jCol && Math.abs(iRow - jRow) === 1) 
            ||  (iRow === jRow && Math.abs(iCol - jCol) === 1)){
                return true;
            }
            

        return false;

    }

    // the rest of the function

};

Then, when we instantiate the union-find class, we pass the isNeighbors function to its constructor:

    const uF = new UF(isNeighbors);

Then, in the UF's constructor, we assign it to the private checking method:

class UF {

    private roots:number[] = [];    

    private counts:number[] = [];

    private numCats:number = 0;

    private cells:Cell[] = [];


    private shouldUnion: (c1:Cell, c2:Cell) => boolean;

    constructor(shouldUnion:(c1:Cell, c2:Cell) => boolean) {
        this.shouldUnion = shouldUnion;
    }
   
       // ... the rest of the class
   }

Notice that we don't need to set up roots, counts, numCats inside the constructor anymore because at the beginning, we have 0 element. We will add them one by one and update those accordingly inside the function add.

So, my final code looks like this:

interface Cell {

    row: number;

    col: number;

}



function numIslands(grid: string[][]): number {

    const isNeighbors = (cell1: Cell, cell2: Cell): boolean => {

        const { row: iRow, col: iCol } = cell1;

        const { row: jRow, col: jCol } = cell2;



        if ((iCol === jCol && Math.abs(iRow - jRow) === 1) || (iRow === jRow && Math.abs(iCol - jCol) === 1))

            return true;



        return false;

    }



    const uF = new UF(isNeighbors);



    for (let r = 0; r < grid.length; r++) {

        for (let c = 0; c < grid[r].length; c++) {

            if (grid[r][c] === "1")

                uF.add({

                    row: r,

                    col: c

                });

        }

    }



    return uF.getNumCats();



};



class UF {

    private roots: number[] = [];

    private counts: number[] = [];

    private numCats: number = 0;

    private cells: Cell[] = [];



    private shouldUnion: (c1: Cell, c2: Cell) => boolean;



    constructor(shouldUnion: (c1: Cell, c2: Cell) => boolean) {

        this.shouldUnion = shouldUnion;

    }




    add(cell: Cell) {

        this.cells.push(cell);

        this.numCats++;

        this.counts.push(1);

        this.roots.push(this.roots.length);



        const newCellI = this.cells.length - 1;



        for (let i = 0; i < newCellI; i++) {

            if (this.shouldUnion(this.cells[newCellI], this.cells[i])) {

                this.union(newCellI, i);

            }

        }

    }



    union(i: number, j: number) {

        const rootI = this.findRoot(i), rootJ = this.findRoot(j);



        if (rootI === rootJ) return;




        if (this.counts[rootI] > this.counts[rootJ]) {

            this.roots[rootJ] = rootI;

        }

        else {

            this.roots[rootI] = rootJ;

        }



        const totalCounts = this.counts[rootI] + this.counts[rootJ];

        this.counts[rootI] = totalCounts;

        this.counts[rootJ] = totalCounts;



        this.numCats--;



    }



    getNumCats(): number {

        return this.numCats;

    }



    private findRoot(i: number) {

        if (this.roots[i] === i) return i;



        this.roots[i] = this.findRoot(this.roots[i]);



        return this.roots[i];

    }

}

All is fine, right?

Unfortunately, it passed all but 1 test, where the time limit was exceeded. The one test that it fails has a humongous input like this:

What happened? What made it take too long?

Let's examine the add function:

    add(cell: Cell) {

        this.cells.push(cell);

        this.numCats++;

        this.counts.push(1);

        this.roots.push(this.roots.length);  

        const newCellI = this.cells.length - 1;  

        for (let i = 0; i < newCellI; i++) {

            if (this.shouldUnion(this.cells[newCellI], this.cells[i])) {

                this.union(newCellI, i);

            }

        }

    }

Notice the for loop? Basically, for every new cell that is being added to cells, you need to check if it is the neighbor of each of all cells that are already in cells. It is unnecessary to check all of them because we already know which ones among them are neighbors to the new cell: the one right below, right above, next to the left, and next to the right of it.

So, we can modify this for loop to make it faster. Instead of checking if each of all cells that are already in cells is the new cell's neighbor, we do the opposite, which is check if any of the new cell's neighbors is in cells. If there is such a cell, union the new cell to its group.

The for loop becomes like this:


// go over 4 directions: up, down, left, right
const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];

for (const [dr, dc] of directions) {

    // for each direction, get the neighbor cell in that direction.
    const neighborCell:Cell = {row: row + dr, col: col + dc};

    if(//the neighborCell is not a valid cell)
        continue;

    if (// the neighborCell is in the array cells) {
        this.union(index, neighborIndex);
    }

}

In the first if conditional, we need to check if neighborCell is not a valid cell. It is not a valid cell if its row is less than 0 or greater or equal to the grid's row size or its col is less than 0 or greater or equal to the grid's col size. In particular, this is how it looks like in code:

if(neighborCell.row < 0 || neighborCell.row >= this.gridRowSize 
   || neighborCell.col < 0 || neighborCell.col >= this.gridColSize) {
       continue;
}

Notice this.gridRowSize and this.gridColSize? Remember to give those information to the constructor when instantiate the class.

In the second if conditional, we need to check if neighborCell is in the array cells. This is tricky, because in union-find, we "encode" the identity of a node by its index in an array. For example, the array roots stores the root value of a node, right? So, the root value of the node that identity is 1 will be stored at index 1 in the array roots. So, the only piece of information that we can use to identify neighborCell in cells is its index in cells. But, to identify neighborCell, we need two pieces of information, which are its row and its column. How can we combine 2 pieces into 1 piece of information? Well, we can "flatten" the grid to make a 2D coordinate into only 1D coordinate. So, the index of neighborCellin a 1D array is const neighborIndex = neighborCell.row * this.gridColSize + neighborCell.col;

To check if it is in cells, we check if this.cells[neighborIndex] is undefined. Then, the second if conditional would look like this:

if (this.cells[neighborIndex] !== undefined) {
    this.union(index, neighborIndex);
}

When come to think about it, we don't even need the array cells. In the previous implementation, we need it to store the coordinate of the land cells for the function shouldUnion to check. Now, we don't need shouldUnion, we can also eliminate the array cells.

The final code looks like this:

interface Cell {

    row: number;

    col: number;

}



class UF {

    private roots: number[];

    private counts: number[];

    private numCats: number;

    private gridRowSize: number;

    private gridColSize: number;



    constructor(rowSize: number, colSize: number) {

        this.gridRowSize = rowSize;

        this.gridColSize = colSize;

        this.roots = [];

        this.counts = [];

        this.numCats = 0;

    }



    add(cell: Cell) {

        const { row, col } = cell;

        const index = row * this.gridColSize + col; // Calculate a unique index for each cell

        this.roots[index] = index;

        this.counts[index] = 1;

        this.numCats++;



        // Check four neighboring cells

        const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];

        for (const [dr, dc] of directions) {

            const neighborCell:Cell = {row: row + dr, col: col + dc};



            if(neighborCell.row < 0 || neighborCell.row >= this.gridRowSize

            || neighborCell.col < 0 || neighborCell.col >= this.gridColSize) {

                continue;

            }



            const neighborIndex = neighborCell.row * this.gridColSize + neighborCell.col;

            if (this.roots[neighborIndex] !== undefined) {

                this.union(index, neighborIndex);

            }

        }

    }



    union(i: number, j: number) {

        const rootI = this.findRoot(i);

        const rootJ = this.findRoot(j);



        if (rootI === rootJ) return;



        if (this.counts[rootI] > this.counts[rootJ]) {

            this.roots[rootJ] = rootI;

            this.counts[rootI] += this.counts[rootJ];

        } else {

            this.roots[rootI] = rootJ;

            this.counts[rootJ] += this.counts[rootI];

        }



        this.numCats--;

    }



    getNumCats(): number {

        return this.numCats;

    }



    private findRoot(i: number): number {

        if (this.roots[i] === i) return i;



        this.roots[i] = this.findRoot(this.roots[i]);

        return this.roots[i];

    }

}



function numIslands(grid: string[][]): number {

    const numRows = grid.length;

    const numCols = grid[0].length;

    const uf = new UF(numRows, numCols);



    for (let r = 0; r < numRows; r++) {

        for (let c = 0; c < numCols; c++) {

            if (grid[r][c] === '1') {

                uf.add({ row: r, col: c });

            }

        }

    }



    return uf.getNumCats();

}

It beats 39.50% of users with TypeScript. Not ideal, but also not bad, consider that I came up to the solution all by myself.

46. Permutations

Minh Le — Mon, 11 Mar 2024 16:09:29 +0000

PROBLEM:

Given an array nums of distinct integers, return all possible permutations. You can return the answer in any order.

REASONING:

Let's say we are given this array: [1,2,3]. The process of deriving all permutations is depicted in the following diagram:

To understand what is really happening, let's just focus on the first branch of the decision tree.

The blue arrows in the following diagram illustrate the steps that we will go through, in order. At step 1, we put 1 into our basket. Now, our basket contains the element 1. At step 2, we put 2 into our basket. Now our basket contains 2 elements: 1 and 2. At step 3, we put 3 into our basket. Now our basket contains 3 elements: 1, 2, and 3. At this point, the number of elements in our basket is equal to the number of elements in the given array. We have nothing left to collect. So, we pour all content of our basket into the result array. At step 4, we go back to node 2 while throwing element 3 away. Now, our basket contains only 1 and 2. At step 5, we go back to node 1 while throwing the element 2 away. Now, our basket contains only one element, which is 1. Then, we move to the right branch and do similar things.

Notice that whenever we go back from one node, we throw the value of that node away. For example, when we go back from node 2 to node 1 at step 5, we throw the value 2 away so that our basket from containing 1 and 2 at step 4 now only has 1. This is what the backtracking algorithm does. We examine one branch, get back, clean up after ourselves so that we are ready for another branch.

Now, let's look at the decision tree again:

Notice that at the first level, we examine node 1, then node 2, then node 3. In other words, we examine all nodes of the array, one by one. We can use a for loop for that:

for(let i = 0; i < nums.length; i++) {
        // do something with nums[i]
}

Let's look at the decision tree again, but only the first branch this time:

Notice that at the second level of a branch, we only examine the nodes that we haven't examined at the first level of that branch. Because we've already examined node 1 at the first level, we only need to examine node 2 and node 3 at the second level.

Also, at the third level, we only examine the nodes that we haven't examined at the first and second levels of that branch. For example, on the left branch, because we've already examined node 1 at the first level, and node 2 at the second level, now, we only have node 3 to examine.

So, we need a hash table to mark the node that we've already examined:

const hashTB: Record<string, boolean> = {};

Then, at each level, we will go through the nums array, and only "do something" with the elements that are not in hashTB:

for(let i = 0; i < nums.length; i++) {
   if(!hashTB[nums[i]]) {
       // do something with nums[i]
   }
}

But what is "do something" anyway? Well, it's very simple: put nums[i] into the basket and hashTB.

So, we need a basket. Let's create one:

    const comb = [];

So, the process of "do something" would look like this:

comb.push(num);
hashTB[num] = true;

Notice that, at each level, we repeat this process, only with fewer elements. This calls for a recursive function. Let's call our function backtrack.

So, our function would look like this:

function backtrack(num: number) {
      // do something with the current element.
        comb.push(num);
        hashTB[num] = true;

       // going through all the elements left at the next level
        for(let i = 0; i < nums.length; i++) {
            if(!hashTB[nums[i]]) {
                backtrack(nums[i]);
            }
        }
    }

Do you remember the clean-up process in our backtracking algorithm? It's just simply setting hashTB[num] to false and using comb.pop() to pop the current value out of the basket.

But how do we know that we've already collected all the elements in nums? Well, it is when comb.length is equal to nums.length.

So, our final code looks like this:

function permute(nums: number[]): number[][] {   
    const comb = [];
    const result: number[][] = [];
    const hashTB: Record<string, boolean> = {};
    const isComplete = () => comb.length === nums.length;

    for(let i = 0; i < nums.length; i++) {
        backtrack(nums[i]);
    }

    return result;

    function backtrack(num: number) {
        comb.push(num);
        hashTB[num] = true;

        for(let i = 0; i < nums.length; i++) {
            if(!hashTB[nums[i]]) {
                backtrack(nums[i]);
            }
        }

        if(isComplete())
            result.push([...comb])

        hashTB[num] = false;
        comb.pop();
    }  
};

This code successfully generates all possible permutations of the given array by utilizing a backtracking algorithm, which explores each branch of the decision tree, collects elements along the way, and cleans up before moving to the next branch.

1448. Count Good Nodes in Binary Tree

Minh Le — Mon, 11 Mar 2024 03:55:19 +0000

PROBLEM:

Given a binary tree root, a node X in the tree is named "good" if, in the path from the root to X, there are no nodes with a value greater than X.

Return the number of good nodes in the binary tree.

REASONING:

Let's say we are given this tree: [3,2,4,6,null,1,5].

The tree's shape would look like this:

The orange nodes are good nodes because there are no nodes in the path coming from the root to their position that have values greater than them.

The root node 3 is a good node because the path from the root to its position only contains one node (itself), so there are no nodes in the path that are greater than it.
Node 2 is not a good node because the path from the root to its position contains two nodes: 3 and 2, and there is a node that is greater than it, which is 3.
The node 6 at the bottom is a good node because the path from the root to its position contains three nodes: 3, 2, and 6, and it is the greatest one along the path.

You can start to see the pattern, right? You go from the root to the end of one branch, checking for each node along the way if there is any node greater than it on the path that you have already passed. If there is not, you mark it as a good node and continue your path.

The graph below shows the route that you should go through:

You start from the root node. You check the left path by going through arrow 1 to node 2, then through arrow 2 to node 6. Along this path, you keep track of the maximum value. If any node is greater than or equal to the maximum value, you count it as a good node and update the maximum value to the node's value. Now, you reach the end of the left path, and you need to go back.

You go back through arrow 3 to node 2, then through arrow 4 back to the root.

Now, it's time to check the right path. You go through arrow 5 to node 4, then through arrow 6 to node 1. Along this path, you keep track of the maximum value. If any node is greater than or equal to the maximum value, you count it as a good node and update the maximum value to the node's value. Now, you reach the end of the first right path, and you need to go back.

You go back through arrow 7 back to node 4.

Now, it's time to check the second right path. You go through arrow 8 to node 5. Along this path, you keep track of the maximum value. If any node is greater than or equal to the maximum value, you count it as a good node and update the maximum value to the node's value. Now, you reach the end of the second right path, and you need to go back.

You go back through arrow 9 back to node 4, then through arrow 10 back to the root.

This is a depth-first search problem!

My initial approach was to set count to 0 and max to -Infinity. Then, consider the root node. If it is null, return. Otherwise, check if max is less than root.val. If it is (of course, it is. Any value is greater than -Infinity), update max to root.val and increase count. Then, do the same thing with the left node and right node consecutively.

The solution should look like this:

function goodNodes(root: TreeNode | null): number {
    let count = 0;
    let max = -Infinity;

    dfs(root);

    return count;

    function dfs(node: TreeNode | null) {
        if (node === null) return;

        if (max <= node.val) {
            count++;
            max = node.val;
        }

        dfs(node.left);
        dfs(node.right);
    }
}

There are two values that my code keeps track of along the way: count and max. Let's use the graph to see how it updates those values.

You check the root node. Its value is greater than max, so you increase count from 0 to 1 and update max to 3 (equal to the value of the root node).
You check node 2. Its value is less than max. You keep count and max the same.
You check node 6. Its value is greater than max, so you increase count from 1 to 2 and update max to 6.
You go back to node 2, then to node 3.

Now, you check node 4.

Wait, there is something wrong here. Right before you check node 4 (at arrow 5), max should reflect the current maximum value of the current path, which is 3, not 6. Why is it still 6?

It turns out that when you go back one level, you need to update the max accordingly. For example, when you are at node 6, the maximum value is 6. However, when you go back to node 2, the maximum value is not 6 anymore, because now, 6 is not in the path. The maximum value should be 3.

Updating the max value on the way back is too complicated. Why don't we store the max value at each level? For example, when we are at node 2, we save the max value at node 2 to be 3. Then, after we go to node 6 and come back to node 2, we just get the value max that we previously saved at node 2 to update our current max.

Let's introduce prevMax!

We can add one more parameter prevMax to our dfs function.

prevMax is the maximum value before we call the function. Before we call the dfs function on the root node, prevMax is -Infinity. So, we call the dfs function like this: dfs(root, -Infinity).

Then, inside the dfs function, we assign prevMax to curMax. Then, we update curMax depending on the value of node.val. Then we call dfs on node.left with the value of curMax. It will traverse all the way to the left, then go back. When it goes back from node.left, the value of curMax is still the same, ready for calling dfs on node.right.

So, the revised solution is like this:

function goodNodes(root: TreeNode | null): number {
    let count = 0;

    dfs(root, -Infinity);

    return count;

    function dfs(node: TreeNode | null, prevMax: number) {
        if (node === null) return;

        let curMax = prevMax;

        if (curMax <= node.val) {
            count++;
            curMax = node.val;
        }

        dfs(node.left, curMax);
        dfs(node.right, curMax);
    }
}

This approach ensures that the max value is correctly updated as we traverse the binary tree, allowing us to accurately count the number of good nodes.

424. Longest Repeating Character Replacement

Minh Le — Sun, 10 Mar 2024 01:35:44 +0000

function characterReplacement(s: string, k: number): number {
    let lo = k, hi = s.length + 1;

    while(lo < hi - 1) {
        const mid = Math.floor((lo + hi)/2);
        if(isValidLength(mid)) {
            lo = mid;
        }
        else {
            hi = mid;
        }
    }

    return lo;

    function isValidLength(l:number):boolean {
        const hashTB:Record<string, number> = {};

        let start = 0, maxFreq = 0;

        for(let end = 0; end < s.length; end++) {
            if(!hashTB[s[end]]) hashTB[s[end]] = 1;
            else hashTB[s[end]]++;


            if(end - start + 1 > l) {
                hashTB[s[start]]--;
                start++;
            }

            if(maxFreq < hashTB[s[end]]) {
                    maxFreq = hashTB[s[end]];
            }

            if(l - maxFreq <= k) return true;

        }

        return false;
    }
};

My solution might not be the fastest, most efficient, or simplest, but I want to use this opportunity to delve deeper into the related algorithms.

The problem requires us to find the length of the longest substring that contains the same letter, which can be achieved by changing any character of the string to any other uppercase English letter no more than k times.

The brute force approach would start with a substring of length 1 and check if it is valid. If it is, the process continues by checking substrings of lengths 2, 3, and so on, until finding the first substring that is not valid. Let's say this substring is of length n. Thus, the longest valid substring is one of length n-1, and we would return n-1.

However, this method is time-consuming. Is there a faster way? Notice that we are consecutively checking substrings of lengths 1, 2, 3, 4, 5, and so on, meaning that the lengths of the substrings we are checking are in sorted and ascending order. With any searching task in a sorted sequence like this, we can always employ binary search to speed up the process.

How can we apply binary search in this context? First, we need to identify the characteristics that make a substring valid. Essentially, the problem requires us to find a substring where the difference between the frequency of the most frequently occurring character and the length of the substring is less than or equal to k. This difference represents the number of characters that are not the most frequent character. If this number is less than or equal to k, we can change all of them to the most frequent character, resulting in a substring that contains only the same character (the most frequent character).

Let's say the length of the substring is l and the frequency of the most frequent character is maxFreq. A substring is considered valid if l - maxFreq <= k. If a substring of length l is valid, is a substring of length l-1 also valid? Of course, it is. This is because (l - 1) - maxFreq < l - maxFreq <= k. In other words, if a substring of length l is valid, all substrings shorter than that are also valid.
Conversely, if a substring of length l is invalid, what can we say about substrings of length l+1? An invalid substring of length l means that l - maxFreq > k. But since l + 1 > l, it follows that l + 1 - maxFreq > l - maxFreq > k. Therefore, if a substring of length l is invalid, all substrings longer than l are also invalid.

With this information in hand, how can we apply binary search? Binary search operates by setting low (lo) and high (hi) pointers at both ends of the search space. A search space is a set in which any element could potentially be the one we are looking for. We then compare the element in the middle with the target element to determine if the target is in the first half or the second half of the search space. Based on this comparison, we adjust the lo and hi pointers to shrink the search space. The process continues until there is only one element left, which is the element we are looking for.

Let's return to our problem and define the search space with two boundaries using pointers: lo and hi. We know that a substring of length k is always valid because we can change all its characters (up to k times) to the same character. Since a substring of length k is valid, all shorter substrings are also valid, but they are not the longest valid substrings. Therefore, we start the search space from k, setting lo to k as the starting point.

Additionally, we cannot rule out the possibility that the original string is the longest valid substring. Therefore, we set hi to the length of the string plus 1 (s.length + 1) to mark the end of the search space.

In summary, lo points to the length of a longest valid substring known so far, and hi points to one unit higher than the search space. We call these two facts invariant because we need to maintain them after each round.

To shrink the search space, we follow these steps:

Find the midpoint.
If we can find a valid substring whose length equals the value at the midpoint, it means all substrings that are shorter than that are also valid but can’t be the longest substring. The longest one that we know is the one whose length equals to the value at the midpoint. To shrink the search space while keeping the invariant, we move lo to mid. Now, lo still points to the length of the longest valid substring known so far (previously pointed by mid), and hi remains in the same position.
If we cannot find a valid substring whose length equals the value at the midpoint, it means all longer substrings are also invalid. Thus, the length of the longest substring should be less than the midpoint value. We shrink the search space to the range from lo to mid - 1 by moving hi to mid. Now, the hi pointer is one unit higher than the search space, and lo remains in the same position, maintaining the invariant.
We continue steps 2 and 3 until only one element is left in the search space. Typically, in binary search, when the algorithm stops, lo and hi can point to either the same element or two adjacent elements, with lo pointing to the lower one and hi pointing to the higher one. In our case:

lo always points to the length of a known valid substring, while hi always points to the length of a known invalid substring. Therefore, they cannot point to the same element.
Any invalid substring has a length greater than any valid substring. For example, if there is a value l such that it is the length of an invalid substring while l+1 is the length of a valid substring, it leads to a contradiction because a shorter string, including l, should also be valid. Therefore, hi always points to an invalid substring and lo always points to a valid substring, so hi is always greater than lo.
The only possibility left is that lo and hi are adjacent, with lo pointing to the lower value and hi pointing to the higher value. The invariant states that lo points to the length of the longest valid substring known so far while hi points to one unit higher than the search space. Thus, there is only one value in the search space, pointed to by lo, that can be the length of the longest substring. It is the one that we are looking for.

743. Network Delay Time - Dijkstra's Algorithm

Minh Le — Fri, 08 Mar 2024 22:39:04 +0000

function networkDelayTime(times: number[][], n: number, k: number): number {
    const adjList:Record<string, [number,number, number][]> = {};

    for(let i = 0; i < times.length; i++) {
        if(!adjList[times[i][0]]){
            adjList[times[i][0]] = [[times[i][0], times[i][1], times[i][2]]];
        }
        else {
            adjList[times[i][0]].push([times[i][0], times[i][1], times[i][2]]);
        }
    }


    const minTimes = Array(n+1).fill(Infinity);
    minTimes[k] = 0;

    const minHeap = new MinHeap();
    const edges = adjList[String(k)];

    if(!edges) return -1;

    for(let i = 0; i < edges.length; i++)
        minHeap.add(edges[i]); 


    while(!minHeap.isEmpty()){
        const [source, target, time] = minHeap.pop();

        if(minTimes[target] > minTimes[source] + time) {

            minTimes[target] = minTimes[source] + time;

            const edges = adjList[target];

            if(!edges) continue;


            for(let i = 0; i< edges.length; i++) {
                minHeap.add(edges[i]);
            }
        }

    }

    let max = 0;


    for(let i = 1; i < minTimes.length; i++) {
        if(minTimes[i] === Infinity)
            return -1;
        else if(max < minTimes[i])
            max = minTimes[i];
    }

    return max;
};

class MinHeap {
    private arr:[number,number,number][] = [];

    isEmpty():boolean {
        return this.arr.length === 0;
    }


    add(e:[number,number,number]){
        this.arr.push(e);

        let curI = this.arr.length - 1, parentI = this.getParentI(curI);

        while(curI > 0 && this.arr[curI][2] < this.arr[parentI][2]){
            this.swap(curI, parentI);
            curI = parentI;
            parentI =  this.getParentI(curI);
        }
    }

    pop():[number,number,number]{
        const retE = this.arr[0];
        const last = this.arr.pop();

        if(this.arr.length === 0) return retE;

        this.arr[0] = last;

        let curI = 0, leftChildI = this.getLeftChildI(curI), rightChildI = this.getRightChildI(curI);

        while((leftChildI < this.arr.length && this.arr[leftChildI][2] < this.arr[curI][2])
                || (rightChildI < this.arr.length && this.arr[rightChildI][2] < this.arr[curI][2])) {
                    const smallerChildI = (rightChildI >= this.arr.length || this.arr[rightChildI][2] > this.arr[leftChildI][2])
                                            ? leftChildI : rightChildI;

                    this.swap(smallerChildI, curI);
                    curI = smallerChildI;
                    leftChildI  = this.getLeftChildI(curI);
                    rightChildI = this.getRightChildI(curI);
                }

        return retE;
    }

    private swap(i:number, j:number) {
        const temp = this.arr[i];
        this.arr[i] = this.arr[j];
        this.arr[j] = temp;
    }

    private getParentI(i:number) {
        return Math.floor((i - 1)/2);
    }

    private getLeftChildI(i:number) {
        return 2*i + 1;
    }

    private getRightChildI(i:number) {
        return 2*i + 2;
    }
}

Dijkstra's algorithm works by iteratively updating the shortest path to each node. Starting from the source node, it considers all outgoing edges and adds the shortest edge to the path. This process is repeated for each newly added node, considering all its outgoing edges. If a shorter path is discovered to a node, the algorithm updates the path length. This continues until all nodes have been considered.

Here's an overview of the implementation:

Initialize a minTimes array to store the shortest time to reach each node, setting all elements to Infinity, except for the source node, which is set to 0.
Push all edges originating from the source node into a min-heap.
Pop the shortest edge from the min-heap and consider its target node. If the path through this edge to the target node is shorter than the current path, update the time in minTimes and add all edges originating from the target node to the min-heap.
Repeat step 3 until the min-heap is empty.
Iterate through the minTimes array to find the maximum value. If any element remains Infinity, it indicates that the corresponding node is unreachable, so return -1.
Return the maximum value, representing the time required to reach the furthest node.

743. Network Delay Time - Breadth-First Search Approach

Minh Le — Thu, 07 Mar 2024 22:21:07 +0000

function networkDelayTime(times: number[][], n: number, k: number): number {

    const adjList: Record<string,[number,number][]> = {};

    for(let i = 0; i < times.length; i++) {
        if(adjList[times[i][0]] === undefined) {
            adjList[String(times[i][0])] = [[times[i][1], times[i][2]]];
        } else {
            adjList[String(times[i][0])].push([times[i][1], times[i][2]]);
        }
    }

    const minTimes = Array(n+1).fill(Infinity);
    minTimes[k] = 0;
    let nextNodes = [k];

    while(nextNodes.length !== 0) {
        const temp:number[] = [];

        for(let iN = 0; iN < nextNodes.length; iN++) {
            const curNode = nextNodes[iN];
            const curEdges = adjList[String(curNode)];

            if(!curEdges) continue;


            for(let iE = 0; iE < curEdges.length; iE++) {
                if(minTimes[curEdges[iE][0]] > minTimes[curNode] + curEdges[iE][1]) {
                    minTimes[curEdges[iE][0]] = minTimes[curNode] + curEdges[iE][1];
                    temp.push(curEdges[iE][0]);
                }
            }
        }

        nextNodes = temp;


    }

    let max = 0;

    for(let i = 1; i < minTimes.length; i++) {
        if(minTimes[i] === Infinity)
            return -1;
        else if( max < minTimes[i])
            max = minTimes[i];
    }

    return max;
};

This is the breadth-first search approach to solving this problem. It is much faster than the depth-first search approach that I've discussed (beats 83.18% of users with TypeScript). Well, who am I kidding? That percentage is kind of meaningless since it can vary (a lot) from one submission to another of the same code. But if the DFS approach only beats somewhere around 9.7% of users, it must mean something, right?

So, in this approach, I use an array of nodes called nextNodes to keep track of which nodes I need to process in the next round. At first, it only contains the source node (k) because in the next round, which is also the first round, we need to examine the source node first. Then, we enter the while loop until there are no more next nodes to process (nextNodes.length === 0).

At each round of the while loop, we pick the nodes from nextNodes, one by one. For each of them, we get the edges array from the adjacency list (well, I forgot to mention, we need to build the adjacency list adjList first, where each key is a node and the value is an array of pairs in which the first value is the target node and the second value is the weight of the edge that leads from it to the target node). For each edge, we check if adding that edge to our graph creates another path from the source node to the target node that is shorter than the current distance from the source node to the target node. If it is, we update the min value.

Then, we iterate through the min value array to find the maximum value and return it. If any element from the min value array still hasn't been updated yet and still has the Infinity value, it means we can't reach all of the nodes from the source node. In that case, we return -1.

743. Network Delay Time - Depth First Search Approach

Minh Le — Thu, 07 Mar 2024 05:40:22 +0000

function networkDelayTime(times: number[][], n: number, k: number): number {


   const adjList: Record<string, [number,number][]> = {};
   for(let i = 0; i < times.length; i++) {
       if(!adjList[String(times[i][0])]) {
           adjList[String(times[i][0])] = [[times[i][1], times[i][2]]];
       }
       else {
           adjList[String(times[i][0])].push([times[i][1], times[i][2]]);
       }
   }

    const curTimes = Array(n + 1).fill(Infinity);
    curTimes[k] = 0;

    dfs(adjList[String(k)], k);

    function dfs(edges:[number,number][]|undefined, curV:number) {
        if(edges === undefined) return;

        for(let i = 0; i < edges.length; i++) {
            const curE = edges[i];

            if(curE[1] + curTimes[curV] < curTimes[curE[0]]){
                curTimes[curE[0]] = curE[1] + curTimes[curV];
                dfs(adjList[String(curE[0])], curE[0]);
            }



        }
    }

    let max = 0;

    for(let i = 1; i < curTimes.length; i++) {
        if(curTimes[i] === Infinity)
            return -1;

        if(max < curTimes[i]) {
            max = curTimes[i];
        }
    }

    return max;

};

This problem is solved using a depth-first search (DFS) approach. Initially, I considered using a min-heap to select the smallest weight edge and then adding the target vertex to the graph. However, this method only yields the total length of the shortest-spanning tree, which is not the required solution for this problem.

In the DFS approach, the algorithm explores all possible paths originating from the source vertex. During each iteration, it updates the distance from the source to the current vertex with the minimum value found so far. For example, consider two paths from the source vertex s to vertex 3. If the first path takes 3 units of time to reach vertex 3, this value is recorded. Upon exploring the second path, if it takes only 2 units of time to reach vertex 3, the distance from s to 3 is updated to 2. Conversely, if the second path takes more than 3 units of time, no update is made, as a shorter path already exists.

The algorithm ensures that the shortest time to reach each vertex from the source is calculated, and the maximum of these times is returned as the final result. If any vertex is unreachable from the source, the function returns -1.