LeetCode 48. Rotate Image

https://leetcode.com/problems/rotate-image/description/ 

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

 

Input: 

3

1 2 3

4 5 6

7 8 9

Output:

Transpose of a Matrix

1 4 7 

2 5 8 

3 6 9 

Reverse of Matrix

7 4 1 

8 5 2 

9 6 3 

package jan22;

import java.util.Scanner;

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

        Scanner scanner = new Scanner(System.in);  // O(1) space for Scanner object

        int n = scanner.nextInt();  // Input matrix size — O(1)

        int[][] arr = new int[n][n];  // 2D array allocation — SC: O(n^2)

        // Input loop — reads n^2 elements — TC: O(n^2)
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = scanner.nextInt();  // O(1) per element
            }
        }

        // Transpose the matrix — upper triangle only — TC: O(n^2)
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int temp = arr[i][j];
                arr[i][j] = arr[j][i];  // Swap elements to transpose
                arr[j][i] = temp;
            }
        }

        display(arr);  // Print transposed matrix — TC: O(n^2)

        // Reverse each row — completes the clockwise rotation — TC: O(n^2)
        for (int i = 0; i < n; i++) {
            reverseArray(arr[i], 0, arr[i].length - 1);  // O(n) per row
        }

        display(arr);  // Print rotated matrix — TC: O(n^2)

    }

    private static void reverseArray(int[] arr, int left, int right) {
        // In-place array reversal — TC: O(n), SC: O(1)
        while (left < right) {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }

    public static void display(int[][] arr) {
        // Print 2D array — TC: O(n^2)
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                System.out.print(arr[i][j] + " ");  // O(1)
            }
            System.out.println();  // O(1) per row
        }
    }
}

⏱ Time Complexity Summary

Case
Time Complexity
Explanation
Best
O(n²)
Always processes full matrix regardless of values.
Average
O(n²)
No early stopping — every element is touched.
Worst
O(n²)
Full input, transpose, row reversal, and display calls.

💾 Space Complexity Summary

Case
Space Complexity
Explanation
Best
O(n²)
2D array occupies n² space, no extra space used.
Average
O(n²)
Same as best — all operations are in-place.
Worst
O(n²)
Still just the matrix and constant space for temp vars.