How would you implement an efficient in-place algorithm on a 2D array, such as rotating a matrix 90 degrees, while minimizing extra memory allocation?

Advanced

Answer

An in-place rotation can be achieved through a combination of transposing the matrix (swapping matrix[i][j] with matrix[j][i] across the diagonal) followed by reversing each row (or column, depending on rotation direction), avoiding the need to allocate an entirely new matrix -- this two-step decomposition is a classic technique that reduces an seemingly complex 2D transformation into two simpler, well-understood O(n²) operations performed directly on the existing array structure.

public static void rotate90Clockwise(int[][] matrix) {
    int n = matrix.length;
    // Step 1: transpose in place
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }
    // Step 2: reverse each row
    for (int[] row : matrix) {
        for (int left = 0, right = row.length - 1; left < right; left++, right--) {
            int temp = row[left];
            row[left] = row[right];
            row[right] = temp;
        }
    }
}

Real-world example An image-processing utility rotating a pixel matrix representing a small icon uses the transpose-then-reverse in-place technique to avoid allocating a second full-size matrix, meaningful for memory-constrained environments processing many images where allocation overhead would otherwise add up significantly.

Common follow-ups: What's the time and space complexity of this in-place approach compared to a naive approach allocating a new rotated matrix?;How would this algorithm need to change for a non-square (rectangular) matrix?

Diagnostics & Performance;Garbage Collection

All 15 Arrays & Multidimensional Arrays questions