Good morning! Here's our prompt for today.
You are given a 2D matrix with several characters contained in its cells. You will also have two distinct characters which are guaranteed to be in the given matrix. Your job will be to find the minimum manhattan distance between the two characters in the matrix.
The manhattan distance of two points (x1, y1)
and (x2, y2)
is |x1-x2|+|y1-y2|
. In other words, it is the distance between two points measured along axes at right angles.

For example in the above image:
The result will be 2
, because the minimum distance is from A(4,3)
to B(2,3)
-- which is 2. Note, for the points of the graph, we respect the programming version and use a 0-index.
Constraints
- Minimum Size of Matrix:
2
cells (e.g.1x2
or2x1
) - Maximum Size of Matrix:
10^8
cells (e.g.10^4x10^4
) - The given 2 characters are guaranteed to appear at least once in the matrix.
- Expected Time Complexity:
O(m*n)
where m and n are the height and width of matrix. - Expected Space Complexity:
O(m*n)
.
Try to solve this here or in Interactive Mode.
How do I practice this challenge?
xxxxxxxxxx
69
"The below matrix with A='A' and B='B' should return 2.let matrix = [ ['A', 'A', 'A', 'x', 'B'], ['x', 'A', 'x', 'B', 'x'], ['x', 'x', 'x', 'B', 'x'], ['A', 'x', 'B', 'x', 'x'], ['x', 'A', 'x', 'B', 'B'],];"
var assert = require('assert');
​
function smallestDist(matrix, A, B) {
// Fill in
}
​
try {
let matrix = [
['x', 'x', 'A', 'x', 'B'],
['x', 'A', 'x', 'x', 'x'],
['x', 'x', 'x', 'B', 'x'],
['A', 'x', 'x', 'x', 'x'],
['x', 'A', 'x', 'A', 'A'],
];
let result = smallestDist(matrix, 'A', 'B');
assert.equal(2, result, 'Wrong Answer');
​
console.log(
'PASSED: ' +
"The below matrix with A='A' and B='B' should return 2.let matrix = [ ['x', 'x', 'A', 'x', 'B'], ['x', 'A', 'x', 'x', 'x'], ['x', 'x', 'x', 'B', 'x'], ['A', 'x', 'x', 'x', 'x'], ['x', 'A', 'x', 'A', 'A'],]"
);
} catch (err) {
console.log(err);
}
​
try {
let matrix = [
['A', 'A', 'A', 'x', 'B'],
['x', 'A', 'x', 'B', 'x'],
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
Here's our guided, illustrated walk-through.
How do I use this guide?