BFS Flashcards
- Rotting Oranges
Medium
You are given an 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.
Example 1:
Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output:
class Solution {
int count = 0;
Queue<int[]> q = new LinkedList<>();
int[][] neighbour = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
public int orangesRotting(int[][] grid) {
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 2) {
q.add(new int[] { i, j });
}
}
}
while (!q.isEmpty()) {
int size = q.size();
count++;
for (int k = 0; k < size; k++) {
int[] curr = q.poll();
for (int i = 0; i < neighbour.length; i++) {
int curr_x = curr[0] + neighbour[i][0];
int curr_y = curr[1] + neighbour[i][1];
if (curr_x < 0 || curr_y < 0 || curr_x >= grid.length || curr_y >= grid[0].length && grid[curr_x][curr_y]==0){
continue;
}
System.out.println(curr_x + "," + curr_y);
if (grid[curr_x][curr_y] == 1) {
grid[curr_x][curr_y] = 2;
q.add(new int[] { curr_x, curr_y });
}
}
}
}
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 1) {
return -1;
}
}
}
return count - 1;
}
}
- Sum of Nodes with Even-Valued Grandparent
Medium
Given the root of a binary tree, return the sum of values of nodes with an even-valued grandparent. If there are no nodes with an even-valued grandparent, return 0.
A grandparent of a node is the parent of its parent if it exists.
Example 1:
Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 18
Explanation: The red nodes are the nodes with even-value grandparent while the blue nodes are the even-value grandparents.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
int sum = 0;
public int sumEvenGrandparent(TreeNode root) {
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
while (!q.isEmpty()) {
TreeNode curr = q.poll();
if (curr.val % 2 == 0 && curr.left != null) {
if (curr.left.left != null)
sum = sum + curr.left.left.val;
if (curr.left.right != null)
sum = sum + curr.left.right.val;
q.add(curr.left);
}
if (curr.val % 2 == 0 && curr.right != null) {
if (curr.right.left != null)
sum = sum + curr.right.left.val;
if (curr.right.right != null)
sum = sum + curr.right.right.val;
q.add(curr.right);
}
}
return sum;
} }
- Deepest Leaves Sum
Medium
Given the root of a binary tree, return the sum of values of its deepest leaves.
Example 1:
Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
Output: 15
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
int sum = 0;
public int deepestLeavesSum(TreeNode root) {
Queue<TreeNode> q = new LinkedList<>();
Map<Integer, List<Integer>> hm = new HashMap<>();
q.add(root);
int depth = 0;
while(!q.isEmpty()){
depth++;
int size = q.size();
for(int i =0;i<size;i++){
TreeNode curr = q.poll();
if(curr.left!=null){
q.add(curr.left);
}
if(curr.right!=null){
q.add(curr.right);
}
if(!hm.containsKey(depth)){
hm.put(depth, new ArrayList<>());
}
hm.get(depth).add(curr.val);
}
}
List<Integer> finalList = hm.get(hm.size());
for(int i : finalList){
sum= sum+i;
}
return sum;
} }
- Binary Tree Level Order Traversal
Medium
Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {</Integer>
List<List<Integer>> output = new ArrayList<>();
if(root==null) return output;
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
while(!q.isEmpty()){
List<Integer> li = new ArrayList<>();
int size = q.size();
for(int i =0;i<size;i++){
TreeNode curr = q.poll();
li.add(curr.val);
if(curr.left!=null)
q.add(curr.left);
if(curr.right!=null)
q.add(curr.right);
}
output.add(li);
}
return output;
} }
- Binary Tree Zigzag Level Order Traversal
Solved
Medium
Topics
Companies
Given the root of a binary tree, return the zigzag level order traversal of its nodes’ values. (i.e., from left to right, then right to left for the next level and alternate between).
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
List<List<Integer>> output = new ArrayList<>();</Integer>
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
Stack<TreeNode> currStack = new Stack<>();
Stack<TreeNode> nextStack = new Stack<>();
boolean isLeftToRight = false;
currStack.push(root);
while (!currStack.isEmpty() || !nextStack.isEmpty()) {
List<Integer> li = new ArrayList<>();
while (!currStack.isEmpty()) {
TreeNode currNode = currStack.pop();
li.add(currNode.val);
if (isLeftToRight == true) {
if (currNode.right != null)
nextStack.push(currNode.right);
if (currNode.left != null)
nextStack.push(currNode.left);
} else {
if (currNode.left != null)
nextStack.push(currNode.left);
if (currNode.right != null)
nextStack.push(currNode.right);
}
}
isLeftToRight = !isLeftToRight;
output.add(li);
if (!nextStack.isEmpty()) {
currStack = nextStack;
nextStack = new Stack<>();
}
}
return output;
} }
- Maximum Level Sum of a Binary Tree
Solved
Medium
Topics
Companies
Hint
Given the root of a binary tree, the level of its root is 1, the level of its children is 2, and so on.
Return the smallest level x such that the sum of all the values of nodes at level x is maximal.
Example 1:
Input: root = [1,7,0,7,-8,null,null]
Output: 2
Explanation:
Level 1 sum = 1.
Level 2 sum = 7 + 0 = 7.
Level 3 sum = 7 + -8 = -1.
So we return the level with the maximum sum which is level 2.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int maxLevelSum(TreeNode root) {
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
int maxSum = Integer.MIN_VALUE;
int level = 0;
int storeLevel = 0;
while (!q.isEmpty()) {
int sum = 0;
int size = q.size();
level++;
for (int i = 0; i < size; i++) {
TreeNode curr = q.poll();
sum = sum + curr.val;
if (curr.left != null)
q.add(curr.left);
if (curr.right != null)
q.add(curr.right);
}
if (maxSum < sum) {
maxSum = sum;
storeLevel = level;
}
}
return storeLevel;
} }
- Course Schedule
Solved
There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.
For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
Return true if you can finish all courses. Otherwise, return false.
Example 1:
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.
Example 2:
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
Map<Integer, List<Integer>> hm = new HashMap<>();</Integer>
for (int i = 0; i < prerequisites.length; i++) {
int dest = prerequisites[i][0];
int from = prerequisites[i][1];
if (!hm.containsKey(from)) {
hm.put(from, new ArrayList<>());
List<Integer> li = hm.get(from);
li.add(dest);
hm.put(from, li);
} else {
List<Integer> li = hm.get(from);
li.add(dest);
hm.put(from, li);
}
}
int[] degreeIngress = new int[numCourses];
for (int i = 0; i < prerequisites.length; i++) {
int dest = prerequisites[i][0];
degreeIngress[dest] = degreeIngress[dest] + 1;
}
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < degreeIngress.length; i++) {
if (degreeIngress[i] == 0) {
q.add(i);
}
}
while (!q.isEmpty()) {
int num = q.poll();
List<Integer> li = hm.get(num);
if (li != null) {
for (int i = 0; i < li.size(); i++) {
int val = li.get(i);
degreeIngress[val] = degreeIngress[val] - 1;
if (degreeIngress[val] == 0) {
q.add(val);
}
}
}
}
for (int i = 0; i < degreeIngress.length; i++) {
if (degreeIngress[i] != 0) {
return false;
}
}
return true;
} }
- Maximum Depth of Binary Tree
Easy
Given the root of a binary tree, return its maximum depth.
A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: 3
class Solution {
int count = 0;
public int maxDepth(TreeNode root) {
int count = dfs(root);
return count;
}
public int dfs(TreeNode root){
if(root == null){
return 0 ;
}
return 1+Math.max(dfs(root.left), dfs(root.right));
}
}
