19
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];
        }
    }
}
4

8 Answers 8

11

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.

5
  • here i have question, what is the algo for this, or pleas give a hint how can i first add to row, than columns ?
    – halu
    Sep 18, 2014 at 20:50
  • @halu Finished my implementation. Should work for you. Sep 18, 2014 at 20:54
  • I just made a O(n^2) down below. It has some dynamic programming aspects to it. Its a little messy and probably has a nicer way to write it. But it works for any dimension.
    – Jay
    Sep 18, 2014 at 21:37
  • 2
    Nitpicking: O(2n^2) is O(n^2). The constant is not relevant in big-oh notation.
    – You
    Sep 18, 2014 at 23:13
  • Yeah, @You are correct. But in the spirit of full disclosure, I wanted to make the distinction. Sep 18, 2014 at 23:15
7

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.

1
  • I like your solution. It is indeed O(n^2) (note the nested loops mean you will perform your operation n * n times). This was the same idea I had after posting my solution. Sep 19, 2014 at 1:58
4

Diagonal of an M by N Matrix, with Robust Array Formatting

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).

Code

Main

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

Printing a 2-Dimensional Array

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("}");
     }
}

The Diagonal Converter

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

Sample Output

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}
2

Luke's intuition is a good one - you're working through down-and-left diagonals. Another thing to notice is the length of the diagonal: 1, 2, 3, 2, 1. I'm also assuming square matrix. Messing with your for indicies can yield this:

    int len = 1;
    int i = 1;
    while(len <= arr.length){
        //Fill this diagonal of length len
        for(int r = 0; r < len; r++){ 
            int c = (len - 1) - r;
            arr[r][c] = i;
            i++;
        }

        len++;
    }
    len--; len--;
    while(len > 0){
        //Fill this diagonal of length len
        for(int c = arr.length - 1; c > (arr.length - len - 1); c--){ 
            int r = arr.length - len + 2 - c;
            arr[r][c] = i;
            i++;
        }

        len--;
    }

    System.out.println(Arrays.deepToString(arr));
1
  • it is doing wrong calculations when i just copy the code!!
    – halu
    Sep 18, 2014 at 21:03
2

Here is the code translated from here to Java and adjusted to your problem.

int[][] convertToDiagonal(int[][] input) {
    int[][] output = new int[input.length][input.length];
    int i = 0, j = 0; // i counts rows, j counts columns

    int n = input.length;
    for (int slice = 0; slice < 2 * n - 1; slice++) {
        int z = slice < n ? 0 : slice - n + 1;
        for (int k = z; k <= slice - z; ++k) {
            // store slice value in current row
            output[i][j++] = input[k][slice - k];
        }
        // if we reached end of row, reset column counter, update row counter
        if(j == n) {
            j = 0;
            i++;
        }
    }
    return output;     
}

Input:

| 1 2 3 |
| 4 5 6 |
| 7 8 9 |

Output:

| 1 2 4 |
| 3 5 7 |
| 6 8 9 |

Click here for running test code

2

This is a simple dynamic programming (ish) solution. You basically learn from the last move you made.

NOTE: THIS IS A O(N^2) ALGOIRTHM

Initialize:

 int m = 4;
 int n = 4;
 int[][] array = new int[m][n];;
 for(int i = 0; i < 3; i++){
    for(int j = 0; j < 3; j++){
        array[i][j] = 0;
    }
 }

The work:

array[0][0] = 1;
for(int i = 0; i < m; i++){
    if(i != 0){ array[i][0] = array[i-1][1]+1;} 
  // This is for the start of each row get 1+ the diagonal 
    for(int j = 1; j < n; j++){
        if(i == 0){
            array[i][j] = array[i][j-1]+j;
            // only for the first row, take the last element and add + row Count
        }else{
            if(i == m-1 && j == n -1){
               // This is only a check for the last element
                array[i][j] = array[i][j-1]+1;
                break;  
            } 
            // all middle elements: basically look for the diagonal up right.
            // if the diagonal up right is out of bounds then take +2 the 
            // prev element in that row
            array[i][j] = ((j+1) != (m)) ? array[i-1][j+1] +1: array[i][j-1]+2;
        }
    }
}

Printing the solution:

 for(int i = 0; i < m; i++){
     for(int j = 0; j < n; j++){
        System.out.print(array[i][j]);
     }
     System.out.println("");
  }
 return 0;
}
1
  • Question is for Java. Sep 18, 2014 at 21:44
2

You need to do a conversion from index 0..n for x/y (from 0 to x*y) and back to x/y from index...

public void toPos(int index){
    return...
}

public int toIndex(int x, int y){
    return...
}

I've left the implementation details to you.

1

Here is Complete working code for your problem. Copy and paste if you like

public class FillArray{
    public static void main (String[] args){


    int[][] array = {
            {1,2,3},
            {4,5,6},
            {7,8,9}}; //This is your original array

    int temp = 0; //declare a temp variable that will hold a swapped value

    for (int i = 0; i < array[0].length; i++){
        for (int j = 0; j < array[i].length; j++){
            if (i < array.length - 1 && j == array[i].length - 1){ //Make sure swapping only
                temp = array[i][j];                                //occurs within the boundary  
                array[i][j] = array[i+1][0];                       //of the array. In this case
                array[i+1][0] = temp;                              //we will only swap if we are
            }                                                      //at the last element in each
        }                                                          //row (j==array[i].length-1)
    }                                                              //3 elements, but index starts
                                                                   //at 0, so last index is 2 
  }                                                                   
  }

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.