Frontend School

Count Connected Delivery Hub Groups

DSA
easy

Count Connected Delivery Hub Groups

Easy
Union Find
Graph
Data Structures

Overview

Shiprocket operates a vast network of delivery hubs. Efficiently managing these hubs often requires understanding their connectivity. For instance, if a road network connects two hubs, they belong to the same operational group. This problem challenges you to determine the total number of distinct operational groups within our network, given a set of hubs and their direct connections.

What you need to do / Task

Your task is to implement a function countConnectedHubGroups that takes the total number of delivery hubs and a list of direct connections between them. You must return the total number of distinct connected groups of hubs.

  1. Initialize a data structure to represent n hubs, where each hub initially forms its own group.
  2. Process each given connection: if two hubs are connected, merge their respective groups.
  3. After processing all connections, count the total number of distinct groups remaining.

Input & output

  • Input:
    • n: An integer representing the total number of delivery hubs. Hubs are indexed from 0 to n-1.
    • connections: An array of arrays, where each inner array [u, v] denotes a direct connection between hub u and hub v.
  • Output:
    • An integer representing the total number of distinct connected groups of hubs.

Clarifications

  • A connection [u, v] implies u and v are directly connected. This connection is bi-directional.
  • If u and v are already in the same group, processing [u, v] should not change the number of groups.
  • Hubs are 0-indexed.

Examples

1

Example 1

Input:

n = 5, connections = [[0,1], [1,2], [3,4]]

Output:

2

Note:

Hubs {0,1,2} form one connected group. Hubs {3,4} form another connected group. There are 2 distinct groups.

2

Example 2

Input:

n = 4, connections = [[0,1], [2,3], [0,2]]

Output:

1

Note:

Connections [0,1], [2,3], and [0,2] eventually connect all hubs {0,1,2,3} into a single group.

3

Example 3

Input:

n = 3, connections = []

Output:

3

Note:

With no connections, each hub {0}, {1}, {2} remains in its own distinct group. There are 3 distinct groups.

Constraints

Constraints & assumptions

  • 1 <= n <= 10^4
  • 0 <= connections.length <= 10^5
  • connections[i].length == 2
  • 0 <= u, v < n
  • u != v
  • The input connections might contain duplicate connections, but they should be handled gracefully (i.e., not affect the final count of groups if the hubs are already connected).
  • The solution should be efficient enough for the given constraints.

What interviewers evaluate

  • Correct implementation of the Union-Find data structure (find with path compression, union by rank/size).
  • Ability to correctly initialize and process connections to form groups.
  • Accurate counting of distinct connected components.
  • Time and space complexity analysis and optimization.

Loading editor...