# Convert lower-left matrix triangle 1D index to row, column

How can I convert a 1D index in the lower-left triangle of a grid into a row and column?

For example, consider this table of 1D indices, indexed by row and column

        //       0  1  2  3 4
//    +--------------- ...
// 0  |  0
// 1  |  1  2
// 2  |  3  4  5
// 3  |  6  7  8  9
// 4  | 10 11 12 13 14
// ...


Computing the 1D index from row and column is easy.

Computing the column from the row and 1D index would also be easy. The triangle above a row has -- with 0-based indices -- (row^2 + row)/2 indices.

How can I compute the row from the 1D index quickly, ideally in constant time, without any pre-computed mapping?

The $$r$$ first rows include $$T_r=\dfrac{r(r+1)}2$$ elements and the linear index corresponding to $$(r,c)$$, with $$0\le c\le r$$, is $$i:=T_r+c$$.

The $$T_r$$ are called the triangular numbers.

Retrieving the row and column from the linear index is a little more tricky.

For given $$i$$, we have

$$\frac{r(r+1)}2\le i\le\frac{r(r+1)}2+r$$

or, multiplying by 2 then adding 1/4:

$$\left(r+\frac12\right)^2\le 2i+\frac14\le \left(r+\frac32\right)^2-2$$ and this is solved by

$$r=\left\lfloor\sqrt{2i+\frac14}-\frac12\right\rfloor.$$ $$c$$ follows.

• Works for zero-based r. Thanks! Adding a bit of perhaps obvious detail to step 2. Dec 5, 2022 at 20:39

I think this is a solution. Works better with 1-based indices.

        //       1  2  3  4  5
//    +--------------- ...
// 1  |  1
// 2  |  2  3
// 3  |  4  5  6
// 4  |  7  8  9 10
// 5  | 11 12 13 14 15
// ...


Let i be the 1D index. Then we have i < (row^2 + row / 2). And for the rightmost value in a row, we have i = (row^2 + row / 2).

That gives the quadratic equation 0 = row^2 + row - 2i. Given i, we can solve for row, using:

q = -1/2 * (b + sgn(b) * sqrt( b^2 - 4ac ))
x1 = q/a
x2 = c/q


Then:

row = ceil( x2 ) = ceil( c / q )


For example, consider i=10, in the fourth row above. Then:

c = -2 * 10 = -20

q = -1/2 * (1 + 1*sqrt(1 - 4 * 1 * (-2*10)))
= -1/2 * (1 + sqrt( 1 + 80 ))
= -1/2 * (1 + 9)
= -5

row = ceil( c / q ) = -20 / -5 = 4


Doing the same for i=15 results in row = -30/-6 = 5.

The ceiling of the results for anything between 10 < i <= 15 is also 5.