rectangleSum - Interview question of the week from rendezvous with cassidoo
This one was tricky to stay mindful of the number of iterations.
Interview question of the week
This week’s question: Given a 2D array
n
of integers, and an arraym
of four (4) coordinates that represent corners of a rectangle inn
, return the sum of all of the numbers in the rectangle.Example:
n = [6, 9, -7, 3, 8, -1, -6, -4, 2, -7, 7, -7, -1, 4, 7, 9] m = [-1, 8, -7, 2] > rectangleSum(n, m) > 2 > rectangleSum(n, [6, 3, 2, -7]) > 3
My solution
/**
* Returns the sum of all of the numbers n in the rectangle m
* @param {Array<number>} n Array of numbers assumed to represent a square 2D matrix (equal rows and columns)
* @param {Array<number>} m Array of four numbers existing in m that represent a rectangle
* @returns {number} sum of all numbers n in rectangle m; null if rectangle m could not be found
*/
function rectangleSum(n, m) {
const nSide = Math.sqrt(n.length);
const [a, b, c, d] = m;
const indices = {
a: [],
b: [],
c: [],
d: [],
};
n.forEach((v, i) => {
let acc;
if (v === a) {
acc = indices.a;
} else if (v === b) {
acc = indices.b;
} else if (v === c) {
acc = indices.c;
} else if (v === d) {
acc = indices.d;
} else {
return;
}
acc.push({
x: i % nSide,
y: Math.floor(i / nSide),
});
});
function getBounds(...corners) {
let xMin = nSide;
let yMin = nSide;
let xMax = 0;
let yMax = 0;
for (const { x, y } of corners) {
xMin = Math.min(xMin, x);
xMax = Math.max(xMax, x);
yMin = Math.min(yMin, y);
yMax = Math.max(yMax, y);
}
return {
xMin,
xMax,
yMin,
yMax,
area: (xMax - xMin) * (yMax - yMin),
};
}
const validBounds = [];
for (const a of indices.a) {
for (const b of indices.b) {
for (const c of indices.c) {
for (const d of indices.d) {
if (a.x === b.x) {
if (a.y === c.y) {
if (b.y === d.y) {
validBounds.push(getBounds(a, b, c, d));
}
} else if (b.y === c.y) {
if (a.y === d.y) {
validBounds.push(getBounds(a, b, c, d));
}
}
} else if (a.y === b.y) {
if (a.x === c.x) {
if (b.x === d.x) {
validBounds.push(getBounds(a, b, c, d));
}
} else if (b.x === c.x) {
if (a.x === d.x) {
validBounds.push(getBounds(a, b, c, d));
}
}
} else {
if (a.x === c.x && b.y === c.y) {
if (b.x === d.x && a.y === d.y) {
validBounds.push(getBounds(a, b, c, d));
}
} else if (b.x === c.x && a.y === c.y) {
if (a.x === d.x && b.y === d.y) {
validBounds.push(getBounds(a, b, c, d));
}
}
}
}
}
}
}
if (validBounds.length === 0) return null;
validBounds.sort(
(a, b) => -(a.area === b.area ? 0 : a.area < b.area ? -1 : 1) // Descending sort
);
const [bounds] = validBounds;
let result = 0;
for (let x = bounds.xMin; x <= bounds.xMax; x++) {
for (let y = bounds.yMin; y <= bounds.yMax; y++) {
const i = y * nSide + x;
result += n[i];
}
}
return result;
}
const n = [6, 9, -7, 3, 8, -1, -6, -4, 2, -7, 7, -7, -1, 4, 7, 9];
console.log(
"rectangleSum(n, [-1, 8, -7, 2]) should be 2: ",
rectangleSum(n, [-1, 8, -7, 2])
);
console.log(
"rectangleSum(n, [6, 3, 2, -7]) should be 3: ",
rectangleSum(n, [6, 3, 2, -7])
);
// Extra tests
console.log(
"rectangleSum(n, [8, -7, -1, 2]) should be 2: ",
rectangleSum(n, [8, -7, -1, 2])
);
console.log(
"rectangleSum(n, [8, -7, 2, -1]) should be 2: ",
rectangleSum(n, [8, -7, 2, -1])
);
console.log(
"rectangleSum([9, -7, 2, 1], [8, -7, 2, -1]) should be null: ",
rectangleSum([9, -7, 2, 1], [8, -7, 2, -1])
);