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

Question

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?

Answer 1

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.

Answer 2

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)$.

Answer 3

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)

}