CareerCup

Looking for interview experience sharing and coaching?

Visit aonecode.com for private lessons by FB, Google and Uber engineers

Our ONE TO ONE class offers

SYSTEM DESIGN Courses (highly recommended for candidates for FLAG & U)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Coding),
latest interview questions sorted by companies,
mock interviews.

Our students got hired from G, U, FB, Amazon, LinkedIn and other top tier companies after weeks of training.

Feel free to email us aonecoding@gmail.com with any questions. Thanks!

Solution:
Breath First Search.
Create a map that stores Map<Node, [PreviousNode, Cost]> the cost to the current node.
Since the question asks for the actual shortest path, in the map also store the previous node in the path.
During the BFS, if the current node has been visited before, but the current cost < former cost, update the cost and route for the current node (only keep the min cost route). Otherwise if current cost > former cost, stop search by not including the current node into the BFS queue.

To stand for a node in the map with an integer rather than a point (x, y), do
nodeID = x * matrix[0].length + y;

To convert the ID back to a point, do
x = nodeID / matrix[0].length;
y = nodeID % matrix[0].length;

//Follow-up
    public void minCostPath(int[][] matrix) {
        Queue<Integer> queue = new ArrayDeque<>();
        Map<Integer, int[]> map = new HashMap<>(); //key: current location; value[0]: the previous node from where it gets to the current location, value[1]:total cost up to current node
        for(int j = 0; j < matrix[0].length; j++) { //put first row into queue
            if(matrix[0][j] != 0) {
                queue.add(j);
                map.put(j, new int[] {-1, matrix[0][j]});
            }
        }
        int destination = -1, minCost = Integer.MAX_VALUE;
        while(!queue.isEmpty()) {
            int id = queue.poll();
            int fromX = id / matrix[0].length, fromY = id % matrix[0].length;
            if(fromX + 1 < matrix.length) {
                int cost = moveMinCost(queue, map, matrix, id, fromX + 1, fromY);
                if (cost >= 0 && fromX + 1 == matrix.length - 1) {
                    if (cost < minCost) {
                        destination = id + matrix[0].length;
                        minCost = cost;
                    }
                }
            }
            if(fromY + 1 < matrix[0].length)
                moveMinCost(queue, map, matrix, id, fromX, fromY + 1);
            if(fromX - 1 >= 0)
                moveMinCost(queue, map, matrix, id, fromX - 1, fromY);
            if(fromY - 1 >= 0)
                moveMinCost(queue, map, matrix, id, fromX, fromY - 1);
        }
        if(destination == -1) return; //no such path from first row to last row
        while(map.containsKey(destination)) {   //print shortest path from destination to source
            int x = destination / matrix[0].length, y = destination % matrix[0].length;
            System.out.println("(" + x + ","+ y + "),");
            destination = map.get(destination)[0];
        }
    }

    private int moveMinCost(Queue<Integer> queue, Map<Integer, int[]> map, int[][] matrix, int from, int x, int y) {
        if(matrix[x][y] == 0) return -1;
        int id = x * matrix[0].length + y;
        int cost = map.get(from)[1] + matrix[x][y];
        if(!map.containsKey(id) || map.get(id)[1] > cost) {
            map.put(id, new int[]{from, cost});
            queue.add(id);
            return cost;
        }
        return -1;
    }

Apply BFS through a queue, with each Node containing pointer to previous Node and cost so far. Keep track of nodes visited. If a Node is present again in the queue, it can be ignored as we previously traversed it with lower cost.

The original question: BFS.
The follow up: Dijkstra (the code below).

class Node {
	public:
		Node(int row, int col)
		{
			row_ = row;
			col_ = col;
		}
		int row_, col_;
};

class Label {
	public:
		Label(int parent_idx, int idx, Node node, int cost) : node_(node.row_, node.col_)
		{
			parent_idx_ = parent_idx;
			idx_ = idx;
			cost_ = cost;
		}
		bool operator>(Label const &other) const
		{
			return cost_ > other.cost_;
		}

		int idx_, parent_idx_;
		Node node_;
		int cost_;
};

vector <Node> ShortestPath(vector<vector<int>> const &m)
{
	vector<Node> path;
	if (!m.empty() &&
		!m[0].empty())
	{
		priority_queue<Label, vector<Label>, greater<Label>> pq;
		unordered_set<uint64_t> seen;
		vector<Label> labels;
		for (int col = 0; col < m[0].size(); ++col) {
			labels.push_back(Label(-1, labels.size(), Node(0, col), m[0][col]));
			pq.push(labels.back());
		}
		while (!pq.empty()) {
			Label l = pq.top();
			pq.pop();
			Node n = l.node_;
			uint64_t key = ((uint64_t)n.row_ << 32) | n.col_;
			if (m[n.row_][n.col_] != 0 &&
				seen.find(key) == seen.end())
			{
				seen.insert(key);
				if (n.row_ == m.size() - 1) {
					for (int i = l.idx_; i != -1; i = labels[i].parent_idx_) {
						path.push_back(labels[i].node_);
					}
					reverse(path.begin(), path.end());
					break;
				}
				if (n.row_ - 1 >= 0) {
					labels.push_back(Label(l.idx_, labels.size(), Node(n.row_ - 1, n.col_), l.cost_ + m[n.row_ - 1][n.col_]));
					pq.push(labels.back());
				}
				if (n.row_ + 1 < m.size()) {
					labels.push_back(Label(l.idx_, labels.size(), Node(n.row_ + 1, n.col_), l.cost_ + m[n.row_ + 1][n.col_]));
					pq.push(labels.back());
				}
				if (n.col_ - 1 >= 0) {
					labels.push_back(Label(l.idx_, labels.size(), Node(n.row_, n.col_ - 1), l.cost_ + m[n.row_][n.col_ - 1]));
					pq.push(labels.back());
				}
				if (n.col_ + 1 < m[0].size()) {
					labels.push_back(Label(l.idx_, labels.size(), Node(n.row_, n.col_ + 1), l.cost_ + m[n.row_][n.col_ + 1]));
					pq.push(labels.back());
				}
			}
		}
	}
	return path;
}

use Dijkstra