user3639557 - 3 years ago 149

Java Question

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.

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

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**