user3639557 user3639557 - 3 years ago 137
Java Question

What is the best data structure for representing an upper triangular matrix in Java?

Suppose an upper triangular matrix of integers is given. What's the best way of storing this in Java? The naive 2d int array is obviously not efficient. The solution I came up with was moved to the answers section.

Answer Source

I think I found the solution. Here is my solution: Assume you have a 4X4 upper triangular matrix M.

1 2 3 4
0 6 7 1
0 0 8 9
0 0 0 5

If you can map every element of M in a 1d array, that's the best solution. All you need to know is to know which [row,col] of matrix corresponds to which element of your 1d array. Here is how you do the magic:

start_index=((col_index-1)+1)+((col_index-2)+1)+...+1
end_index=start_index + col_index

For example: if I want to find where are the elements on the 3rd column of the matrix, in the array:

start_index=((3-1)+1)+((3-2)+1)+((3-3)+1)=6
end_index=6+3=9

So, all I need to do is to start at index 6 of my array, and read all the elements till index 9 (including 9th element). Following this procedure, then you can store and retrieve all the cells of the nXn matrix in (n + n^2)/2 space.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download