How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Applied Intuition.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Applied Intuition during technical interviews.

Find grid cell minimizing sum distances | Applied Intuition Coding Question

Find grid cell minimizing sum distances

Company: Applied Intuition

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

You are given an m x n 2D grid with k marked points. Movement is allowed in four directions (up, down, left, right) with unit cost per step. Find a grid cell whose sum of shortest-path distances to all marked points is minimized; if any marked point is unreachable from every cell, return -1. Implement a brute-force BFS-based solution that computes these distances, return both the minimum total distance and one optimal cell, and analyze time and space complexity. Discuss when multi-source BFS or using coordinate medians (if there are no obstacles) can reduce complexity.

Quick Answer: This question evaluates proficiency in grid-based graph traversal and shortest-path computation using BFS, reachability analysis from multiple marked points, and algorithmic time/space complexity reasoning.

You are given a rectangular grid where -1 represents a blocked cell, 0 represents an empty traversable cell, and 1 represents a marked point. You may move up, down, left, or right between non-blocked cells with cost 1 per step. For any traversable cell, define its cost as the sum of its shortest-path distances to all marked points. Return the minimum possible cost and one optimal cell as `(min_total_distance, (row, col))`. If multiple cells are optimal, return the lexicographically smallest `(row, col)`. If no traversable cell can reach every marked point, return `-1`. For this version, implement the brute-force approach: try every traversable cell as the meeting cell and run BFS from it to compute distances. As a follow-up, discuss why reversing the searches and running BFS from each marked point can reduce the work, why a simultaneous multi-source BFS is only enough for nearest-source-style objectives, and why in a grid with no obstacles the optimal row and column are given by the medians of the marked coordinates.

Constraints

1 <= m, n <= 30
grid[i][j] is one of -1, 0, or 1
There is at least one marked cell
Movement is allowed only through cells whose value is not -1

Examples

Input: ([[1,0,0],[0,1,0],[0,0,1]],)

Expected Output: (4, (1, 1))

Explanation: Cell (1, 1) reaches the three marked cells in distances 2, 0, and 2, for a total of 4, which is minimal.

Input: ([[1,-1,0,0],[0,-1,0,1],[0,0,1,0]],)

Expected Output: (6, (2, 2))

Explanation: Obstacles force paths around the blocked cells; from (2, 2) the distances to the marks are 4, 2, and 0, summing to 6.

Input: ([[1,-1,1]],)

Expected Output: -1

Explanation: The obstacle splits the two marked cells into different connected components, so no traversable cell can reach both.

Input: ([[1]],)

Expected Output: (0, (0, 0))

Explanation: The only cell is already marked, so the minimum total distance is 0 at (0, 0).

Input: ([[1,0,1]],)

Expected Output: (2, (0, 0))

Explanation: All three traversable cells have total distance 2 to the two marks, so the lexicographically smallest optimal cell is (0, 0).

Solution

def solution(grid):
    from collections import deque

    if not grid or not grid[0]:
        return -1

    m, n = len(grid), len(grid[0])
    candidates = []
    mark_count = 0

    for r in range(m):
        for c in range(n):
            if grid[r][c] != -1:
                candidates.append((r, c))
            if grid[r][c] == 1:
                mark_count += 1

    if not candidates or mark_count == 0:
        return -1

    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
    best_total = None
    best_cell = None

    for start_r, start_c in candidates:
        visited = [[False] * n for _ in range(m)]
        visited[start_r][start_c] = True
        queue = deque([(start_r, start_c, 0)])
        found_marks = 0
        total = 0
        valid = False

        while queue:
            r, c, dist = queue.popleft()

            if grid[r][c] == 1:
                total += dist
                found_marks += 1

                if found_marks == mark_count:
                    valid = True
                    break

                if best_total is not None and total > best_total:
                    queue.clear()
                    break

            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n and not visited[nr][nc] and grid[nr][nc] != -1:
                    visited[nr][nc] = True
                    queue.append((nr, nc, dist + 1))

        if valid:
            if best_total is None or total < best_total:
                best_total = total
                best_cell = (start_r, start_c)

    if best_total is None:
        return -1

    return (best_total, best_cell)

Time complexity: O(T * m * n), where T is the number of non-blocked cells; in the worst case this is O((m*n)^2). Space complexity: O(m * n).

Hints

Because every move has the same cost, shortest paths from one cell to all others in an unweighted grid are found with BFS.
For the required brute-force solution, iterate over every non-blocked cell, run BFS, add distances when marked cells are first reached, and keep the best total. Scanning cells row by row naturally handles lexicographic tie-breaking.

Quick Overview

This question evaluates proficiency in grid-based graph traversal and shortest-path computation using BFS, reachability analysis from multiple marked points, and algorithmic time/space complexity reasoning.