Problem Statement # Given a binary tree, your goal is to install cameras on the tree nodes in such a way that every node in the tree is monitored. A camera at a node can monitor its parent, itself, and its immediate children. Calculate the minimum number of cameras needed to monitor all nodes of the given binary tree. Note: Every node has at most one parent. Tree nodes are numbered uniquely. ...
Problem Statement # You are designing an algorithm for an elevator system in a skyscraper without accessing specific floors marked as special. Given a list of special floors specialFloors and two integers bottom and top indicating the lowest and highest floors you’re allowed to visit, return the maximum number of consecutive floors you can visit between bottom and top without stopping at any special floor. Special floors are guaranteed to be within the range of bottom to top. ...
Problem Statement # Given a directed graph with n nodes labeled from 0 to n-1, and a list of edges where edges[i] = [ai, bi] represents a directed edge from node ai to node bi, determine if the graph contains a cycle. A cycle occurs if a node can be visited more than once by following the directed edges. Return true if the graph contains at least one cycle, otherwise return false. ...
Problem Statement # Given a weighted undirected graph with n vertices numbered from 0 to n-1, represented by an array edges where edges[i] = [from_i, to_i, weight_i] denotes a bidirectional and weighted edge between nodes from_i and to_i. Each node has a value values[i] representing its value. You start traversing the graph from node 0 and collect values. You can visit each node at most once. However, you can revisit node 0 any number of times. ...
Problem Statement # Given an integer array nums and an integer k, return true if it is possible to divide this array into k non-empty subsets whose sums are all equal. Example: Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4 Output: True Explanation: It’s possible to divide it into 4 subsets (5), (1, 4), (2, 3), (2, 3) with equal sums. Solution Approach # The solution involves using depth-first search (DFS) and backtracking to try and create k subsets with equal sums. ...
Problem Statement # Given an undirected, connected tree with n nodes labeled from 0 to n - 1, and an array edges where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi, return an array answer of length n where answer[i] is the sum of the distances between the i-th node and all other nodes. Example: Input: n = 6, edges = [[0,1], [0,2], [2,3], [2,4], [2,5]] Output: [8, 12, 6, 10, 10, 10] Explanation: The tree is shown as follows: 0 / 1 2 /| ...
Problem # Given a network represented as a graph with n nodes labeled from 0 to n-1 and an array connections where connections[i] = [a, b] indicates that there is a bidirectional road between nodes a and b, your task is to find the node that, if removed, would minimize the connectivity of the network. The connectivity of a network is defined as the number of nodes that are reachable from any node. ...
Problem # You are given a 2D grid map of '1's (land) and '0's (water). An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are surrounded by water. Write an algorithm to find the perimeter of the island in the grid. If there are multiple islands, calculate the perimeter of the largest one. ...
Problem # Given a binary tree where each node can either be 0 or 1, each root-to-leaf path represents a binary number. A leaf is a node with no children. The root is the top node of the tree. Calculate the sum of these numbers. Example: # Input: 1 / \ 0 1 / \ / \ 0 1 0 1 Output: 22 Explanation: The binary numbers are 100, 101, 110, and 111, which sum to 22. ...
Problem # Given the root of a binary tree, find the length of the longest consecutive sequence path. The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path needs to be from parent to child (cannot be the reverse). Example: # 1 \ 3 / \ 2 4 \ 5 Longest consecutive sequence path is 3-4-5, so return 3. ...
Problem # Given a binary tree (not a binary search tree) and two nodes values, find the lowest common ancestor (LCA) of the two nodes in the tree. The lowest common ancestor is defined between two nodes p and q as the lowest node in the tree that has both p and q as descendants (where we allow a node to be a descendant of itself). Example # Input: Root of the Binary Tree, p = 5, q = 1 3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4 Output: 3 Explanation: The LCA of nodes 5 and 1 is 3. ...
Problem # Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph. Example: # Input: n = 5, edges = [[0, 1], [1, 2], [3, 4]] Output: 2 Explanation: There are two connected components: 0-1-2 and 3-4. Solution # Algorithm: Depth-First Search (DFS) ...
Problem # Given a directed graph, write a function to detect whether the graph contains a cycle. Example: Input: Graph with edges [[0, 1], [1, 2], [2, 0]] Output: True (There is a cycle 0 -> 1 -> 2 -> 0) Solution # Algorithm: Depth-First Search (DFS) Use DFS to detect the presence of a cycle in the graph. The idea is to traverse the graph along a particular path and if during the traversal we revisit a node, then there is a cycle in the graph. ...
Problem # Given a binary tree, determine if it is height-balanced. In this context, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differs by more than one. Example: # Consider the following binary tree: 3 / \ 9 20 / \ 15 7 Output: True Explanation: This binary tree is balanced as the heights of the left and right subtrees of every node differ by no more than 1. ...
Problem # find the maximum sum of values in a binary tree where each node has a value and two children. The goal is to find the maximum sum of values that can be obtained by traveling upwards from a leaf to the root. Solution # Here’s the Python code to design an efficient algorithm that finds the maximum sum of values from a leaf to the root in a binary tree: ...
Problem # Given a binary tree, partition it into two subtrees such that the sum of values in the left subtree is equal to the sum of values in the right subtree. If multiple answers exist, return any one. If no answer exists, return NULL. Solution # class TreeNode: def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = right def partition_tree(root): if not root: return None, None # Calculate sum of all nodes in the tree total_sum = sum_tree(root) # Find the target sum for the left subtree target_sum = total_sum // 2 # Search for the target sum in the tree left_subtree, right_subtree = find_target_subtree(root, target_sum) # Check if a valid partition exists if left_subtree and sum_tree(left_subtree) == target_sum: return left_subtree, right_subtree return None, None def sum_tree(root): if not root: return 0 return root. ...
Problem # Given a 2D grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. Solution 1 # Here’s the Python code to count the number of islands in a 2D grid map, where ‘1’s represent land and ‘0’s represent water: def numIslands(grid): if not grid: return 0 rows, cols = len(grid), len(grid[0]) visited = set() islands = 0 def dfs(r, c): # If the current cell is out of bounds, water, or already visited, return if (r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0' or (r, c) in visited): return # Mark the cell as visited visited. ...
Problem # Design an algorithm to serialize a binary tree into a string and deserialize that string back into the original tree structure. Solution # To solve the problem of serializing and deserializing a binary tree, we can use a preorder traversal to serialize the tree. During serialization, we’ll represent null nodes as a specific marker (e.g., ‘X’). For deserialization, we can use the serialized string and rebuild the tree by following the order of elements. ...
Problem # Given a 2D board of letters and a target word, find all occurrences of the word in the board. Solution # Below is the complete Python code for the function find_word_occurrences, which finds all occurrences of a given word in a 2D board of letters. You can use this code in your Python environment: def find_word_occurrences(board, word): if not board or not word: return [] def dfs(board, word, index, x, y): if index == len(word): return True if x < 0 or x >= len(board) or y < 0 or y >= len(board[0]) or board[x][y] ! ...