Left Rotate Matrix K times

You are given an integer k andmatrix mat. Return a matrix where it is rotated Left k times.

Examples:

Input: k=1, mat=[[1,2,3],[4,5,6],[7,8,9]]
Output:
1 2 3
4 5 6
7 8 9
Explanation: Rotate the matrix by one
1 2 3         2 3 1
4 5 6  =>  5 6 4
7 8 9       
  8 9 7

Input: k=2, mat=[[1,2,3],[4,5,6],[7,8,9]]
Output:
3 1 2
6 4 5
9 7 8
Explanation: After rotating the matrix looks like
1 2 3       2 3 1       3 1 2
4 5 6  =>  5 6 4  =>   6 4 5
7 8 9       8 9 7      9 7 8

Expected Time Complexity: O(n*m)
Expected Auxillary Space: O(n*m)

Constraints:
1<= mat.size, mat[0].size, mat[i][j] <=1000
1<=k<=10000

Approach 01:

#include <vector>
#include <algorithm> // For the swap function

using namespace std;

class Solution {
public:
    void reverseArray(vector<int>& arr, int low, int high) {
        while (low < high) {
            swap(arr[low], arr[high]);
            low++;
            high--;
        }
    }

    vector<vector<int>> rotateMatrix(int k, vector<vector<int>>& matrix) {
        int rows = matrix.size();
    
        for (int i = 0; i < rows; i++) {
            int cols = matrix[i].size();
            int num_rotations = k % cols;
            
            reverseArray(matrix[i], 0, num_rotations - 1);
            reverseArray(matrix[i], num_rotations, cols - 1);
            reverseArray(matrix[i], 0, cols - 1);
        }
        
        return matrix;
    }
};

from typing import List

class Solution:
    def reverse_array(self, arr: List[int], low: int, high: int) -> None:
        while low < high:
            arr[low], arr[high] = arr[high], arr[low]
            low += 1
            high -= 1

    def rotateMatrix(self, k: int, matrix: List[List[int]]) -> List[List[int]]:
        rows = len(matrix)
    
        for i in range(rows):
            cols = len(matrix[i])
            num_rotations = k % cols
            
            self.reverse_array(matrix[i], 0, num_rotations - 1)
            self.reverse_array(matrix[i], num_rotations, cols - 1)
            self.reverse_array(matrix[i], 0, cols - 1)
        
        return matrix

Time Complexity

• The time complexity of the rotate_matrix function is \( O(r \cdot c) \), where \( r \) is the number of rows and \( c \) is the number of columns in the matrix.
• For each row, we perform three reversals, each taking \( O(c) \) time, leading to a total time complexity of \( O(r \cdot c) \).

Space Complexity

• The space complexity of the rotate_matrix function is \( O(1) \).
• This is because we are performing the operations in-place without using any additional data structures that grow with the size of the input.