Shell Rotate 2 in 2D Array

Input:

4

4

1    2    3     4

5    6    7     8

9   10  11   12

13 14  15   16

Shell: 2 

k = 3

Output:

1     2    3    4 

5    10   6    8 

9    11   7   12 

13  14  15  16 

package jan22;

import java.util.Scanner;

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

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

        int m = scanner.nextInt();  // O(1)
        int n = scanner.nextInt();  // O(1)

        int[][] arr = new int[m][n];  // SC: O(m * n) for matrix

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

        int shellNumber = scanner.nextInt();  // O(1)
        int rotateCount = scanner.nextInt();  // O(1)

        rotate(arr, shellNumber, rotateCount);  // Main rotation logic

        display(arr);  // TC: O(m * n)
    }

    private static void rotate(int[][] arr, int shellNumber, int rotateCount) {

        // Compute shell boundaries — O(1)
        int min_row = shellNumber - 1,
                min_col = shellNumber - 1,
                max_row = arr.length - shellNumber,
                max_col = arr[0].length - shellNumber;

        int total_elements = 2 * (max_row - min_row) + 2 * (max_col - min_col);  // O(1)
        int[] one_d_array = new int[total_elements];  // SC: O(m + n) (for 1 shell)

        int idx = 0;

        // Extract left wall — O(m)
        for (int i = min_row; i <= max_row; i++) one_d_array[idx++] = arr[i][min_col];

        min_col++;

        // Extract bottom wall — O(n)
        for (int i = min_col; i <= max_col; i++) one_d_array[idx++] = arr[max_row][i];

        max_row--;

        // Extract right wall — O(m)
        for (int i = max_row; i >= min_row; i--) one_d_array[idx++] = arr[i][max_col];

        max_col--;

        // Extract top wall — O(n)
        for (int i = max_col; i >= min_col; i--) one_d_array[idx++] = arr[min_row][i];

        min_row++;

        rotateOneD(one_d_array, rotateCount);  // Rotate the extracted shell — TC: O(m + n)

        // Reinitialize boundaries — O(1)
        min_row = shellNumber - 1;
        min_col = shellNumber - 1;
        max_row = arr.length - shellNumber;
        max_col = arr[0].length - shellNumber;

        idx = 0;

        // Fill left wall — O(m)
        for (int i = min_row; i <= max_row; i++) arr[i][min_col] = one_d_array[idx++];

        min_col++;

        // Fill bottom wall — O(n)
        for (int i = min_col; i <= max_col; i++) arr[max_row][i] = one_d_array[idx++];

        max_row--;

        // Fill right wall — O(m)
        for (int i = max_row; i >= min_row; i--) arr[i][max_col] = one_d_array[idx++];

        max_col--;

        // Fill top wall — O(n)
        for (int i = max_col; i >= min_col; i--) arr[min_row][i] = one_d_array[idx++];

        min_row++;
    }

    private static void rotateOneD(int[] arr, int k) {

        int len = arr.length;

        // Normalize k — O(1)
        k = k > len ? k % len : k;
        k = k < 0 ? k + len : k;

        // Reverse 3 segments to rotate — TC: O(n)
        reverseArray(arr, 0, len - k - 1);      // Part 1
        reverseArray(arr, len - k, len - 1);    // Part 2
        reverseArray(arr, 0, len - 1);          // Full array
    }

    private static void reverseArray(int[] arr, int left, int right) {
        // In-place reverse — TC: O(right - left + 1), 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) {
        // Display the matrix — TC: O(m * n)
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();  // Newline per row
        }
    }
}

🚀 Time & Space Complexity Summary

Section	Best Case	Average Case	Worst Case	Space Complexity
Input Reading	O(m * n)	O(m * n)	O(m * n)	O(1) (excluding matrix)
Shell Extraction	O(m + n)	O(m + n)	O(m + n)	O(m + n)
1D Rotation (rotateOneD)	O(k + (n-k) + n) = O(n)	O(n)	O(n)	O(1)
Shell Insertion	O(m + n)	O(m + n)	O(m + n)	O(1)
Display	O(m * n)	O(m * n)	O(m * n)	O(1)
Total	O(m * n)	O(m * n)	O(m * n)	O(m + n)

📌 Explanation in One Line

• TC: The total time is proportional to the number of elements in the matrix since each element is processed once while reading, rotating, and printing.

• SC: Apart from the input matrix, we use an auxiliary 1D array of size ~2(m+n), so space is O(m + n).