Retrieving arrays put in HashMap

Question

The code below is the answer I wrote for a question that asks to rotate an n x n 2D matrix by 90 degrees (clockwise), without creating a new 2D array. So for example,

Given input matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

rotate the input matrix:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

I tried to do it row by row, but the problem I have to deal with is what to do if the pair of index if already altered. So if I try to assign index pair [1, 2] to [0, 1], but then [0,1] is already changed before. The solution I came up with is to use a HashMap, put the index pair in an array as key, and the original number as value.

Here is my code

public void rotate(int[][] matrix) {
        int n = matrix.length;
        HashMap<int[], Integer> map = new HashMap<>();
        for(int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                if(map.containsKey(new int[]{n-j,i})){
                    matrix[i][j] = map.get(new int[]{n-j, i});
                }
                else{
                    int temp = matrix[i][j];
                    matrix[i][j] = matrix[n-j][i]; 
                    map.put(new int[]{n-j,i}, temp);
                }
            }
        }  

    }

However, the result shows that

if(map.containsKey(new int[]{n-j,i})){
                    matrix[i][j] = map.get(new int[]{n-j, i});
                }

this line of code isn't searching for the array I put in before. I know that I am creating a new array every time, but how does it make containsKey not know if the array contains same numbers(the same array)? Can anyone help me understand why using an array here to mark the pair of index isn't working in a HashMap?

Answer 1

You don't need a Map to rotate a matrix. You only need one temp variable.

To rotate a 3x3:

1 2 3
4 5 6
7 8 9

temp = 1, copy corner values around, then save value to next corner:

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

repeat for border values, temp = 2:

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

And you're done, in-place rotation with only 1 value in temp storage, i.e. O(1) memory footprint.

Now I'll let you actually code that, for any size matrix.

---

UPDATE

For the fun of it, I decided to try writing it, so here it is, with test code. I'm not going to explain the logic though, that's for you to figure out yourself.

public static void main(String... args) {
    for (int size : new int[] {2,3,4,5,10}) {
        int[][] matrix = createMatrix(size);
        printMatrix(matrix);
        System.out.println();
        rotateMatrix(matrix);
        printMatrix(matrix);
        printSeparatorLine(matrix);
    }
}
private static int[][] createMatrix(int size) {
    int[][] matrix = new int[size][size];
    for (int y = 0, i = 0; y < size; y++)
        for (int x = 0; x < size; x++)
            matrix[y][x] = ++i;
    return matrix;
}
private static void rotateMatrix(int[][] matrix) {
    for (int y1 = 0; y1 < matrix.length / 2; y1++) {
        for (int y2 = matrix.length - y1 - 1, x1 = y1; x1 < y2; x1++) {
            int x2 =  matrix.length - x1 - 1, temp = matrix[y1][x1];
            matrix[y1][x1] = matrix[x2][y1];
            matrix[x2][y1] = matrix[y2][x2];
            matrix[y2][x2] = matrix[x1][y2];
            matrix[x1][y2] = temp;
        }
    }
}
private static void printMatrix(int[][] matrix) {
    int w = maxValueWidth(matrix);
    for (int[] row : matrix) {
        for (int i = 0; i < row.length; i++)
            System.out.printf("%" + (w + (i == 0 ? 0 : 1)) + "d", row[i]);
        System.out.println();
    }
}
private static void printSeparatorLine(int[][] matrix) {
    char[] buf = new char[(maxValueWidth(matrix) + 1) * matrix.length - 1];
    Arrays.fill(buf, '-');
    System.out.println(new String(buf));
}
private static int maxValueWidth(int[][] matrix) {
    return Arrays.stream(matrix).flatMapToInt(Arrays::stream).map(i -> String.valueOf(i).length()).max().getAsInt();
}

Output

1 2
3 4

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

7 4 1
8 5 2
9 6 3
-----
 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15 16

13  9  5  1
14 10  6  2
15 11  7  3
16 12  8  4
-----------
 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

21 16 11  6  1
22 17 12  7  2
23 18 13  8  3
24 19 14  9  4
25 20 15 10  5
--------------
  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

 91  81  71  61  51  41  31  21  11   1
 92  82  72  62  52  42  32  22  12   2
 93  83  73  63  53  43  33  23  13   3
 94  84  74  64  54  44  34  24  14   4
 95  85  75  65  55  45  35  25  15   5
 96  86  76  66  56  46  36  26  16   6
 97  87  77  67  57  47  37  27  17   7
 98  88  78  68  58  48  38  28  18   8
 99  89  79  69  59  49  39  29  19   9
100  90  80  70  60  50  40  30  20  10
---------------------------------------

Answer 2

You said "this line of code isn't searching for the array I put in before". But you also acknowledge that you were creating a new object each time. That won't work:

Since arrays extend Object, but don't override hashCode() or equals(), you get the default implementations defined by Object. These require that the array is actually the exact same one as is being compared to - so it can't just be 'equivalent'. That is, another array of the same type, with the same elements in the same order, won't work.

Source: https://coderanch.com/t/399422/java/array-HashMap-Key

Instead, you should use a Pair object to store your coordinates. You can write your own implementation or use a pre-existing one, such as javafx.util.Pair