The question

Given a matrix of integers and coordinates of a rectangular region within the matrix, find the sum of numbers falling inside the rectangle. Our program will be called multiple times with different rectangular regions from the same matrix.

My solution

Just from the question I am not completely sure what they are asking me but it sounds like I will have a matrix of integers (I will assume a 2 dimensional matrix) and then they will give me coordinates for two opposite corners and I just need to sum all numbers inside the limits of those coordinates. They also mention that the program will be called multiple times with different rectangular regions which makes me thing that I’m expected to do some kind of caching.

I spent some time thinking of how to do this in an efficient way but I couldn’t come up with something that felt right.

The best solution

Apparently the best solution involves some pre-computation in order to calculate all possible sums starting from the top left corner. The original article explains this very well.

The implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
var matrix = [
  [1, 2, 3, 4, 5, 6, 7],
  [9, 8, 7, 6, 5, 4, 3],
  [1, 1, 1, 1, 1, 1, 1],
  [0, 1, 2, 3, 2, 1, 0],
  [9, 9, 9, 9, 9, 9, 9],
  [4, 4, 4, 4, 4, 4, 4]
];

// Create an array for the sums
var sums = new Array(matrix.length);

function calculateSums() {
  var height = matrix.length;
  var width = matrix[0].length;

  for (var y = 0; y < height; y++) {
    // Add a row to the array
    sums[y] = new Array(width);
    for (var x = 0; x < width; x++) {
      // We can use a similar technique to calculate the sums based on the
      // values already in the sums matrix
      var leftSum = sums[y][x-1] || 0;
      var topSum = 0;
      var topLeftSum = 0;
      if (typeof sums[y - 1] === 'object') {
        topSum = sums[y - 1][x] || 0;
        topLeftSum = sums[y-1][x-1] || 0;
      }

      sums[y][x] = topSum + leftSum - topLeftSum + matrix[y][x];
    }
  }

  return sums;
}

function getRectangleSum(topLeft, bottomRight) {
  return sums[bottomRight[1]][bottomRight[0]] -
      sums[topLeft[1] - 1][bottomRight[0]] -
      sums[bottomRight[1]][topLeft[0] - 1] +
      sums[topLeft[1] - 1][topLeft[0] - 1];
}

// Fill sums with all possible sums starting from top left corner
calculateSums();

function test() {
  if (getRectangleSum([3, 2], [4, 3]) === 7) {
    console.log('successs');
  } else {
    console.log('failure');
  }
}

test(); // Prints success
[ application_design  computer_science  algorithms  javascript  programming  ]
Sorting algorithms computer_science algorithms javascript programming
Raft for reaching consensus computer_science algorithms
The Rabin-Karp algorithm computer_science algorithms javascript programming
Load testing a Rails app with Vegeta application_design programming
House painting problem computer_science algorithms javascript programming