Queries in a Matrix - GeeksforGeeks

Queries in a Matrix - GeeksforGeeks
Given a matrix M of size m x n ( 1 <= m,n <= 1000 ). It is initially filled with integers from 1 to m x n sequentially in a row major order. The task is to process a list of queries manipulating M such that every query is one of the following three.

1. R(x, y): swaps the x-th and y-th rows of M where x and y vary from 1 to m.
2. C(x, y): swaps the x-th and y-th columns of M where x and y vary from 1 to n.
3. P(x, y): prints the element at x-th row and y-th column where x varies from 1 to m and y varies from 1 to n.

Note that the given matrix is stored as a typical 2D array with indexes start from 0, but values of x and y start from 1.

A simple solution for this problem is to finish all the queries manually, that means when we have to swap the rows just swap the elements of x’th row and y’th row and similarly for column swamping. But this approach may have time complexity of q*O(m) or q*O(n) where ‘q’ is number of queries and auxiliary space required O(m*n).

An efficient approach for this problem requires little bit mathematical observation. Here we are given that elements in matrix are filled from 1 to mxn sequentially in row major order, so we will take advantage of this given scenario and can solve this problem.

• Create an auxiliary array rows[m] and fill it with values 0 to m-1 sequentially.
• Create another auxiliary array cols[n] and fill it with values 0 to n-1 sequentially.
• Now for query ‘R(x, y)’ just swap the value of rows[x-1] with rows[y-1].
• Now for query ‘C(x, y)’ just swap the value of cols[x-1] with cols[y-1].
• Now for query ‘P(x, y)’ just skip the number of columns you have seen and calculate the value at (x, y) by rows[x-1]*n + cols[y-1] + 1.

Time complexity : O(q) , q = number of queries
Axillary space : O(m+n)

// Fills initial values in rows[] and cols[]

void preprocessMatrix(int rows[], int cols[],

                     int m, int n)

{

    // Fill rows with 1 to m-1

    for (int i=0; i<m; i++)

        rows[i] = i;

    // Fill columns with 1 to n-1

    for (int i=0; i<n; i++)

        cols[i] = i;

}

// Function to perform queries on matrix

// m --> number of rows

// n --> number of columns

// ch --> type of query

// x --> number of row for query

// y --> number of column for query

void queryMatrix(int rows[], int cols[], int m,

                 int n, char ch, int x, int y)

{

    // perform queries

    int tmp;

    switch(ch)

    {

    case 'R':

        // swap row x with y

        swap(rows[x-1], rows[y-1]);

        break;

    case 'C':

        // swap coloumn x with y

        swap(cols[x-1], cols[y-1]);

        break;

    case 'P':

        // Print value at (x, y)

        printf("value at (%d, %d) = %d\n", x, y,

                   rows[x-1]*n + cols[y-1]+1);

        break;

    }

    return ;

}

Read full article from Queries in a Matrix - GeeksforGeeks