Friend Groups That Merge and Get Queried
Solve this ProblemSome people start out alone, and friendships then merge groups over time. You receive a list of operations: "merge the groups of a and b", or "are a and b in the same group?". Answer every operation in order: merges report the number of groups that remain, questions report 1 or 0.
A disjoint set (union-find) stores the groups as trees. Union by rank keeps the trees shallow by always hooking the shallower tree under the deeper one, and path compression flattens paths while searching.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ n ≤ 10 people numbered 0 … n-1; at the start every person is alone in their own group - ◆
ops is a list of at most 12 operations, each a row [kind, a, b] with 0 ≤ a, b < n: kind 1 means "merge the groups of a and b" (nothing happens if they are already the same group), kind 2 means "ask whether a and b are in the same group" - ◆
The operations are processed in the given order and every operation produces one answer - ◆
Return the answers: for a merge (kind 1) the number of groups that exist AFTER it, for a question (kind 2) 1 if a and b are in the same group and 0 otherwise
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Give Every Person a Group Label and Relabel on Merge
BruteKeep a group label for each person (at first their own number) and a counter of groups. To merge a and b when their labels differ, sweep over all n people and give everyone with b's label the label of a; the counter goes down by one. A question just compares two labels. Questions are instant, but every merge touches all n people.
O(n) per merge, O(1) per questionO(n)1class Solution {
2 public int[] processOps(int n, int[][] ops) {
3 int[] label = new int[n];
4 for (int i = 0; i < n; i++) label[i] = i;
5 int groups = n;
6 int[] answers = new int[ops.length];
7 for (int k = 0; k < ops.length; k++) {
8 int a = ops[k][1], b = ops[k][2];
9 if (ops[k][0] == 1) {
10 if (label[a] != label[b]) {
11 int from = label[b], to = label[a];
12 for (int i = 0; i < n; i++) {
13 if (label[i] == from) label[i] = to;
14 }
15 groups--;
16 }
17 answers[k] = groups;
18 } else {
19 answers[k] = label[a] == label[b] ? 1 : 0;
20 }
21 }
22 return answers;
23 }
24}Optimal — Disjoint Set With Union by Rank and Path Compression
OptimalStore every group as a tree: parent[x] points towards the root that represents the group. find(x) walks up to the root (shortening the path on the way, "path compression"). To merge two groups, hook the root of the SHALLOWER tree under the root of the deeper one; rank[] is an upper bound of the tree height, and it grows only when two trees of equal rank are merged. This keeps trees very flat: each operation is nearly constant time (inverse Ackermann). A question compares the two roots.
O(α(n)) per operationO(n)1class Solution {
2 private int find(int[] parent, int x) {
3 while (parent[x] != x) {
4 parent[x] = parent[parent[x]];
5 x = parent[x];
6 }
7 return x;
8 }
9
10 public int[] processOps(int n, int[][] ops) {
11 int[] parent = new int[n];
12 int[] rank = new int[n];
13 for (int i = 0; i < n; i++) parent[i] = i;
14 int groups = n;
15 int[] answers = new int[ops.length];
16 for (int k = 0; k < ops.length; k++) {
17 int ra = find(parent, ops[k][1]), rb = find(parent, ops[k][2]);
18 if (ops[k][0] == 1) {
19 if (ra != rb) {
20 if (rank[ra] < rank[rb]) {
21 parent[ra] = rb;
22 } else if (rank[ra] > rank[rb]) {
23 parent[rb] = ra;
24 } else {
25 parent[rb] = ra;
26 rank[ra]++;
27 }
28 groups--;
29 }
30 answers[k] = groups;
31 } else {
32 answers[k] = ra == rb ? 1 : 0;
33 }
34 }
35 return answers;
36 }
37}