Posts

Connected Components in a Graph

-
Image
This problem is an interesting one—it initially looks daunting, but upon closer inspection, it turns out to be quite approachable. The solution involves two main steps: building the graph and counting the connected components. I prefer to represent graphs using a simple Hashtable, as it makes accessing and traversing the graph straightforward and efficient. Since this problem involves an undirected graph, it's important to remember to add edges in both directions, meaning both {i, j} and {j, i} must be included. Counting connected components is a classic graph problem that can be efficiently solved using Depth-First Search (DFS). The DFS approach systematically marks all vertices belonging to the same component, ensuring that each vertex is visited at most twice—resulting in a linear-time algorithm. If you're curious about the detailed analysis of the algorithm, ChatGPT 4.5 provides a thorough complexity breakdown, confirming that, given the constraints, the solution is quite...
Post a Comment
Read more

The power of pruning in backtracking IV

-
Image
Although this is marked as an easy problem, solving generically would make it a medium one. Standard backtracking but the key it to prune it: as soon as the number exceeds the min allowed, cut short the search space. Code is down below, cheers, ACC. Unique 3-Digit Even Numbers - LeetCode You are given an array of digits called  digits . Your task is to determine the number of  distinct  three-digit even numbers that can be formed using these digits. Note : Each  copy  of a digit can only be used  once per number , and there may  not  be leading zeros.   Example 1: Input:   digits = [1,2,3,4] Output:   12 Explanation:  The 12 distinct 3-digit even numbers that can be formed are 124, 132, 134, 142, 214, 234, 312, 314, 324, 342, 412, and 432. Note that 222 cannot be formed because there is only 1 copy of the digit 2. Example 2: Input:   digits = [0,2,2] Output:   2 Explanation:  The only 3-digit even numbers that ca...
Post a Comment
Read more

Spreadsheet class in O(1)-time

-
Image
Key to make this class work very fast is to use a hash table to store the elements in each cell. Notice that you don't want to create a sparse matrix otherwise this will be very memory consuming. Rows can be safely ignored. The formula calculation is a simple lookup or int conversion. Code is down below, cheers, ACC. Design Spreadsheet - LeetCode A spreadsheet is a grid with 26 columns (labeled from  'A'  to  'Z' ) and a given number of  rows . Each cell in the spreadsheet can hold an integer value between 0 and 10 5 . Implement the  Spreadsheet  class: Spreadsheet(int rows)  Initializes a spreadsheet with 26 columns (labeled  'A'  to  'Z' ) and the specified number of rows. All cells are initially set to 0. void setCell(String cell, int value)  Sets the value of the specified  cell . The cell reference is provided in the format  "AX"  (e.g.,  "A1" ,  "B10" ), where the letter represents the column (from...
Post a Comment
Read more