🚀

Thanksgiving Sale: Use Coupon Code THANKS25 to Get Extra 25% Off.

00DAYS
:
00HOURS
:
00MINUTES
:
00SECONDS

Leetcode Problem 2421. Number of Good Paths

2421. Number of Good Paths

Leetcode Solutions

Union-Find Approach for Counting Good Paths

  1. Create an adjacency list to store the tree structure.
  2. Create a map valuesToNodes to map each value to the list of nodes with that value, sorted by keys.
  3. Define a Union-Find class with find and union_set methods.
  4. Initialize a Union-Find instance and a variable goodPaths to count the number of good paths.
  5. Iterate over each entry in valuesToNodes in ascending order.
    • For each node, iterate over its neighbors.
    • If the neighbor's value is less than or equal to the current node's value, perform a union operation.
  6. After processing all nodes with the same value, use a map group to count the number of nodes in each component.
  7. For each component, calculate the number of good paths using the formula size * (size + 1) / 2 and add it to goodPaths.
  8. Return the value of goodPaths.
UML Thumbnail

Depth-First Search (DFS) Approach for Counting Good Paths

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...