Leetcode Daily - August 9, 2020

Rotting Oranges

Link to Leetcode Question

Lately I've been grinding Leetcode and decided to record some of my thoughts on this blog. This is both to help me look back on what I've worked on as well as help others see how one might think about the problems.

However, since many people post their own solutions in the discussions section of Leetcode, I won't necessarily be posting the optimal solution.

Question

(Copy Pasted From Leetcode)

In a given grid, each cell can have one of three values:

• the value 0 representing an empty cell;
• the value 1 representing a fresh orange;
• the value 2 representing a rotten orange. Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1 instead.

Example 1:

Input: [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Example 2:

Input: [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation:  The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3:

Input: [[0,2]]
Output: 0
Explanation:  Since there are already no fresh oranges at minute 0, the answer is just 0.

Note:

1 <= grid.length <= 10
1 <= grid[0].length <= 10
grid[i][j] is only 0, 1, or 2.

My Approach(es)

I won't go over all the code for all attempts but I will explain my approach(es) qualitatively.

Attempt 1 - Brute Force (iterate out the grids)

(Submission - Accepted)

My basic thought process focused on whether I could determine if the rotting oranges would reach all the fresh oranges on the grid. I realized that if the board didn't change between one minute and the next, that it wouldn't change at all anymore, because rotten oranges only spread to adjacent fresh oranges.

My brute force approach simply iterates the grid minute by minute by checking all the fresh oranges for adjacency to rotten oranges and then changing them from 1 to 2. I decided to use a while loop with a counter that counts the number of minutes elapsed (number of iterations).

I used a while loop but I realized there were two ending conditions:

1. The counter amount should be returned if the grid has no fresh oranges left.

2. The value -1 should return instead if the grid does not change from iteration N to iteration N+1 (but there are still fresh oranges left).

The only other complication is making copies of the grid so that I could check if the new grid (after rotten orange spread has been calculated) is the same as the current grid (before the rotten oranges spread for that minute). In Javascript, assigning the arrays equal to each other would make them reference the same array, so they would always end up equal. I wrote some helper functions in my code but end up with a pretty cumbersome implementation.

var orangesRotting = function(grid) {
    let currGrid = copyGrid(grid);
    let minutes = 0;

    while (true) {
        // check currentGrid for fresh (1)
        if (!hasFresh2D(currGrid)) {
            return minutes
        }

        let newGrid = copyGrid(currGrid);
        // process the new Grid for rottenness 
        for (let i = 0; i < newGrid.length; i++) {
            for (let j = 0; j < newGrid[0].length; j++) {
                // check 4 directions of a 1 for 2's, if true change it to a 2 
                if (newGrid[i][j] === 1) {
                    if (i-1 >= 0 && currGrid[i-1][j] === 2) newGrid[i][j] = 2
                    if (j-1 >= 0 && currGrid[i][j-1] === 2) newGrid[i][j] = 2
                    if (i+1 < newGrid.length && currGrid[i+1][j] === 2) newGrid[i][j] = 2
                    if (j+1 < newGrid[0].length && currGrid[i][j+1] === 2) newGrid[i][j] = 2
                }
            }
        }

        // check if no fresh oranges get rotten 
        if (allEqual2D(currGrid, newGrid)) {
            // cannot get more oranges rotten 
            // because no change 
            return -1;
        }

        minutes ++ 
        currGrid = copyGrid(newGrid);
    }
};

const copyGrid = (arrs1) => {
    let result = [];
    for (let i = 0; i < arrs1.length; i++) {
        result.push(arrs1[i].slice())
    }
    return result;
}

const allEqual2D = (arrs1, arrs2) => {
    // assume the lengths are equal, just want to check values 
    for (let i = 0; i < arrs1.length; i++) {
        for (let j = 0; j < arrs1[0].length; j++) {
            if (arrs1[i][j] !== arrs2[i][j]) return false;
        }
    }
    return true;
}

const hasFresh2D = (arrs1) => {
    for (let i = 0; i < arrs1.length; i++) {
        for (let j = 0; j < arrs1[0].length; j++) {
            if (arrs1[i][j] === 1) return true;
        }
    }
    return false 
}

Discussion and Conclusions

Some of my notable thoughts about my implementation can be summarized as:

• Can I use a different data structure to store the grids instead of a 2D array?
• Are there better indicators or ways of calculating the ending conditions? For example, Using a search algorithm starting from every rotten orange to every fresh orange. The search algorithms would also calculate the manhattan grid distances and the maximum value would be returned unless theres are fresh oranges that cannot be reached (if at least one exists, return -1).
• I believe the algorithm I used is O(n⁴), if n is the length or width of the grid. That is because I check the entire grid once per iteration (O(n²), and for a rotten orange to spread from one corner to a fresh orange in the other it whose maximum path (if zigzagging) can take around half the boxes of the grid (and the size of the grid is O(n²). But luckily, n is constrained to 10, and n⁴ is 10,000, so investigating better algorithms for dealing with grids could pay off.