Albert Gao - 1 year ago 82

Java Question

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

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;

}

Answer

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 r_{1}: r_{1} ∈ [0, R) and r_{2} = r_{1} + 1. Then, N = min{*num_cols(r _{1}), num_cols(r_{2})*}.

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;
}
```

Source (Stackoverflow)