# In O(1) get the coordinate i,j of a diagonally ordered matrix

Say you have a matrix like this:

[][]int{
{0, 2, 5, 9, 14},
{1, 4, 8, 13, 18},
{3, 7, 12, 17, 21},
{6, 11, 16, 20, 23},
{10, 15, 19, 22, 24},
}


As you can see, it is diagonally ordered

Question: In Order O(1) if I give you a number N, give me the position i,j.

For example, on a regular ordered matrix

[][]int{
{0,1,2,3},
{4,5,6,7},
{8,9,10,11},
{13,14,15,16}
}


The solution is

j := n % len(m)
i := n / len(m[0])


With that you get i,j.
Ex: N=9 -> 2,1

But how to get them for diagonals?

These are triangular numbers, so:
$$i = \lfloor(-0.5 + \sqrt{0.25 + 2 * n}\rfloor - 1\\ triangular = \frac{i * (i + 1)}{2}\\ j = n - triangular - 1$$

Minus one comes from indexing from 1.

So the series for your very first column is $$0, 1, 3, 6, 10, \dots$$ which is A000217 also known as the triangular numbers. It has formula $$k(k+1)/2$$ for the $$k$$th triangular number.

We want to find the diagonal our number lies in, so we want to find the largest $$k$$ such that $$k(k+1)/2 \leq n$$. I'll leave that as an exercise to you.

Then once we found $$k$$ our number is the $$l = n - k(k+1)/2$$ element in the diagonal, counting from zero. So our number is simply at $$(k-l, l)$$.

Thanks @Evil, I got this algorithm based on your response. It returns the coordinates when giving an input number.

Only tested for squared matrices. EDIT: works on non squared matrices too.

func translateDiagonal(n, lenY, lenX int) (int, int) {

shifted := false

if n > lenX*lenY/2 {
n = lenX*lenY - n - 1
shifted = true
}

k := int(math.Floor((-0.5 + math.Sqrt(0.25+2.0*float64(n)))))
j := n - (k * (k + 1) / 2)
i := k - j

if shifted {
i = lenY - i - 1
j = lenX - j - 1
}

return i, j
}

func traverseDiagonal(m [][]int) {
for k := 0; k < len(m)*len(m[0]); k++ {
i, j := translateDiagonal(k, len(m), len(m[0]))
fmt.Println(m[i][j])
}
}

func main() {
m := [][]int{
{0, 2, 5, 9, 14},
{1, 4, 8, 13, 18},
{3, 7, 12, 17, 21},
{6, 11, 16, 20, 23},
{10, 15, 19, 22, 24},
}

traverseDiagonal(m)

}