Algorithm to Traverse a 2D Matrix
Date: Jul 2014
Level: Advanced


INTERVIEW QUESTIONS

Company: Oracle
Question Title: Algorithm to Traverse a 2D Matrix
Language: Java
QUESTION DETAILS:

Traverse a given 2D matrix from given source to destination in such way that every cell should be visited exactly one time (we have to cover all cells of matrix exactly once and have to reach the destination).


Here's the solution:
import java.util.*;
public class Traverse2DMatrix {
    class Point{
        int x;
        int y;
        public Point(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    public Point start = new Point(0, 0);
    public Point end = new Point(1, 2);
    public int [][] matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    public void traverse2D(){
        int m = matrix.length;
        int n = matrix[0].length;
        boolean[][] visited = new boolean[m][n];
        ArrayList<Point> res = new ArrayList<Point>();
        Stack<Point> st = new Stack<Point>();
        st.push(start);
        while(st.isEmpty() == false) {
            Point temp = st.pop();
            if(visited[temp.x][temp.y] == false) {
                res.add(temp);
                visited[temp.x][temp.y] = true;
                if(temp.x - 1 >= 0 && (temp.x - 1 != end.x || temp.y != end.y)) {
                    st.push(new Point(temp.x - 1, temp.y));
                }
                if(temp.x + 1 <= m - 1 && (temp.x + 1 != end.x || temp.y != end.y)) {
                    st.push(new Point(temp.x + 1, temp.y));
                }
                if(temp.y - 1 >= 0 && (temp.x != end.x || temp.y - 1 != end.y)) {
                    st.push(new Point(temp.x, temp.y - 1));
                }
                if(temp.y + 1 <= n - 1 && (temp.x != end.x || temp.y + 1 != end.y)) {
                    st.push(new Point(temp.x, temp.y + 1));
                }
            }
        }
        res.add(end);
    }
}
All Questions