CODEWITHSUNDEEP
java
Dave
Dave

Reputation: 97

Storing all diagonals from top right to bottom left in array

I am trying to store all of the values in the matrix from the top right to the bottom left and store them in an array.

    int matrixSample [][]  = {
            {6,4,1,4},
            {7,5,4,4},
            {4,4,8,3},
            {4,4,8,3}
            };

The output should be

[4,1,4,4,4,3,6,5,8,3,7,4,8,4,4,4]

I can get the bottom right diagonal

static int[] getAllDiagonalsInMatrix(int matrix[][]){
    // Sum of arithmetic progression 
    int diagonal[] = new int[matrix.length * (matrix.length + 1)*2];
    int index = 0;  
    for(int row = 0; row < matrix.length; row++) {          
        for(int col = 0; col < matrix[row].length - row; col++) {
            diagonal[index++] = matrix[row + col][col];         
        }
    }
    return diagonal;
}

Is this even possible to do using the same two loops by adjustments made in the loops above?

Upvotes: 0

Views: 1695

Answers (2)

Locke
Locke

Reputation: 8964

Okay, here is my thought process on your problem. However, I'm going to print values instead of collecting them to make it a little easier on me and keep the solution easy to read.

First, how do you get a diagonal? We need to do this frequently so lets start by making a function for that. Maybe we could pass in the top left corner of the diagonal and go from there.

public void getDiagonal(int[][] array, int row, int col) {
    // While row and col are within the bounds of the array
    while (row < array.length && col < array[row].length) {
        // Print element in diagonal
        System.out.println(array[row][col]);

        // Diagonal moves from top-left to bottom-right
        row++;
        col++;
    }
}

Now that we have a function to get a diagonal, we just need a way to call it. Essentially, we just need to follow an L shape going from the top-right to the top-left to the bottom-left.

// Get diagonals starting in the first row with a column > 0 
for (int col = array.length - 1; col > 0; col--) {
    getDiagonal(array, 0, col);
}

// Get all diagonals starting from the left most column
for (int row = 0; row < array.length; row++) {
    getDiagonal(array, row, 0);
}

Now that we have a working way to iterate through the values, we can rewrite it to save the values into an array instead. You could also choose to remove the function entirely now that you have a process.

Edit: I almost forgot, but the mathematical solution you were looking for is as follows.

for (int row = 0; row < array.length; row++) {
    for (int col = 0; col < array.length; col++) {
        // Index along diagonal
        int diagonal = Math.min(row, col);

        // Which part of L contains value
        if (col >= row) {
            int start = array.length - 1 - (col - row);
            int passed = start * (start + 1) / 2;
            solution[passed + diagonal] = array[row][col];
        } else {
            int start = array.length - 1 - (row - col);
            int passed = array.length * array.length - 1 - start * (start + 1) / 2;          solution[passed - array.length + 1 + row] = array[row][col];
        }
    }
}

Upvotes: 1

ODDminus1
ODDminus1

Reputation: 709

One solution is to iterate through a matrix where you consider positions outside of the matrix, but exclude every index out of bounds.

static int[] getDiagonals(int[][] mat) {
    int diagonal[] = new int[mat.length * (mat[0].length)];
    int index = 0;
    int yStart = -mat[0].length;
    for (int y = yStart; y < mat.length; y++) {
        for (int x = 0; x < mat[0].length; x++) {
            if (y + x >= 0 && y + x < mat.length) {
                diagonal[index++] = mat[y+x][x];
            }
        }
    }
    return diagonal;
}

Might not be optimal as you are effectively traversing a matrix nearly twice the size, but it is pretty intuitive.

Upvotes: 0

Related Questions