Menu
1 2 3
4 5 6
7 8 9
this is my normal array, but i need to make it diagonally like this
1 2 4
3 5 7
6 8 9
this is very stupid way to make it work, but even it is not working because i am not able to find 2nd column elements.
for (i = 0; i < arr.length; ++i) {
for (n = 0; n < arr[0].length; ++n) {
if (i == 0 && n == 0){
arr[i][n] = 0;
} else if (i == 0 && n == 1) {
arr[i][n] = 2;
} else if (i == 1 && n == 0) {
arr[i][n] = 3;
} else if (n == 0) {
arr[i][n] = arr[i - 1][n] - arr[i - 2][n] + 1 + arr[i - 1][n];
} else {
arr[i][n] = arr[i][n - 1] - arr[i][n - 2] + 1 + arr[i][n - 1];
}
}
}
773
Start from the index (0,0) and print the elements diagonally upward then change the direction, change the column and print diagonally downwards. This cycle continues until the last element is reached. Algorithm: Create variables i=0, j=0 to store the current indices of row and column.
Well, if you were to enumerate the indices in order for that fill pattern, you would get
0,0
1,0
0,1
2,0
1,1
0,2
2,1
1,2
2,2
So, you need to iterate through the total of the two indices. That is, the additive total. As you can see, 0,0 totals 0, 1,0 and 0,1 total 1, and so on. Giving us something like this:
0 1 2
1 2 3
2 3 4
To iterate in this diagonal pattern, we can do the following:
// set up your matrix, any size and shape (MxN) is fine, but jagged arrays will break
int[][] matrix = {{0,0,0},{0,0,0},{0,0,0}};
// number is the value we will put in each position of the matrix
int number = 1;
// iterate while number is less than or equal to the total number of positions
// in the matrix. So, for a 3x3 matrix, 9. (this is why the code won't work for
// jagged arrays)
for (int i = 0; number <= matrix.length * matrix[0].length; i++) {
// start each diagonal at the top row and from the right
int row = 0;
int col = i;
do {
// make sure row and length are within the bounds of the matrix
if (row < matrix.length && col < matrix[row].length) {
matrix[row][col] = number;
number++;
}
// we decrement col while incrementing row in order to traverse down and left
row++;
col--;
} while (row >= 0);
}
Note that while this implementation will work for all matrix sizes (and shapes), it won't be as efficient as possible. Where n is matrix.length (assuming a square matrix), this implementation is an optimal O(n^2) class algorithm in big O notation; however, it effectively performs 2*n^2 iterations, whereas an optimal solution would only perform n^2.
174
You want to achive something like this:
1 2 4 7
3 5 8 B
6 9 C E
A D F G
In the grid of size NxN, for every point (x,y) in the grid, you can determine the value like this (still needs some corrections for offset at 0, see final formula):
if you are on the upper left half, calculate the area of the triangle that is above and left of you and add your distance from the top
if you are in the lower right half (or on the middle), calculate the area of the triangle below and right of you, add your distance from the bottom and subtract that from the whole area
Let's try it as a formula:
int N = 4; int[][] v = new[N][N];
for(int y = 0; y < N; y++) for(int x = 0; x < N; x++)
v[x][y] = ( x + y < N ) ?
( ( x + y + 1 ) * ( x + y ) / 2 + y + 1 ) :
( N * N + 1 - ( N - y ) - ( 2 * N - x - y - 1 ) * ( 2 * N - x - y - 2 ) / 2 );
I have no idea what complexity this is, but the experts can surely confirm that it is O(N^2) ? Also if it has some cool name like dynamic code, please let me know!
The advantage I see here is that you don't need to jump around memory and can fill all fields with one linear run through the memory. Also having it as a history independent formula can be optimized by the compiler or allow better parallelisation. If you had a machine with N^2 units, they could calculate the whole matrix in one operation.
23
Given that a lot of these answers have already covered the basic N by N arrays, and some are pretty efficient, I went ahead and made a more robust version that handles M by N arrays, along with a nice formatted printer, for your own enjoyment/masochistic viewing.
The efficiency of this method is O(N^2). The format of the printer is O(N^2).
You can set whatever rows and columns you want, assuming positive integer values.
public static void main(String[] args) {
//create an M x N array
int rows = 20;
int columns = 11;
int[][] testData = new int[rows][columns];
//iteratively add numbers
int counter = 0;
for(int i = 0; i < rows; i++) {
for(int j = 0; j < columns; j++) {
testData[i][j] = ++counter;
}
}
//print our test array
printArray(testData);
System.out.println("");
//print our diagonal array
printArray(diagonal(testData));
}
This method works specifically for this example by determining the number of entries using M x N, and then counting the digits. If you want to, say, display any sized array based on the longest item in the array, you could easily adapt this code to do that. A decent challenge best assigned to the reader. O(N^2) for this, but due to having to search the array for the largest value, one that takes the largest digit will by nature require another O(N^2) for search.
static void printArray(int[][] array) {
//get number of digits
int count = array.length * array[0].length;
//get power of function
int power;
//probably the only time I'd ever end a for loop in a semicolon
//this gives us the number of digits we need
//You could also use logs I guess but I'm not a math guy
for(power = 0; count / Math.pow(10, power) > 1; power++);
for(int i = 0; i < array.length; i++){
System.out.print("{");
for(int j = 0; j < array[0].length; j++){
//Let's say Power is 0. That means we have a single-digit number, so we need
// +1 for the single digit. I throw in 2 to make it extra wide
System.out.print(String.format("%" + Integer.toString(power + 2)
+ "s", Integer.toString(array[i][j])));
}
System.out.println("}");
}
}
There's a lot of edge cases to be tested for when we account for M x N, so I went ahead and seem to have covered all of them. Not the neatest, but looks to be working.
static int[][] diagonal(int[][] input) {
//our array info
final int numRows = input.length;
final int numColumns = input[0].length;
int[][] result = new int[numRows][numColumns];
//this is our mobile index which we will update as we go through
//as a result of certain situations
int rowIndex = 0;
int columnIndex = 0;
//the cell we're currently filling in
int currentRow = 0;
int currentColumn = 0;
for(int i = 0; i < numRows; i++) {
for(int j = 0; j < numColumns; j++) {
result[currentRow][currentColumn] = input[i][j];
//if our current row is at the bottom of the grid, we should
//check whether we should roll to top or come along
//the right border
if(currentRow == numRows - 1) {
//if we have a wider graph, we want to reset row and
//advance the column to cascade
if(numRows < numColumns && columnIndex < numColumns - 1 ) {
//move current row down a line
currentRow = 0;
//reset columns to far right
currentColumn = ++columnIndex;
}
//if it's a square graph, we can use rowIndex;
else {
//move current row down a line
currentRow = ++rowIndex;
//reset columns to far right
currentColumn = numColumns - 1;
}
}
//check if we've reached left side, happens before the
//top right corner is reached
else if(currentColumn == 0) {
//we can advance our column index to the right
if(columnIndex < numColumns - 1) {
currentRow = rowIndex;
currentColumn = ++columnIndex;
}
//we're already far right so move down a row
else {
currentColumn = columnIndex;
currentRow = ++rowIndex;
}
}
//otherwise we go down and to the left diagonally
else {
currentRow++;
currentColumn--;
}
}
}
return result;
}
Input
{ 1 2 3}
{ 4 5 6}
{ 7 8 9}
{ 10 11 12}
Output
{ 1 2 4}
{ 3 5 7}
{ 6 8 10}
{ 9 11 12}
Input
{ 1 2 3 4 5 6}
{ 7 8 9 10 11 12}
{ 13 14 15 16 17 18}
{ 19 20 21 22 23 24}
{ 25 26 27 28 29 30}
{ 31 32 33 34 35 36}
Output
{ 1 2 4 7 11 16}
{ 3 5 8 12 17 22}
{ 6 9 13 18 23 27}
{ 10 14 19 24 28 31}
{ 15 20 25 29 32 34}
{ 21 26 30 33 35 36}
Input
{ 1 2 3 4 5 6}
{ 7 8 9 10 11 12}
{ 13 14 15 16 17 18}
{ 19 20 21 22 23 24}
{ 25 26 27 28 29 30}
{ 31 32 33 34 35 36}
{ 37 38 39 40 41 42}
{ 43 44 45 46 47 48}
{ 49 50 51 52 53 54}
{ 55 56 57 58 59 60}
{ 61 62 63 64 65 66}
{ 67 68 69 70 71 72}
{ 73 74 75 76 77 78}
{ 79 80 81 82 83 84}
{ 85 86 87 88 89 90}
{ 91 92 93 94 95 96}
{ 97 98 99 100 101 102}
{ 103 104 105 106 107 108}
{ 109 110 111 112 113 114}
{ 115 116 117 118 119 120}
{ 121 122 123 124 125 126}
{ 127 128 129 130 131 132}
{ 133 134 135 136 137 138}
{ 139 140 141 142 143 144}
{ 145 146 147 148 149 150}
Output
{ 1 2 4 7 11 16}
{ 3 5 8 12 17 22}
{ 6 9 13 18 23 28}
{ 10 14 19 24 29 34}
{ 15 20 25 30 35 40}
{ 21 26 31 36 41 46}
{ 27 32 37 42 47 52}
{ 33 38 43 48 53 58}
{ 39 44 49 54 59 64}
{ 45 50 55 60 65 70}
{ 51 56 61 66 71 76}
{ 57 62 67 72 77 82}
{ 63 68 73 78 83 88}
{ 69 74 79 84 89 94}
{ 75 80 85 90 95 100}
{ 81 86 91 96 101 106}
{ 87 92 97 102 107 112}
{ 93 98 103 108 113 118}
{ 99 104 109 114 119 124}
{ 105 110 115 120 125 130}
{ 111 116 121 126 131 136}
{ 117 122 127 132 137 141}
{ 123 128 133 138 142 145}
{ 129 134 139 143 146 148}
{ 135 140 144 147 149 150}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
