Skip to the code
cf.
+25 XP

#456 Build a Group Tracker

medium

A collaborative whiteboard lets users group shapes. Write a class GroupTracker for n shapes numbered 0 to n - 1, where each shape starts in its own group.

  • new GroupTracker(n) creates the tracker.
  • merge(a, b) joins the groups of a and b, and returns true if they were in different groups before, false if they were already together.
  • together(a, b) returns true if a and b are in the same group.
  • groupCount() returns the number of groups.
  • groupSize(a) returns how many shapes are in a's group.

Every method should run in nearly constant time.

Each example lists the calls in order, then each call's arguments. The first call creates the object with new GroupTracker(…); the output lists what each call returns (null for the constructor and for methods that return nothing).

Example 1

Input: ["GroupTracker","merge","together","groupCount","groupSize"]
[[4],[0,1],[1,0],[],[1]]
Output: [null,true,true,3,2]

After merging 0 and 1, they are together, there are 3 groups ({0, 1}, {2}, {3}), and 1's group has 2 shapes.

Example 2

Input: ["GroupTracker","merge","merge","merge","groupCount","together"]
[[3],[0,1],[1,2],[2,0],[],[0,2]]
Output: [null,true,true,false,1,true]

The third merge finds 2 and 0 already in one group, so it returns false.

Constraints

  • 1 <= n <= 100000
  • At most 100000 method calls.
  • 0 <= a, b < n
Saved in this browser

Run tries your code on the examples. Submit runs every test, including hidden edge cases, and solves the problem when they all pass.

Ctrl + Enter runs, Ctrl + Shift + Enter submits (⌘ on a Mac).