Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

Review: Union Find Problems

Posted on August 14, 2019July 26, 2020 by braindenny

Union find is helpful to build relationship among different sets

Key operations: union, find, etc.



Basic Abstractions

Name Summary
Entities Set of objects
Union command Connect two objects or two groups
Find query Is there a path connecting one object to another?
Disjoint sets of objects Subsets of connected grid points
Union by rank vs by size link
Reference YouTube: Disjoint Sets Data Structure – Weighted Union and Collapsing Find
Reference Wikipedia: Disjoint-set data structure

Top Questions

Num Problem Summary
1 Union find for weighted graph LeetCode: Evaluate Division
2 Union find: connect groups and merge node count LeetCode: Bricks Falling When Hit

Scenarios
Union-find applications involve manipulating objects of all types:

Name Summary
Computers in a network  
Web pages on the Internet  
Transistors in a computer chip  
Variable name aliases  
Pixels in a digital photo  
Metallic sites in a composite system  
Minimum spanning tree of a graph – Kruskal’s algorithm  
What are the nodes and how to union nodes LeetCode: Largest Component Size by Common Factor
What nodes are? What edges are? LeetCode: Sentence Similarity II, LeetCode: Regions Cut By Slashes
Count node then initialize VS a fixed array LeetCode: Satisfiability of Equality Equations
Maintain a counter for group count LeetCode: Graph Valid Tree
Path compression to reduce levels Keeps tree almost completely flat, and avoid tall trees
Rank based merge Balance by linking small tree below large one
Collect result: add vs extract? LeetCode: Most Stones Removed with Same Row or Column
Get the nodes relationship quickly LeetCode: Most Stones Removed with Same Row or Column
How efficient unionfind vs DFS/BFS?  
Time and space complexity of unionfind?  

Code Skeleton

// 1. Get node count. And initialize array with parent as itself
// 2. Union: Connect two nodes, which is two groups essentially
// 3. Find: find node's parent by value
type DSU struct {
    parent []int
}

func constructor(size int) DSU {
    parent := make([]int, size)
    for i, _ := range parent {
        parent[i] = i
    }
    return DSU{parent:parent}
}

func (dsu *DSU) union(x, y int) {
    // TODO: rank based merge
    dsu.parent[dsu.find(y)] = dsu.find(x)
}

func (dsu *DSU) find(x int) int {
    // TODO: path compression
    for dsu.parent[x] != x {
        x = dsu.parent[x]
    }
    return x
}

  • CheatSheet: Leetcode For Code Interview
  • CheatSheet: Common Code Problems & Follow-ups

See all unionfind tree problems: #unionfind

  • Review: Union Find Problems
  • LeetCode: Validate Binary Tree Nodes
  • LeetCode: Sentence Similarity II
  • LeetCode: Satisfiability of Equality Equations
  • LeetCode: Redundant Connection
  • LeetCode: Path With Maximum Minimum Value
  • LeetCode: Optimize Water Distribution in a Village
  • LeetCode: Number of Islands II
  • LeetCode: Number of Connected Components in an Undirected Graph
  • LeetCode: Most Stones Removed with Same Row or Column
  • LeetCode: Majority Element II
  • LeetCode: Lexicographically Smallest Equivalent String
  • LeetCode: Largest Component Size by Common Factor
  • LeetCode: Graph Valid Tree
  • LeetCode: Friend Circles
  • LeetCode: Evaluate Division
  • LeetCode: Bricks Falling When Hit
  • LeetCode: Accounts Merge

See more blog posts.

linkedin
github
slack

Post Views: 0
Posted in ReviewTagged review, unionfind

Post navigation

LeetCode: Market Analysis II
LeetCode: Convert to Base -2

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #blog #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum binarysearch editdistance hashmap intervaldp knapsack monotone oodesign presum rectangle redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • a
  • a
  • a
  • a
  • a

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.