Thread: Compacting a sparse matrix

So i'm dealing with sparse matrix and i have to compact in into a single array, for this assignment i created a struct called Point that has a line, column and value and i created an array of Points.
So, i dont have a 2d array, just a normal array of Points with their position on the matrix (line and column) and value.
Lets imagine my matrix its like this (the -1s dont not count as values of the matrix):

Code:

 -1   5   6  -1  -1
 -1  -1  -1   7  -1 
  8   9  -1  -1   4

I have to start with the line with the most elements and put those elements in the array ( thats already has a size pre defined), so, since the line with the most elements is the 3rd, it would look like this:

Code:

8  9  -1  -1   4

Then comes the 2nd line, but, as you can see, i can't keep the relative positions of the elements unless i move the line 1 spot to the front, it would look like this:

Code:

8  9  5  6  4  -1

In this case, the offset for the 2nd line is 1 because i had to move it 1 spot. For the final line, the one with the least elements, i have to move it 2 spots to the side, so the offset would be 2 and the final result would be:

Code:

8  9  5  6  4  7

This is my goal, first i created an array with the lines sorted by number of elements, but im really struggling with putting the elements in the array and keeping their relative positions. Remember, i dont have a 2d array, a just a normal array which each element is Point with a line, column and value.
Normally i dont ask thngs like these but im really having a hard time and getting really frustrated. Does anyone have an idea, not even code, just for a algorhytm to solve this?