Matrix Multiplication

package jan22_2D_Array;

import java.util.Scanner;

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

        Scanner sc = new Scanner(System.in); // O(1) time, O(1) space

        int r1 = sc.nextInt(); // O(1)
        int c1 = sc.nextInt(); // O(1)
        int[][] arr1 = new int[r1][c1]; // O(r1 * c1) space

        for (int i = 0; i < arr1.length; i++) { // O(r1)
            for (int j = 0; j < arr1[0].length; j++) { // O(c1)
                arr1[i][j] = sc.nextInt(); // O(1)
            }
        }

        int r2 = sc.nextInt(); // O(1)
        int c2 = sc.nextInt(); // O(1)
        int[][] arr2 = new int[r2][c2]; // O(r2 * c2) space

        for (int i = 0; i < arr2.length; i++) { // O(r2)
            for (int j = 0; j < arr2[0].length; j++) { // O(c2)
                arr2[i][j] = sc.nextInt(); // O(1)
            }
        }

        if (c1 != r2) { // O(1)
            System.out.println("Invalid Input"); // O(1)
            return; // EXIT early if invalid
        }

        int[][] product = new int[r1][c2]; // O(r1 * c2) space

        // Matrix Multiplication: O(r1 * c2 * c1)
        for (int i = 0; i < product.length; i++) { // O(r1)
            for (int j = 0; j < product[0].length; j++) { // O(c2)
                for (int k = 0; k < c1; k++) { // O(c1)
                    product[i][j] += arr1[i][k] * arr2[k][j]; // O(1)
                }
            }
        }

        // Output result: O(r1 * c2)
        for (int i = 0; i < product.length; i++) { // O(r1)
            for (int j = 0; j < product[0].length; j++) { // O(c2)
                System.out.print(product[i][j] + " "); // O(1)
            }
            System.out.println(); // O(1)
        }

    }
}

✅ Time Complexity

Case	Time Complexity	Explanation
Best	O(r1 × c2 × c1)	All inputs are valid and multiplication is performed.
Average	O(r1 × c2 × c1)	Typical case with no input errors.
Worst	O(r1 × c2 × c1)	Still the same, as all elements must be multiplied once regardless.

---

💾 Space Complexity

Case	Space Complexity	Explanation
Best	O(r1 × c1 + r2 × c2 + r1 × c2)	For input and output matrices.
Average	O(r1 × c1 + r2 × c2 + r1 × c2)	Same as best — no dynamic variation.
Worst	O(r1 × c1 + r2 × c2 + r1 × c2)	No space optimization — full storage used.