The reader is advised to read all the lessons (tutorials) in this full course, in the order presented.

Row-Wise Traversal

Example

Input: 
mat[][] = {{1, 2, 3}, 
          {4, 5, 6}, 
          {7, 8, 9}}

Output:
1 2 3 4 5 6 7 8 9

Note: With row-wise traversal, the first row is traversed from left to right, then the second row traversed from left to right, and the third row traversed from left to right. This would continue if there are more rows down.

Row-Wise Traversal Program

The program to illustrate row-wise traversal is (read through the code and comments):

#include <stdio.h>

void rowWiseTraversal (int mat[][3], int n, int m) {
    for (int i=0; i < n; i++) {    //visit rows
        for (int j=0; j < m; j++) {    //then column cells
            printf("%i ", mat[i][j]);
        }
        printf("\n");
    }
}

int main() {

    int mat3b3[3][3];
    mat3b3[0][0] = 1; mat3b3[0][1] = 2; mat3b3[0][2] = 3; 
    mat3b3[1][0] = 4; mat3b3[1][1] = 5; mat3b3[1][2] = 6; 
    mat3b3[2][0] = 7; mat3b3[2][1] = 8; mat3b3[2][2] = 9; 
    
    int n=3, m=3;

    rowWiseTraversal (mat3b3, n, m);

    return 0;
}

The output is:

1 2 3 
4 5 6 
7 8 9 

The time complexity is actually O(2 x n x m), where 'n x m' refers to the time to iterate over all the elements in the matrix (2D array), in the called function. This same amount of time is needed to populate the matrix with numbers, one-by-one, in the calling function area of the program. And so that makes '2 x n x m'. However, the coefficient (multiplicand of 2) is normally omitted when quoting the time complexity. The time complexity here is quoted as O(n x m).

The space complexity is O(n x m) for the matrix. The 2D array in the calling function area in the code and the 2D array in the called function, are the same array (same reference).

Column-Wise Traversal

Example

Input: 
mat[][] = {{1, 2, 3}, 
          {4, 5, 6}, 
          {7, 8, 9}}

Output:
1 4 7 2 5 8 3 6 9

Note: With column-wise traversal, the first column is traversed from top to bottom, then the second column traversed top to bottom, and the third column traversed top to bottom. This would continue if there are more columns to the right.

Column-Wise Traversal Program

The program to illustrate column-wise traversal is (read through the code and comments):

#include <stdio.h>

void columnWiseTraversal (int mat[][3], int n, int m) {
    for (int j=0; j < m; j++) {    //visit column
        for (int i=0; i < n; i++) {    //then row cells
            printf("%i ", mat[i][j]);    //should not change compared to row-wise traversal
        }
        printf("\n");
    }
}

int main() {

    int mat3b3[3][3];
    mat3b3[0][0] = 1; mat3b3[0][1] = 2; mat3b3[0][2] = 3; 
    mat3b3[1][0] = 4; mat3b3[1][1] = 5; mat3b3[1][2] = 6; 
    mat3b3[2][0] = 7; mat3b3[2][1] = 8; mat3b3[2][2] = 9; 
    
    int n=3, m=3;

    columnWiseTraversal (mat3b3, n, m);

    return 0;
}

The output is:

1 4 7 
2 5 8 
3 6 9 

The time complexity is actually O(2 x n x m), where 'n x m' refers to the time to iterate over all the elements in the matrix (2D array). This same amount of time is needed to populate the matrix with numbers, one-by-one, in the calling function area of the program. And so that makes '2 x n x m'. However, the coefficient (multiplicand of 2) is normally omitted when quoting the time complexity.

The space complexity is O(n x m) for the matrix. The 2D array in the calling function area in the code and the 2D array in the called function, are the same array (same reference).

O(N x M) Search in a Matrix

Consider the following matrix (2D array):

mat[][] = {{1, 2, 3}, 
          {4, 5, 6}, 
          {7, 8, 9}}

The element, 5 can be looked for, by iterating over each row beginning from the top. This is said to take O(n x m) time, because the element being searched, can be at the last row and last column cell. The maximum possible time is what is quoted.

O(NxM) Search in a Matrix Program

In the following program, a number is looked for. If it is present in the matrix, the number is returned. If the number is not present, -1 is returned. Read through the code and comments:

#include <stdio.h>

int searchRowWise (int mat[][3], int n, int m) {
    for (int i=0; i < n; i++) {    //visit rows
        for (int j=0; j < m; j++) {    //then column cells
            if (mat[i][j] == 5)
                return mat[i][j];
        }
    }
    
    return -1;
}

int main() {

    int mat3b3[3][3];
    mat3b3[0][0] = 1; mat3b3[0][1] = 2; mat3b3[0][2] = 3; 
    mat3b3[1][0] = 4; mat3b3[1][1] = 5; mat3b3[1][2] = 6; 
    mat3b3[2][0] = 7; mat3b3[2][1] = 8; mat3b3[2][2] = 9; 
    
    int n=3, m=3;

    int ret = searchRowWise (mat3b3, n, m);
    printf("%i\n", ret);

    return 0;
}

Actually, the first occurrence of the element is really what is looked for. The output for this program is 5.

If there are more than one return statement in a function, only one is executed. In the above program, there are two return statements in the searchRowWise() function. If the element is seen, the first return statement returns the element. If the element is not seen, it means the iteration reached the cell for the last row and last column, and not able to see the element. In this case, the first return statement could not be executed. So the second and last return statement in the function is executed.

The time complexity is actually O(2 x n x m), where 'n x m' refers to the time to iterate over all the elements in the matrix (2D array). This same amount of time is needed to populate the matrix with numbers, one-by-one, in the calling function area of the program. And so that makes '2 x n x m'. However, the coefficient (multiplicand of 2) is normally omitted when quoting the time complexity.

The space complexity is O(n x m) for the matrix. The 2D array in the calling function area in the code and the 2D array in the called function, are the same array (same reference).

Thanks for reading.