INFO The width path algorithm allows the path of a graph or a tree as follows: we start by exploring a source node, then its successors, then the unexplored successors of successors, etc

PROBLEM Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell. The distance between two adjacent cells is 1. Example1 *Input*: mat = [[0,0,0],[0,1,0],[0,0,0]] *Output*: [[0,0,0],[0,1,0],[0,0,0]] Example2 *Input*: mat = [[0,0,0],[0,1,0],[1,1,1]] *Output*: [[0,0,0],[0,1,0],[1,2,1]] SOLVING we’ll use Breadth-first Search method Steps Create matrix result with the same size filled by 0 Create a queue Parcor the list if there is a 1 next to a 0 : Add in result 1 at it’s position (because it’s at one cell from a zero) And push to the queue it’s position While queue not empty: Pop the queu to get the current value Check the neighboors (up, down, right, left) If it’s equal to 1 and equal to 0 in result (That means we didn’t see this cell before): Push to the queue it’s position Add in result the parent value in result + 1 Return result Code class Solution { public: vector<vector<int>> updateMatrix(vector<vector<int>> &mat) { m = mat.

PROBLEM You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition: struct Node { int val; Node *left; Node *right; Node *next; } Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. Initially, all next pointers are set to NULL.

PROBLEM You are given a m x n grid where each cell can have one of three values: 0 representing an empty cell, 1 representing a fresh orange, or 2 representing a rotten orange. Every minute, any fresh orange that is 4-directionally adjacent 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.