Frontend School

Ola Inter-City Network Optimization

DSA
hard

Ola Inter-City Network Optimization

Hard
Union Find
Graph
Minimum Spanning Tree

Overview

Ola is rapidly expanding its autonomous vehicle network across various cities. To ensure seamless operations and robust service delivery, it's crucial to establish reliable connectivity within distinct geographical regions. This problem challenges you to design an efficient algorithm that optimizes road construction costs to achieve the necessary connectivity for each defined region.

What you need to do / Task

Implement a function calculateRegionConnectivityCosts that determines the minimum total cost of building roads to connect all cities within each specified region.

  1. For each distinct region, all cities belonging to that region must form a single connected component.
  2. The total cost for a region is the sum of costs of roads selected that contribute to connecting its cities.
  3. Return an array where the i-th element represents the minimum connectivity cost for region i.

Input & output

  • N: An integer, representing the total number of cities (0 to N-1).

  • regionIds: An array of integers regionIds[i] where regionIds[i] specifies the region ID (0 to K-1) to which city i belongs. Each city belongs to exactly one region.

  • roads: A 2D array of integers [[u, v, cost], ...] representing potential roads. u and v are city indices (0 to N-1), and cost is the non-negative integer cost to build a road between them. Roads are undirected.

  • Returns: An array of long integers of size K (where K is the number of distinct regions, determined by the maximum region ID in regionIds + 1). result[i] should be the minimum cost to connect all cities in region i. If a region contains only one city, its connectivity cost is 0.

Clarifications

  • Cities and region IDs are 0-indexed.
  • Roads can connect cities belonging to different regions. Such roads are considered for connectivity if they are part of the cheapest path to connect cities within a specific region.
  • The minimum cost for a region implies finding a Minimum Spanning Tree (MST) for the subgraph induced by the cities of that region, considering only relevant edges.

Examples

1

Example 1

Input:

N = 4, regionIds = [0, 0, 1, 1], roads = [[0, 1, 10], [1, 2, 5], [2, 3, 8]]

Output:

[10, 8]

Note:

Region 0 has cities {0, 1}. The road (0,1) with cost 10 connects them. Region 1 has cities {2, 3}. The road (2,3) with cost 8 connects them. The road (1,2) connects cities from different regions and is not needed for intra-region connectivity.

2

Example 2

Input:

N = 5, regionIds = [0, 0, 0, 1, 1], roads = [[0, 1, 10], [1, 2, 5], [0, 2, 12], [3, 4, 7], [1, 3, 20]]

Output:

[15, 7]

Note:

Region 0 has cities {0, 1, 2}. To connect them, we consider roads (1,2,5) and (0,1,10). Total cost: 5 + 10 = 15. The road (0,2,12) is redundant as (0,1,2) already forms a path 0-1-2 with lower total cost. Region 1 has cities {3, 4}. Road (3,4,7) connects them for a cost of 7. Road (1,3,20) connects cities from different regions.

3

Example 3

Input:

N = 6, regionIds = [0, 1, 0, 1, 2, 2], roads = [[0,2,10], [1,3,5], [0,1,1], [2,3,2], [4,5,15]]

Output:

[5, 5, 15]

Note:

Cities by region: R0={0,2}, R1={1,3}, R2={4,5}. Sorted roads by cost: (0,1,1), (2,3,2), (1,3,5), (0,2,10), (4,5,15).

  1. (0,1,1): Connects city 0 (R0) and city 1 (R1). No intra-region cost added.
  2. (2,3,2): Connects city 2 (R0) and city 3 (R1). No intra-region cost added.
  3. (1,3,5): Connects city 1 (R1) and city 3 (R1). Both are from R1. This edge connects cities 1 and 3 within R1. Cost for R1 becomes 5. This edge also connects city 0 (via 1) and city 2 (via 3), effectively connecting two sub-components of R0 (one containing city 0, another containing city 2). So, cost for R0 becomes 5. Both R0 and R1 are now fully connected.
  4. (0,2,10): Cities 0 and 2 are already connected via 0-1-3-2 with a total path cost of 1+5+2=8. This edge is not needed.
  5. (4,5,15): Connects city 4 (R2) and city 5 (R2). Cost for R2 becomes 15. Final costs: R0=5, R1=5, R2=15.

Constraints

Constraints & assumptions

  • 1 <= N <= 10^5
  • 1 <= K <= N (where K is the number of distinct regions)
  • 0 <= regionIds[i] < K for all i
  • 0 <= M <= 2 * 10^5 (number of potential roads)
  • 0 <= u, v < N, u != v for any road [u, v, cost]
  • 0 <= cost <= 10^9 for any road
  • The sum of N over all test cases will not exceed 5 * 10^5.
  • The sum of M over all test cases will not exceed 5 * 10^5.
  • Costs can sum up to values exceeding 2^31 - 1, so use 64-bit integers (long in Java/C++, number in JS/TS) for total costs.

What interviewers evaluate

  • Correctness: The solution accurately calculates the minimum connectivity cost for all regions.
  • Algorithm Design: Demonstrates a clear understanding and correct application of an advanced Union-Find data structure to solve a multi-component MST problem.
  • Efficiency: Achieves optimal time and space complexity, utilizing techniques like path compression and union-by-size/rank, along with efficient merging of component-specific data.
  • Code Quality: Writes clean, well-structured, and readable code with appropriate data structures and variable naming.

Loading editor...