How to find the shortest compact representation of circular buffer (vector).

Question

Say I have a circular buffer of zeros and non-zeros. I want to store as short array of non-zero values as possible and I am allowed to store

1. offset
2. size of array
3. the array itself.

for example [0,1,-1,0,0,0] can be stored either

1. offset 1 and size 2 and array [1,-1]
2. offset 2 and size 6 and array [-1,0,0,0,0,1]

In this case it is easy to see that the first one would be preferable and that the second one would be the worst case ( in terms of storage required for the array ).

What would in general be an efficient algorithm to find the offset which would give the shortest size of array required for storage?

Answer 1

Your approach saves space by dropping a series of consecutive zeros, so to find the best offset, it suffices to find where the longest series of zeros in your original circular array starts. This can be computed in time linear with respect to the size of the array.