1
$\begingroup$

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?

$\endgroup$

3 Answers 3

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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)

}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.