LeetCode - Algorithms - 994. Rotting Oranges

Problem

994. Rotting Oranges

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
class Solution {
    final static int d[][] = {
        {0,1},
        {1,0},
        {0,-1},
        {-1,0}
	};
    
    private boolean isValid(int[][] grid, int width, int height, int row, int col) {
		return (row >= 0) && (row < width) && (col >= 0) && (col < height) && grid[row][col]==1;
	}
    
    public int orangesRotting(int[][] grid) {
        int h = grid.length;
        int w = grid[0].length;

        Queue<Node> queue = new LinkedList<Node>();
        
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
            	if (grid[i][j] == 2) {
            		queue.add(new Node(new Point(i,j),0));
            	}
            }
        }
        
        int ans = 0;

        while (!queue.isEmpty()) {
            Node curr = queue.poll();
            int row = curr.pt.x;
            int col = curr.pt.y;

			for (int i = 0; i < 4; i++) {
				int x = row + d[i][0];
				int y = col + d[i][1];
				if (isValid(grid, h, w, x, y)) {
					grid[x][y] = 2;
					queue.add(new Node(new Point(x, y), curr.dist + 1));
					ans = curr.dist + 1;
				}
			}
        }
        
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (grid[i][j] == 1) {
					return -1;
				}
			}
		}
		
        return ans;        
    }
    
	class Point {
		int x;
		int y;

		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

	class Node {
		Point pt;
		int dist;

		public Node(Point pt, int dist) {
			this.pt = pt;
			this.dist = dist;
		}
	}    
}

Submission Detail

  • 303 / 303 test cases passed.
  • Runtime: 2 ms, faster than 91.42% of Java online submissions for Rotting Oranges.
  • Memory Usage: 38.4 MB, less than 81.25% of Java online submissions for Rotting Oranges.

ref