Take the 2-minute tour ×

I'm building a heatmap-like rectangular array interface and I want the 'hot' location to be at the top left of the array, and the 'cold' location to be at the bottom right. Therefore, I need an array to be filled diagonally like this:

    0    1    2    3
0 | 0  | 2  | 5  | 8  |
1 | 1  | 4  | 7  | 10 |
2 | 3  | 6  | 9  | 11 |

So actually, I need a function f(x,y) such that

f(0,0) = 0
f(2,1) = 7
f(1,2) = 6
f(3,2) = 11

(or, of course, a similar function f(n) where f(7) = 10, f(9) = 6, etc.).

Finally, yes, I know this question is similar to the ones asked here, here and here, but the solutions described there only traverse and don't fill a matrix.

share|improve this question
Just traverse the array and fill the current position with the current step, no? –  Ozan Jun 30 '10 at 22:16
No, one limitation is that the array is traversed row by row, from left to right. So that's why I'm looking for a function to calculate each value, instead of traversing the array in a particular manner. –  dbaw Jun 30 '10 at 22:20
So then you want to calculate f(x,y) directly, rather than filling an array? Because I see no reason why an array should need to be filled left-to-right. Because if you do fill an array like Ozan suggested, you can then just query the array for array[x][y] to find f(x,y) directly... –  BlueRaja - Danny Pflughoeft Jun 30 '10 at 23:44
add comment

5 Answers

up vote 3 down vote accepted

Interesting problem if you are limited to go through the array row by row. I divided the rectangle in three regions. The top left triangle, the bottom right triangle and the rhomboid in the middle.

For the top left triangle the values in the first column (x=0) can be calculated using the common arithmetic series 1 + 2 + 3 + .. + n = n*(n+1)/2. Fields in the that triangle with the same x+y value are in the same diagonal and there value is that sum from the first colum + x.

The same approach works for the bottom right triangle. But instead of x and y, w-x and h-y is used, where w is the width and h the height of rectangle. That value have to be subtracted from the highest value w*h-1 in the array.

There are two cases for the rhomboid in the middle. If the width of rectangle is greater than (or equal to) the height, then the bottom left field of the rectangle is the field with the lowest value in the rhomboid and can be calculated that sum from before for h-1. From there on you can imagine that the rhomboid is a rectangle with a x-value of x+y and a y-value of y from the original rectangle. So calculations of the remaining values in that new rectangle are easy.
In the other case when the height is greater than the width, then the field at x=w-1 and y=0 can be calculated using that arithmetic sum and the rhomboid can be imagined as a rectangle with x-value x and y-value y-(w-x-1).

The code can be optimised by precalculating values for example. I think there also is one formula for all that cases. Maybe i think about it later.

inline static int diagonalvalue(int x, int y, int w, int h) {
    if (h > x+y+1 && w > x+y+1) {
        // top/left triangle
        return ((x+y)*(x+y+1)/2) + x;
    } else if (y+x >= h && y+x >= w) {
        // bottom/right triangle
        return w*h - (((w-x-1)+(h-y-1))*((w-x-1)+(h-y-1)+1)/2) - (w-x-1) - 1;

    // rhomboid in the middle
    if (w >= h) {
        return (h*(h+1)/2) + ((x+y+1)-h)*h - y - 1;
    return (w*(w+1)/2) + ((x+y)-w)*w + x;

        array[x][y] = diagonalvalue(x,y,w,h);

Of course if there is not such a limitation, something like that should be way faster:

n = w*h;
x = 0;
y = 0;
    array[x][y] = i;
    if (y <= 0 || x+1 >= w)  {
        y = x+y+1;
        if (y >= h) {
            x = (y-h)+1;
            y -= x;
        } else {
            x = 0;
    } else {
share|improve this answer
Extensive explanation, nice work. Indeed, it would be elegant to have one formula for all cases. An alternative would be to fill a 'reference array' by means of the latter, 'clean' algorithm and then access this array's values in the row/column-constrained algorithm. –  dbaw Jul 2 '10 at 9:54
add comment

What about this (having an NxN matrix):

count = 1;
for( int k = 0; k < 2*N-1; ++k ) {
  int max_i = std::min(k,N-1);
  int min_i = std::max(0,k-N+1);
  for( int i = max_i, j = min_i; i >= min_i; --i, ++j ) {
    M.at(i).at(j) = count++;
share|improve this answer
add comment

Follow the steps in the 3rd example -- this gives the indexes (in order to print out the slices) -- and just set the value with an incrementing counter:

int x[3][3];
int n = 3;
int pos = 1;
for (int slice = 0; slice < 2 * n - 1; ++slice) {
    int z = slice < n ? 0 : slice - n + 1;
    for (int j = z; j <= slice - z; ++j)
        x[j][slice - j] = pos++;
share|improve this answer
add comment

At a M*N matrix, the values, when traversing like in your stated example, seem to increase by n, except for border cases, so


...and so on up to f(N,0). Then


and then

f(m,n)=f(m-1,n)+N, where m,n are index variables


f(M,N)=f(M-1,N)+2, where M,N are the last indexes of the matrix

This is not conclusive, but it should give you something to work with. Note, that you only need the value of the preceding element in each row and a few starting values to begin.

share|improve this answer
add comment

If you want a simple function, you could use a recursive definition.

H = height

def get_point(x,y)
  if x == 0
      if y == 0
        return 0
        return get_point(y-1,0)+1
    return get_point(x-1,y) + H

This takes advantage of the fact that any value is H+the value of the item to its left. If the item is already at the leftmost column, then you find the cell that is to its far upper right diagonal, and move left from there, and add 1.

This is a good chance to use dynamic programming, and "cache" or memoize the functions you've already accomplished.

If you want something "strictly" done by f(n), you could use the relationship:

n = ( n % W , n / H )   [integer division, with no remainder/decimal]

And work your function from there.

Alternatively, if you want a purely array-populating-by-rows method, with no recursion, you could follow these rules:

  1. If you are on the first cell of the row, "remember" the item in the cell (R-1) (where R is your current row) of the first row, and add 1 to it.
  2. Otherwise, simply add H to the cell you last computed (ie, the cell to your left).

Psuedo-Code: (Assuming array is indexed by arr[row,column])

arr[0,0] = 0

for R from 0 to H

  if R > 0
    arr[R,0] = arr[0,R-1] + 1 

  for C from 1 to W

    arr[R,C] = arr[R,C-1]


share|improve this answer
add comment

Your Answer


