Queries in a Matrix

Given two integers m and n representing the dimensions of a matrix mat[][] of size m × n, the matrix is initially filled with numbers from 1 to m × n in row-major order.

You are also given a 2D array queries[][] of size q × 3. Each query is of the form [t, x, y], where:

If t = 1, swap the x-th and y-th rows of the matrix.
If t = 2, swap the x-th and y-th columns of the matrix.
If t = 3, print the element at position (x, y).

Process all the queries in order and output the result for each query of type 3.

Examples:

Input: m = 3, n = 3
query[][] = [[1, 0, 1],
[3, 0, 0],
[3, 1, 0],
[2, 0, 1],
[3, 0, 0],
[3, 1, 0]]
Output: [4 , 1, 5, 2]
Explanation: Initially the matrix is:
mat[][] = [[1, 2, 3],
[4, 5, 6],
[7, 8, 9]]
First Operation [1, 0, 1]: We need to swap row 0 and row 1.
After this operation, matrix becomes:
mat[][] =[[4, 5, 6],
[1, 2, 3],
[7, 8, 9]]
For the next two operation, we are required to print the elements at given cells.
Fourth Operation [2, 0, 1]: We need to swap column 0 and column 1.
After this operation matrix becomes:
mat[][] =[[5, 4, 6],
[2, 1, 3],
[8, 7, 9]]
For the next two operation, we are required to print the elements at given cells.

Try it on GfG Practice

Table of Content

[Naive Approach] - O(q × n) Time and O(m × n) Space
[Expected Approach] - Using Auxiliary Arrays - O(q) Time and O(m + n) Space

[Naive Approach] - O(q × n) Time and O(m × n) Space

The idea is to create a matrix mat[][] of order m*n, initially filled with integers from 1 to m × n sequentially in a row-major order. For the queries of type 1 and 2, i.e. swap, traverse required row or column and swap the each of its elements. And for the query of type 3, i.e. print, we simply print the element at specified index.

C++

#include <iostream>
#include<vector>
using namespace std;

// function to swap rows of the matrix.
void swapRows(vector<vector<int>> &mat, int r1, int r2) {
    for (int i = 0; i < mat[0].size(); i++) {
        swap(mat[r1][i], mat[r2][i]);
    }
}

// function to swap columns of the matrix.
void swapCols(vector<vector<int>> &mat, int c1, int c2) {
    for (int i = 0; i < mat.size(); i++) {
        swap(mat[i][c1], mat[i][c2]);
    }
}

void solveQueries(int m, int n, vector<vector<int>> &query) {

    // create a matrix or order m*n, filled with
    // values from 1 to m*n.
    vector<vector<int>> mat(m, vector<int>(n));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            mat[i][j] = (i * n) + j + 1;
        }
    }

    for (int i = 0; i < query.size(); i++) {
        
        // type 1 queries
        if (query[i][0] == 1) {
            swapRows(mat, query[i][1], query[i][2]);
        }

        // type 2 queries
        else if (query[i][0] == 2) {
            swapCols(mat, query[i][1], query[i][2]);
        }

        // type 3 queries
        else {
            cout << mat[query[i][1]][query[i][2]] << " ";
        }
    }
}

int main() {
    int m = 3, n = 3;
    vector<vector<int>> query = {{1, 0, 1},
                                 {3, 0, 0},
                                 {3, 1, 0},
                                 {2, 0, 1},
                                 {3, 0, 0},
                                 {3, 1, 0}};
    solveQueries(m, n, query);
    return 0;
}

Java

public class GfG {

    // function to swap rows of the matrix.
    static void swapRows(int[][] mat, int r1, int r2) {
        for (int i = 0; i < mat[0].length; i++) {
            int temp = mat[r1][i];
            mat[r1][i] = mat[r2][i];
            mat[r2][i] = temp;
        }
    }

    // function to swap columns of the matrix.
    static void swapCols(int[][] mat, int c1, int c2) {
        for (int i = 0; i < mat.length; i++) {
            int temp = mat[i][c1];
            mat[i][c1] = mat[i][c2];
            mat[i][c2] = temp;
        }
    }

    static void solveQueries(int m, int n, int[][] query) {

        // create a matrix of order m*n, filled with values from 1 to m*n.
        int[][] mat = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                mat[i][j] = (i * n) + j + 1;
            }
        }

        for (int i = 0; i < query.length; i++) {

            // type 1 queries
            if (query[i][0] == 1) {
                swapRows(mat, query[i][1], query[i][2]);
            }

            // type 2 queries
            else if (query[i][0] == 2) {
                swapCols(mat, query[i][1], query[i][2]);
            }

            // type 3 queries
            else {
                System.out.print(mat[query[i][1]][query[i][2]] + " ");
            }
        }
    }

    public static void main(String[] args) {
        int m = 3, n = 3;
        int[][] query = {
            {1, 0, 1},
            {3, 0, 0},
            {3, 1, 0},
            {2, 0, 1},
            {3, 0, 0},
            {3, 1, 0}
        };

        solveQueries(m, n, query);
    }
}

Python

# function to swap rows of the matrix.
def swapRows(mat, r1, r2):
    for i in range(len(mat[0])):
        mat[r1][i], mat[r2][i] = mat[r2][i], mat[r1][i]


# function to swap columns of the matrix.
def swapCols(mat, c1, c2):
    for i in range(len(mat)):
        mat[i][c1], mat[i][c2] = mat[i][c2], mat[i][c1]


def solveQueries(m, n, query):

    # create a matrix of order m*n, filled with values from 1 to m*n.
    mat = [[(i * n) + j + 1 for j in range(n)] for i in range(m)]

    for q in query:

        # type 1 queries
        if q[0] == 1:
            swapRows(mat, q[1], q[2])

        # type 2 queries
        elif q[0] == 2:
            swapCols(mat, q[1], q[2])

        # type 3 queries
        else:
            print(mat[q[1]][q[2]], end=" ")


if __name__ =="__main__":
    m, n = 3, 3
    query = [
        [1, 0, 1],
        [3, 0, 0],
        [3, 1, 0],
        [2, 0, 1],
        [3, 0, 0],
        [3, 1, 0]
    ]
    
    solveQueries(m, n, query)

using System;

class GfG
{
    // function to swap rows of the matrix.
    static void SwapRows(int[,] mat, int r1, int r2)
    {
        int cols = mat.GetLength(1);
        for (int i = 0; i < cols; i++)
        {
            int temp = mat[r1, i];
            mat[r1, i] = mat[r2, i];
            mat[r2, i] = temp;
        }
    }

    // function to swap columns of the matrix.
    static void SwapCols(int[,] mat, int c1, int c2)
    {
        int rows = mat.GetLength(0);
        for (int i = 0; i < rows; i++)
        {
            int temp = mat[i, c1];
            mat[i, c1] = mat[i, c2];
            mat[i, c2] = temp;
        }
    }

    static void SolveQueries(int m, int n, int[][] query)
    {
        // create a matrix of order m*n, filled with values from 1 to m*n.
        int[,] mat = new int[m, n];
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                mat[i, j] = (i * n) + j + 1;
            }
        }

        for (int i = 0; i < query.Length; i++)
        {
            // type 1 queries
            if (query[i][0] == 1)
            {
                SwapRows(mat, query[i][1], query[i][2]);
            }

            // type 2 queries
            else if (query[i][0] == 2)
            {
                SwapCols(mat, query[i][1], query[i][2]);
            }

            // type 3 queries
            else
            {
                Console.Write(mat[query[i][1], query[i][2]] + " ");
            }
        }
    }

    static void Main()
    {
        int m = 3, n = 3;
        int[][] query = new int[][]
        {
            new int[]{1, 0, 1},
            new int[]{3, 0, 0},
            new int[]{3, 1, 0},
            new int[]{2, 0, 1},
            new int[]{3, 0, 0},
            new int[]{3, 1, 0}
        };

        SolveQueries(m, n, query);
    }
}

JavaScript

// function to swap rows of the matrix.
function swapRows(mat, r1, r2) {
    for (let i = 0; i < mat[0].length; i++) {
        let temp = mat[r1][i];
        mat[r1][i] = mat[r2][i];
        mat[r2][i] = temp;
    }
}

// function to swap columns of the matrix.
function swapCols(mat, c1, c2) {
    for (let i = 0; i < mat.length; i++) {
        let temp = mat[i][c1];
        mat[i][c1] = mat[i][c2];
        mat[i][c2] = temp;
    }
}

function solveQueries(m, n, query) {

    // create a matrix of order m*n, filled with values from 1 to m*n.
    let mat = Array.from({ length: m }, (_, i) =>
        Array.from({ length: n }, (_, j) => (i * n) + j + 1)
    );

    for (let i = 0; i < query.length; i++) {

        // type 1 queries
        if (query[i][0] === 1) {
            swapRows(mat, query[i][1], query[i][2]);
        }

        // type 2 queries
        else if (query[i][0] === 2) {
            swapCols(mat, query[i][1], query[i][2]);
        }

        // type 3 queries
        else {
            process.stdout.write(mat[query[i][1]][query[i][2]] + " ");
        }
    }
}


// Driver code
let m = 3, n = 3;
let query = [
    [1, 0, 1],
    [3, 0, 0],
    [3, 1, 0],
    [2, 0, 1],
    [3, 0, 0],
    [3, 1, 0]
];

solveQueries(m, n, query);

Output

4 1 5 2

[Expected Approach] - Using Auxiliary Arrays - O(q) Time and O(m + n) Space

The element at any position mat[x][y] in the matrix can be described as mat[x][y] = (n*x) + y + 1, where n is the count of columns. Instead of modifying the matrix directly, we can use two auxiliary arrays, rows[m] and cols[n]. The rows array is initialized with values from 0 to m-1, representing the indices of the rows, and the cols array is initialized with values from 0 to n-1, representing the indices of the columns.
To process a query of type 1, which swaps rows x and y, we simply swap the values of rows[x] and rows[y]. Similarly, for a query of type 2, which swaps columns x and y, we swap the values of cols[x] and cols[y]. For a query of type 3, which print the value at position (x, y), we calculate the position using the formula, mat[x][y] = rows[x]*n + cols[y] + 1.

C++

#include <iostream>
#include<vector>
using namespace std;

void solveQueries(int m, int n, vector<vector<int>> &query) {

    // create two arrays rows and cols
    // and fill the value from 0 to size-1
    vector<int> rows(m), cols(n);
    for(int i = 0; i < m; i++) {
        rows[i] = i;
    }
    for(int i = 0; i < n; i++) {
        cols[i] = i;
    }

    for (int i = 0; i < query.size(); i++) {

        // type 1
        if (query[i][0] == 1) {
            swap(rows[query[i][1]], rows[query[i][2]]);
        }

        // type 2
        else if (query[i][0] == 2) {
            swap(cols[query[i][1]], cols[query[i][2]]);
        }

        // type 3
        else {
            cout<< (rows[query[i][1]] * n) + cols[query[i][2]] + 1 << " ";
        }
    }
}

int main() {
    int m = 3, n = 3;
    vector<vector<int>> query = {{1, 0, 1},
                                 {3, 0, 0},
                                 {3, 1, 0},
                                 {2, 0, 1},
                                 {3, 0, 0},
                                 {3, 1, 0}};
    solveQueries(m, n, query);
    return 0;
}