CODEWITHSUNDEEP
algorithmmatrixdata-structures
Mushi Master
Mushi Master

Reputation: 65

Minimise Manhattan distance between x and y in a matrix

I'm trying to solve a question involving Manhattan distance and matrix.

Question: Given a 2D matrix with where each cell may contain either character '0' or 'x' or 'y'. Find the minimum Manhattan distance between x & y.

Manhattan distance between x & y would be |X(x) - X(y)| + |Y(x) - Y(y)|. X & Y represents row number, column number resp. of cell containing a character in matrix.

Example:

[ x, 0, 0, 0 ]
[ 0, y, 0, y ]
[ x, x, 0, 0 ]
[ 0, y, 0, 0 ]

is given and we've to compute minimum Manhattan distance between x & y; in this case it is 1 (between (3,2) and (4,2)).

A brute force approach would amount to O((m * n)^2) time, how can this be optimised to atleast O(m * n)?

Upvotes: 0

Views: 1631

Answers (3)

BonzaiThePenguin
BonzaiThePenguin

Reputation: 1433

For each cell of the matrix, the minimum Manhattan distance is just the distance to the nearest x to the left and the nearest y above it, or the nearest x to the left and the nearest y above it. O(n*m) time to scan the rows and columns and O(n) memory to track the nearest x and y in each column (compared to an O(n*m) worst case for a breadth-first search).

def distance(M):
    rows = len(M)
    cols = len(M[0])
    above_x = cols * [-1]
    above_y = cols * [-1]
    res = float('inf')
    for row in range(rows):
        left_x = -1
        left_y = -1
        for col in range(cols):
            # track the nearest x and y to the left and above
            if M[row][col] == 'x':
                above_x[col] = row
                left_x = col
            if M[row][col] == 'y':
                above_y[col] = row
                left_y = col

            # the shortest distance is just the two distances added together
            if left_y > -1 and above_x[col] > -1:
                res = min(res, (col - left_y) + (row - above_x[col]))
            if left_x > -1 and above_y[col] > -1:
                res = min(res, (col - left_x) + (row - above_y[col]))
    return res

Upvotes: 0

grodzi
grodzi

Reputation: 5703

without use of graph theory

  • put coordinates of any x_i in set x
  • put coordinates of any y_j in set y
  • apply distance on the cartesian product of x and y idem consider d(x_i, y_j) for all ij
  • keep the min

if x_s is size of X and y_s size of Y: runs in O(x_sy_s) (assuming you know where are x_i and y_j beforehand... (O(mn) otherwise)

let {x,y} = `x000,0y0y,xx00,0y00`.replace(/,/g,'').split('').reduce((acc,v,id)=>{
    let y = id%4;
    let x = (id-y)/4
    if(v=='x'||v=='y'){
        acc[v].push([x,y]);
    }
    return acc;
},{x:[],y:[]})
let d = (a,b)=>Math.abs(a[1]-b[1])+Math.abs(a[0]-b[0]);
console.log('dist:', Math.min(...x.map(v=>Math.min(...y.map(w=>d(v,w))))))

Upvotes: 0

Photon
Photon

Reputation: 2777

Its a classic graph theory problem.

First notice that Manhattan distance is just some shortest path on the grid from one cell to the other.

Then add nodes marked with x to the queue and do BFS till you visit some y node and distance to that node will be the answer.

Complexity: O(n*m)

Sample code (C++):

int n = 4;
const int inf = 1234567890;
vector<string>M = {"x000","0y0y","xx00","0y00"};
vector<vector<int>>D(n, vector<int>(n,inf));
queue<array<int,2>>Q;

for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
    if(M[i][j]=='x')
{
    Q.push({i,j});
    D[i][j]=0;
}

int res = inf;

while(!Q.empty())
{
    int row = Q.front()[0];
    int col = Q.front()[1];
    if(M[row][col]=='y')
    {
        res=D[row][col];
        break;
    }
    Q.pop();

    int dr[] = {-1,1,0,0};
    int dc[] = {0,0,-1,1};

    for(int k=0; k<4; k++)
    {
        int r = row + dr[k];
        int c = col + dc[k];
        if(min(r,c) >=0 && max(r,c) < n && D[r][c]==inf)
        {
            D[r][c]=D[row][col]+1;
            Q.push({r,c});
        }
    }
}

cout<<res;

Upvotes: 1

Related Questions