1.
Building Distance Analysis
A logistics company has a network of distribution centers arranged in
a grid with n rows and m columns. Each cell in this grid contains a
distribution center identified by its center ID, represented as an
integer from 1 to 100,000.
The company wants to analyze the travel cost between all distribution
centers of the same ID. The travel cost between two centers located at
(r1, c1) and (r2, c2) is defined by the Manhattan distance: the shortest
path moving horizontally or vertically between them. For example, in
a 3×4 grid, the Manhattan distance between (1, 2) and (3, 3) is 3, and
one possible path is: (1, 2)-> (2, 2)→ (2, 3)→ (3, 3).
The task is to calculate the sum of the Manhattan distances between
each pair of distribution centers with the same ID for every ID in the
grid.
The input contains two integers n and m (1 ≤ n, m, and n * m ≤
100,000) - the number of rows and columns in the grid.
The next n lines describe the grid. Each line contains m integers
representing the IDs of the distribution centers in the corresponding
row, where each ID is an integer between 1 and 100,000.
Function description
Complete the solve function in the editor below. It has the following
parameter(s):
Name Type Description
n number of rows in
INTEGER the grid.
m INTEGER number of columns
in the grid.
a INTEGER 2D n lines describe the
ARRAY grid. Each line
contains m integers
representing the IDs
of the distribution
centers in the
corresponding row,
where each ID is an
integer between 1
and 100,000.
Return
The function must return an INTEGER denoting the sum of the
Manhattan distances between each pair of distribution centers with the
same ID for every ID in the grid.
Constraints
• 1 ≤n≤ 10^5
• 1 ≤m≤ 10^5
1 ≤ a[i][j] ≤ 10^5
Input format for debugging
• The first line contains an integer, n, denoting the number of rows in
a.
• The next line contains an integer, m, denoting the number of
columns in a.
• Each line i of the n subsequent lines (where 0 ≤ I < n) contains m
space separated integers each describing the row a[i].
Sample Testcases
Input Output Output Description
4 129 (1,1), (1,2),
4 (2,2),(2,3), (3,2),
112 (3,4), (4,1), (4,2),
3 (4,4)
211 Sum of Manhattan
2 Distances:98.
312 For ID 2:
1 (1,3),(2,1),(2,4),
112 (3,3),(4,3)
1 Dist: 26
For ID 3:
(1,4), (3,1)
Dist:5
Total: 98+26+5=129
2 7 There are three pairs
3 of cells of same ID:
123 in cells (1,1) and
321 (2,3), in cells (1,2)
and (2,2), in cells
(1,3) and (2,1). The
manhattan distances
between them are 3,
1 and 3, the sum is 7.
3 76 For ID 1:
4 (1,1), (1,2),
112 (2,2),(2,3), (3,3),
2 (3,4) Dist: 35
211 For ID 2:
2 (1,3),(1,4),(2,1),(2,4),
221 (3,1),(3,2)
1 Dist: 41
Total: 35+41=76
JAVA CODE:
import [Link].*;
public class building_distance_analysis {
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int n = [Link](); // number of rows
int m = [Link](); // number of columns
int[][] grid = new int[n][m];
// Maps to hold row and column positions per ID
HashMap<Integer, ArrayList<Integer>> rowMap = new
HashMap<>();
HashMap<Integer, ArrayList<Integer>> colMap = new
HashMap<>();
// Read the grid and fill maps
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
grid[i][j] = [Link]();
int id = grid[i][j];
[Link](id, new ArrayList<>());
[Link](id, new ArrayList<>());
[Link](id).add(i + 1); // 1-based row
[Link](id).add(j + 1); // 1-based column
}
}
long totalDistance = 0;
// For each ID, compute Manhattan distances
for (int id : [Link]()) {
ArrayList<Integer> rows = [Link](id);
ArrayList<Integer> cols = [Link](id);
[Link](rows);
[Link](cols);
totalDistance += computeDistance(rows);
totalDistance += computeDistance(cols);
}
[Link](totalDistance);
}
// Compute total distance using prefix sum trick
private static long computeDistance(ArrayList<Integer> list) {
long sum = 0;
long prefix = 0;
for (int i = 0; i < [Link](); i++) {
long val = [Link](i);
sum += val * i - prefix;
prefix += val;
}
return sum;
}
}