1000HardArrayMathSortingMatrix

Where to Set the Muster Point

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A yard is given as the grid grid, where 1 marks a cell holding a worker and 0 marks an empty cell.

A worker walks one cell at a time to a cell sharing an edge with the current one, so walking between two cells costs the rows between them plus the columns between them.

Choose one cell as the muster point and add up how far every worker walks to reach it. Return the smallest total any choice of cell gives. The muster point may be any cell of the yard, whether a worker stands on it or not.

Examples

Example 1

Input: grid = [[1, 0, 0], [0, 0, 0], [0, 0, 1]]
Output: 4

The two workers stand in opposite corners. Every cell lying on a shortest walk between them costs the same, so the centre serves as well as either corner, and the total is the four steps that separate the two workers.

Example 2

Input: grid = [[1, 0, 1], [0, 0, 0], [1, 0, 1]]
Output: 8

Four workers at the corners of the yard. The two rows apart pair up for two steps, and so do the two columns, twice over, so any cell inside the square they mark costs eight steps altogether.

Example 3

Input: grid = [[1, 1, 1]]
Output: 2

All three workers share a row, so only columns matter. Mustering on the middle worker's cell costs one step from each side and nothing from the middle.

Constraints

1 <= grid.length <= 200
1 <= grid[i].length <= 200
0 <= grid[i][j] <= 1
At least two cells hold a worker.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def min_total_distance(grid: list[list[int]]) -> int:

Java

public int minTotalDistance(int[][] grid)

The intended approach

Time O(m * n) over the grid's cells.Space O(m + n) for the two lists of positions.

The walking cost comes apart neatly. How many rows a worker crosses does not depend on which column the muster point sits in, and how many columns it crosses does not depend on the row. So the total is a row part plus a column part, and each may be made as small as it goes with no regard for the other. That leaves one question, asked twice: given positions along a line, which point makes the summed distance smallest? Pair the outermost two positions. Every point between them costs exactly the gap between them, and every point outside costs more, so the pair prefers anything in between and is indifferent within it. Strip that pair away and repeat on what is left; the choices only narrow, never conflict, so some middle position suits every pair at once and the smallest total is the sum of those outermost gaps taken pair by pair inward. Gather the workers' rows by sweeping the grid row by row, which yields them already in increasing order, and gather their columns by sweeping column by column, likewise in order. Then walk each list inward from both ends, adding gaps. No sorting is needed.

Pythonentry point: min_total_distance

def min_total_distance(grid):
    rows = len(grid)
    cols = len(grid[0])
    down = []
    for r in range(rows):
        for c in range(cols):
            if grid[r][c]:
                down.append(r)
    across = []
    for c in range(cols):
        for r in range(rows):
            if grid[r][c]:
                across.append(c)
    total = 0
    for line in (down, across):
        lo = 0
        hi = len(line) - 1
        while lo < hi:
            total += line[hi] - line[lo]
            lo += 1
            hi -= 1
    return total

The obvious version

Try every cell of the yard as the muster point in turn, adding up each worker's walk to it, and keep the smallest total seen. Costs the cells times the workers rather than two ordered lists walked inward.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_min_total_distance(grid):
    rows = len(grid)
    cols = len(grid[0])
    spots = []
    for r in range(rows):
        for c in range(cols):
            if grid[r][c]:
                spots.append((r, c))
    best = None
    for r in range(rows):
        for c in range(cols):
            total = 0
            for wr, wc in spots:
                total += abs(wr - r) + abs(wc - c)
            if best is None or total < best:
                best = total
    return best

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in