Case study: rotten orange

March 31, 2020

Introduction

It is my favorite algorithm. I did not practice algorithm or weekly contest last few months, I was too busy to practice. But I did learn from my experience as an interviewer. Rotten orange is the classical algorithm which can be written using BFS algorithm using Queue.

Case study

Here is the gist.

	class Solution {
	public static void main(String[] args) {
	Solution s = new Solution();
	int[] nums2 = {2, 1};
	int[][] grid = {{2, 1, 1}, {1, 1, 0}, {0, 1, 1}};
	System.out.println(s.rottenOrange(grid));
	}
	public int rottenOrange(int[][] grid) {
	int h = grid.length;
	if(h == 0) {
	return -1;
	}
	int w = grid[0].length;
	int[] directionX = {0, 0 , -1, 1};
	int[] directionY = {1, -1 , 0, 0};
	Queue<Integer> queue = new LinkedList<>(); // x, y -> x * w + y
	for(int i = 0; i < h; i++) { // height
	for(int j = 0; j < w; j++) { // width
	if(grid[i][j] == 2) {
	queue.offer(i * w + j); // [i,j] -> i * w + j, integer
	}
	}
	}
	int mins = 0;
	while(!queue.isEmpty()) {
	int size = queue.size();
	// update mins
	mins++;
	for(int i = 0; i < size; i++) {
	int cur = queue.poll();
	// 0 1 2 * * * * * * *
	// 3 4 5
	// 6 7 8 -> [0, 1, 2, 3, 4, 5, 6, 7, 8] -> row/ col number -> 0 - 8
	// x * h + y <- x * (w + h) -> less error-prone -> out-of-range - which line
	// cur = x * w + y
	// x = cur / w;
	// y = cur % w;
	int x = cur / w; // divide - x = cur/ (w + h)
	int y = cur % w; // y = cur % (w + h)
	for(int j = 0; j < 4; j++) {
	int nextX = x + directionX[j];
	int nextY = y + directionY[j];
	if(inbound(nextX, nextY, grid)) {
	if(grid[nextX][nextY] == 1) { // fresh ->
	queue.offer(nextX * w + nextY);// add just-turn-rotten
	grid[nextX][nextY] = 2;
	}
	}
	}
	}
	}
	for(int i = 0; i < h; i++) {
	for(int j = 0; j < w; j++) {
	if(grid[i][j] == 1) { // fresh orange
	return -1;
	}
	}
	}
	if(mins == 0) { //
	return 0;
	}
	return mins - 1;
	}
	public boolean inbound(int x, int y, int[][] grid) {
	int h = grid.length;
	if(h == 0) {
	return false;
	}
	int w = grid[0].length;
	// x >=0
	return x > -1 && x < h && y > -1 && y < w;
	/*
	if(x > -1 && x < h && y > -1 && y < w) {
	return true;
	}
	return false;*/
	}
	}

view raw 994RottingOranges.java hosted with ❤ by GitHub