Encountered this problem on hackerrank ,

Please guide on how to rotate a 2D array clockwise by 90 degree using ArrayList only?

Here is my code below:

public static List<List<Integer>> rotate(List<List<Integer>> matrix, int n) {
    
    int N=n;
    ArrayList<List<Integer>> temp = new ArrayList<>();
    for (int j = 0; j < N; j  ) {
        for (int i = N - 1; i >= 0; i--)
            matrix.get(i).get(j);
    }
    temp.add(matrix);  
    return temp;
    }
}

CodePudding user response：

In case if according to the requirements of this challenge you're expected to return a newly created nested list, then you can prepopulate it and then manipulate with it as if it's a nested array.

The key point you need to understand in order to solve this problem - is how in indices are getting changed during rotation of element. And the best way to visualize this is to draw this process on a paper.

If you'll do that, you'll be able to observe that while rotating elements of a square matrix clockwise that:

• a row becomes a column

row -> column // i -> j   in the code

• a new column index becomes equal to the matrix size n minus 1 minus previous row index

j -> (n - 1) - i

That's how it might be implemented:

public static List<List<Integer>> rotate(List<List<Integer>> matrix, int n) {
    List<List<Integer>> result = getMatrix(n);
    
    // i -> j & j -> (n - 1) - i
    
    for (int i = 0; i < n; i  ) {
        for (int j = 0; j < n; j  ) {
            int next = matrix.get(i).get(j);
            result.get(j).set((n - 1) - i, next);
        }
    }
    
    return result;
}

public static List<List<Integer>> getMatrix(int n) {
    List<List<Integer>> result = new ArrayList<>();
    for (int i = 0; i < n; i  ) {
        result.add(new ArrayList<>(Collections.nCopies(n, 0)));
    }
    return result;
}

main()

public static void main(String[] args) {
    List<List<Integer>> rotatedList = rotate(List.of(
        List.of(1, 2, 3),
        List.of(4, 5, 6),
        List.of(7, 8, 9)
    ), 3);
    
    rotatedList.forEach(System.out::println);
}

Output:

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

CodePudding user response：

Try this.

static <T> List<List<T>> rotate(List<List<T>> matrix) {
    final int rows = matrix.size(), cols = matrix.get(0).size();
    List<List<T>> result = new ArrayList<>(cols);
    for (int c = 0; c < cols;   c) {
        List<T> newRow = new ArrayList<>(rows);
        for (int r = rows - 1; r >= 0 ; --r)
            newRow.add(matrix.get(r).get(c));
        result.add(newRow);
    }
    return result;
}

and

List<List<Integer>> matrix = List.of(
    List.of(1,2,3),
    List.of(4,5,6));
List<List<Integer>> result = rotate(matrix);
for (List<Integer> row : result)
    System.out.println(row);

output:

[4, 1]
[5, 2]
[6, 3]

CodePudding user response：

It is possible to do it in place

public static List<List<Integer>> rotate(List<List<Integer>> matrix, int n) {
    matrix.forEach(row -> {
        for (int i = 0, j = n - 1; i < j; i  , j--)
            swap(row, i, row, j);
    });

    for (int i = 0, j = n - 1; i < n; i  , j--) {
        for (int ii = i, jj = j, k = 0, l = n - 1; ii >= 0; ii--, jj  , k  , l--) {
            List<Integer> rowSrc = matrix.get(ii);
            List<Integer> rowDest = matrix.get(l);
            swap(rowSrc, k, rowDest, jj);
        }
    }

    return matrix;
}


private static void swap(List<Integer> one, int i, List<Integer> two, int j) {
    int tmp = one.get(i);
    one.set(i, two.get(j));
    two.set(j, tmp);
}