thzinc

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 array m of four (4) coordinates that represent corners of a rectangle in n, 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])
);

See also