Hello Avid Readers,

Today, I want to discuss a efficient and fast data structure that represents a Upper-Triangular matrix. An upper triangular matrix consists of 1+2+…n=n(n+1)/2 elements, which is less then n^2 of a matrix. The question is how should we represent this as an primitive array? Or more specifically, what should the hash function be that maps and index of this data structure to a 1d-array. I stumbled upon this blog post, which suggests the following approach. First define a hash function:

*i=(n * r) + c – (r * (r + 1))/2*

So now we can iterate:

string[] array = new string[(n*(n+1))/2]; //allocate for (int r=0; r<matrix.GetLength(0); ++r) //each row { for (int c=0; c<matrix.GetLength(1); ++c) { int i = (n * r) + c – ((r * (r+1)) / 2); array[i] = matrix[r,c]; } }

And it works beautifully.