Save space occupied by 2D array

This is an interesting problem. Your code looks effective, and there is little that sticks out at me as being a performance problem, except that I feel the two-array RLE is not the most efficient mechanism.

There are ways that you can reduce the code size, but I don't think that will impact the run-time performance though. You can, if you want, isert the three constant values FISH, SHARK, and EMPTY in to an array, and then you can reduce the code repetition by making use of the array. I do something similar in the example at the end.

OK, about the RLE algorithm though...

For every value in your RLE data you need 2 integers (1 in each array). Each time the run-value changes (e.g. from EMPTY to SHARK) you add 2 integers. For the example data:

data   -> [1,1,1,1,1,2,1,1,1]

you will have two arrays:

code   -> [1,2,1]
length -> [5,1,3]

This is 6 integers worth.

If you change the algorithm to just 1 array, but you force the algorithm to store a possibly empty value for non-existant values, you can have the single output:

encoded -> [5,1,0,3]

To decode this, you say, I have 5 1's, followed by 1 2, followed by 0 3's, and then 3 1's.

The advantage of this system is that, for about half the transitions, you only need to have 1 extra integer for the transition, instead of always requiring 2. This means that each transition takes an average of 1.5 integers, instead of 2.... so the data encodes down to about 25% less space.

Yu can see that in the data, where the single array stores the data in 4 integers, but the 2-array system stores it in 6 integers (3 in each array).

While this space saving is significant, the real benefit is in the encoding, and decoding speed and simplicity.

I put together these two methods that do the encoding, and decoding system. The methods store the arrays structure as part of the encoded stream.... it is basically a serialization of the data. I imagine that this is why you are doing this process anyway.

Anyway, you will see that the loops are actually much simpler than yours, and the encoding and decoding is quite symmetrical... which is nice.

import java.util.Arrays;


@SuppressWarnings("javadoc")
public class RLEncode {

    public final static int EMPTY = 1;
    public final static int SHARK = 2;
    public final static int FISH = 3;

    public static int[] encode(int[][] matrix) {
        final int[] validvalues = {EMPTY, SHARK, FISH};

        final int height = matrix.length;
        final int width = height > 0 ? matrix[0].length : 0;
        // start with some reasonable size
        // will resize as necessary
        int[] result = new int[2 + validvalues.length + 1024];
        int cnt = 0;

        // save away the core details of the ocean.
        result[cnt++] = height;
        result[cnt++] = width;
        result[cnt++] = validvalues.length;
        for (int vv : validvalues) {
            result[cnt++] = vv;
        }

        // The encoding from here cycles through the possible values
        // and stores away the run-length of each value.
        int content = 0;
        for (int[] row : matrix) {
            if (row.length != width) {
                throw new IllegalStateException("Irregular matrix");
            }
            for (int v : row) {
                int ref = content;
                while (v != validvalues[content]) {
                    // cycle until we find the matching cell type.
                    cnt++; // we move on...
                    if (cnt >= result.length) {
                        // add 50% to cell size.
                        result = Arrays.copyOf(result, result.length + (result.length >>> 1));
                    }
                    content = (content + 1) % validvalues.length;
                    if (content == ref) {
                        // we have looped through all our values... oops.
                        throw new IllegalStateException("Illegal value " + v);
                    }
                }
                // add to run-length
                if (++result[cnt] < 0) {
                    throw new IllegalStateException("Overflowed during encoding");
                }
            }
        }
        cnt++;
        return Arrays.copyOf(result, cnt);
    }

    public static int[][] decode(int[] encoded) {
        if (encoded.length < 3) {
            throw new IllegalArgumentException("Minimum size encoded value is " + 3);
        }
        int cnt = 0;
        int height = encoded[cnt++];
        int width = encoded[cnt++];
        int[][] result = new int[height][width];
        int validcnt = encoded[cnt++];
        int[] validvalues = new int[validcnt];
        if (encoded.length < cnt + validcnt) {
            throw new IllegalStateException("Expect there to be " + validcnt + " valid values, but there's not enough data.");
        }
        for (int i = 0; i < validcnt; i++) {
            validvalues[i] = encoded[cnt++];
        }

        int content = 0;
        int cursor = 0;
        for ( ; cnt < encoded.length; cnt++) {
            for (int i = encoded[cnt] - 1; i >= 0; i--) {
                result[cursor / width][cursor % width] = validvalues[content];
                cursor++;
            }
            content = (content + 1) % validcnt;
        }

        if (cursor != (width * height)) {
            throw new IllegalStateException("Expected to decode exactly " + (width * height) + " cells");
        }

        return result;
    }


    public static void main(String[] args) {
        int[][]matrix = {
                {1,1,1,1,1,1,1,2,1},
                {1,1,1,2,1,1,2,1,1},
                {1,2,3,2,1,1,1,2,1},
                {1,1,1,1,1,1,1,1,1},
                {1,1,1,1,1,2,1,1,2},
                {1,1,1,1,1,1,1,1,1}
            };
        int[] encoded = encode(matrix);
        int[][] decoded = decode(encoded);

        if (!Arrays.deepEquals(matrix, decoded)) {
            throw new IllegalStateException("Broken");
        }

    }


}

Run-length encoding is not always the most efficient way. If the value very changes often (so that length is always 1) the RLE encoding method can be longer than the original data (because you're storing the data, plus the extra 1 for each datum).

Sometimes people recommend that you simply using an industrial-strength 'ZIP' algorithm on the data instead.

If you want to make your RLE more compact, a possibility is to use some bits which you're currently not using: you're only using 2 bits within the first int to store the 3-valued data; you could store the length within the free 29-bits of the same integer, and use the last bit to indicate a length overflow into the next int:

• 1st 2 bits: the data (empty or fish or shark)
• Next 29 bits: the length (can't be zero)
• Last (i.e. 32nd) bit: usually 0; 1 (which probably happens rarely) means that the length doesn't fit into 29 bits, and that the next integer in the array store the rest of the length (or that the 29 bits in this integer aren't used, and that the whole of the length is stored in the next integer).

For example, if your ocean consists of 2 fish and 1 shark, you used to encode that in 4 integers like this:

3, 2, 2, 1

With the method I'm suggesting you could encode that in two integers as follows:

3 + (2 << 2), 2 + (1 << 2)

Taking another idea from rolfl's answer, you only need one bit (not two bits) to store the type of datum:

• Remember (separately) the type of the first datum
• Know that the next datum isn't the same as this datum (because this datum is run-length encoded)
• Therefore one bit is enough: for example if the previous datum is FISH, use 0 to specify that the next is EMPTY and 1 to specify that the next is SHARK.

You can compress it further by streating it as a stream of bits and ignoring the 32-bit integer boundaries. For example:

• 1 bit specifies the type of datum
• 5 bits specifies the number of bits which encode the length (i.e. up to 32 bits)
• Variable-length 1 to 32 bits (as specified in the previous 5 bits) specifies the run-length

If a typical run-length is for example 1000 (for empty spaces) that takes about 10 bits for the length. 1 + 5 + 10 means you encode each empty space in only about 16 bits; and the runs for fishes and sharks might be shorter (1 to 4 bits-worth of length), so they encode in 7 to 10 bits. In summary you might be able to encode, on average, two run-lengths in each 32-bits of data.

A few notes about the original code.

1. If the ocean mostly empty it's actually a sparse matrix. If you are allowed to use more arrays or another primitive data structures check the Spare matrix Wikipedia article about it, it contains other, maybe more effective storage structures.

2. The second switch case contains the same logic three times. You could extract it out to a method to remove duplication:

   private static int encode(int[] runType, int[] runLength, int currentType, int index) {
       if (runType[index] == currentType) {
           runLength[index]++;
       } else {
           index++;
           if (index == runType.length) {
               runType = doubleTheSize(runType);
               runLength = doubleTheSize(runLength);
           }
           runType[index] = currentType;
           runLength[index]++;
       }
       return index;
   }
   

   And use it in the switch:

   switch (sea.cellContents(row, col)) {
   case Ocean.EMPTY: {
       final int currentType = Ocean.EMPTY;
       index = encode(runType, runLength, currentType, index);
       break;
   }
   case Ocean.SHARK: {
       int currentType = Ocean.SHARK;
       index = encode(runType, runLength, currentType, index);
       break;
   }
   case Ocean.FISH: {
       int currentType = Ocean.FISH;
       index = encode(runType, runLength, currentType, index);
       break;
   }
   

   After that it's easier to notice that the whole switch-case could be eliminated since the body of every case statement is very similar to each other and depends on only the sea.cellContents(row, col) value.

   final int currentType = sea.cellContents(row, col);
   index = encode(runType, runLength, currentType, index);
   

3. int[] runLength = new int[10]; // corresponding index cell stores its number of occurence of that respective runType.
   

   I'd put the comment before the line it comments:

   // corresponding index cell stores its number of occurrence of that respective runType.
   int[] runLength = new int[10];
   

   It's easier to work with because it requires less horizontal scrolling.

4. A comment says the following:

   // i&j are width & height of a 2d array read from commandline
   

   Then you can use width and height as variable names for better readabilty (you don't have to remember what i or j mean nor check the comment for it) and could get rid of the comment.

5. The temp variable in doubleTheSize could be called doubledArray or newArray, arg is oldArray or originalArray. It would express the purpose of them.

6. Comments on the closing curly braces are unnecessary and disturbing. Modern IDEs could show blocks.

       }// end outer for loop
   }// end main()
   

   “// …” comments at end of code block after } - good or bad?

One point that I recognized is, firstCell check that I did for every cell doesn't make sense. I need suggestion to better this logic because I need to enter in firstCell i{} block for only (0, 0) cell.

You should measure it and if it's a really real bottleneck do something about it. Otherwise it's just bad premature optimization and will lead to harder to read and unmaintainable code. JVM is smart, I guess it will optimize it for you at runtime if it's really necessary. It can unroll loops and eliminate dead code.

DON'T DO THIS, just for fun, let's unroll the some iteration from the loop manually to save some boolean checks at runtime:

Initial loop:

boolean firstCell = true;
for (int row = 0; row < j; row++) {
    for (int col = 0; col < i; col++) {
        if (firstCell) {
            firstCell = false;
            runType[index] = sea.cellContents(0, 0);
            runLength[index]++;
            continue;
        }
        switch (sea.cellContents(row, col)) {
            // ...
        }
    }
}

After unrolling one iteraton of the outer loop:

if (j > 0) {
    int row = 0;
    for (int col = 0; col < i; col++) {
        if (firstCell) {
            firstCell = false;
            runType[index] = sea.cellContents(0, 0);
            runLength[index]++;
            continue;
        }
        switch (sea.cellContents(row, col)) {
            // ...
        }
    }
}
for (int row = 1; row < j; row++) { // initial value changes
    for (int col = 0; col < i; col++) {
        if (firstCell) { // dead code
            firstCell = false;
            runType[index] = sea.cellContents(0, 0);
            runLength[index]++;
            continue;
        }
        switch (sea.cellContents(row, col)) {
            // ...
        }
    }
}

Unrolling the first iteration of the inner loop:

if (j > 0) {
    int row = 0;
    if (i > 0) {
        if (firstCell) {
            firstCell = false;
            runType[index] = sea.cellContents(0, 0);
            runLength[index]++;
            // continue; // not necessary anymore 
        }
        // not necessary anymore
        //  switch (sea.cellContents(row, col)) {
        //      // ...
        //  }
    }

    for (int col = 1; col < i; col++) { // initial value changes
        switch (sea.cellContents(row, col)) {
            // ...
        }
    }
}
for (int row = 1; row < j; row++) {
    for (int col = 0; col < i; col++) { // don't need to change
        switch (sea.cellContents(row, col)) {
            // ...
        }
    }
}

Removing firstCell check and dead code:

if (j > 0) {
    if (i > 0) {
        firstCell = false;
        runType[index] = sea.cellContents(0, 0);
        runLength[index]++;
    }

    for (int col = 1; col < i; col++) {
    int row = 0;
        switch (sea.cellContents(row, col)) {
            // ...
        }
    }
}
for (int row = 1; row < j; row++) {
    for (int col = 0; col < i; col++) {
        switch (sea.cellContents(row, col)) {
            // ...
        }
    }
}

Once again, don't do this, it's harder to read and understand, contains lots of duplication and hard to maintain.