Jagged array; check for column-wise value increase
This method is simple, there is 2D array, not a rectangle, the purpose is to check the values in each column whether they are increasing or not, if they are in an increasing order, return true, else return false.
The shape of the array is like the following, it is a Young Tableaux
{
[1,4,5,10,11],
[2,6,8],
[3,9,12],
[7]
}
The main properties of a young tableaux:
- it consists of cells which are filled with integers, and arranged in
left-justified rows, - no row is longer than a preceding row,
- from left to right in any row, and down any column the integers are increasing,
- the set of integers used is {1, 2, . . . , n} where n is the number
of cells
How I solve it?
My approach is simple, first convert this 2D array into a rectangle matrix, if some position is empty, then filled it with 0.
Then check the column one by one, if found a error, then break, and return the result.
It works, I just wonder if there is a better apporach for this.
public static boolean columnValuesIncrease(int[][] t) {
//How many columns are there?
int columnCounts = t[0].length;
int rowCounts = t.length;
//create a rectangle matrix, fill 0 when outIndex
int[][] addZero = new int[rowCounts][columnCounts];
for (int row = 0; row < rowCounts; row++) {
for (int col = 0; col < t[0].length; col++) {
try {
addZero[row][col] = t[row][col];
} catch (IndexOutOfBoundsException e) {
addZero[row][col] = 0;
}
}
}
//Let's check the damn column!
boolean mark = true;
myLoop:
for (int col = 0; col < columnCounts; col++) {
for (int row = 0; row < rowCounts; row++) {
if (row + 1 < rowCounts && col + 1 < columnCounts) {
if (addZero[row + 1][col] != 0) {
mark = addZero[row][col] <
addZero[row + 1][col] ? true : false;
}
}
if (!mark) {
break myLoop;
}
}
}
return mark;
}
This approach takes a row. It considers 'this' row and the one after it. It considers N number of columns, where N is the minimum of the number of columns in this row and the row after. In math, if R is the number of rows in this 2D matrix, take some r1: r1 ∈ [0, R) and r2 = r1 + 1. Then, N = min{num_cols(r1), num_cols(r2)}.
In column n, where n ∈ [0, N], if the value at the column in the next row happens to be smaller than the value in the preceding row, it returns false. If everything else worked, it returns true.
public static boolean columnValuesIncrease(int[][] t) {
for(int i = 0 ; i < t.length - 1 ; i++)
for(int j = 0 ; j < Math.min(t[i].length, t[i+1].length) ; j++)
if(t[i][j] > t[i+1][j])
return false;
return true;
}