Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Test Case
3.1.
Input
3.2.
Output
3.3.
Explanation
4.
Solution
4.1.
Algorithm
4.2.
Implementation
4.2.1.
C++ Code
4.2.2.
Java Code
4.2.3.
Python  Code
4.3.
Output
4.4.
Complexity Analysis
5.
Row-wise vs Column-wise Traversal
6.
Frequently Asked Questions
6.1.
What is row-major traversal?
6.2.
What is column-major traversal?
6.3.
Which one of the traversal among row-major and column-major gives better performance for traversing a matrix?
6.4.
What is the time and space complexity of traversing a matrix?
7.
Conclusion
Last Updated: Mar 27, 2024
Easy

Row-wise vs Column-wise Traversal of a Matrix

Author Aniket Majhi
1 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

Welcome readers! We hope that you are doing great.

Matrices are essential concepts for programmers, as they contribute to building the fundamental concepts of good programmers.

Today we will discuss the Row-wise vs Column-wise Traversal of a Matrix with a proper explanation and diagram.

After reading this blog, you will get an insight into row-major and column-major traversal of matrices in great detail, and you will be able to find out the difference between these traversals. Also, you will get an idea about which one should you prefer in the future.

So, without wasting any more time, let’s start our discussion.

Recommended Topic, Array Implementation of Queue and  Rabin Karp Algorithm

Problem Statement

Given a matrix of size MxN, you need to traverse the matrix both row-wise and column-wise and print the order of the elements for both the traversals.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Test Case

Below is the test case.

Input

{
 {1,2,3},
 {4,5,6},
 {7,8,9}
}

Output

Row-wise traversal: {1,2,3,4,5,6,7,8,9}
Column-wise traversal: {1,4,7,2,5,8,3,6,9}

Explanation

Given Matrix is,

For the Row-wise traversal, you need to print row 1 first, row 2, and row 3, as shown below.

Hence, the output is {1,2,3,4,5,6,7,8,9}.

For the Column-wise traversal, you need to print col1 first, then col 2, and then col 3, as shown below.

Hence the output is {1,4,7,2,5,8,3,6,9}.

We hope that the question is clear to you. Let’s now move to the solution part.

Solution

This problem has a simple solution. You just need to traverse through the whole matrix.

For row-wise traversal, first, you need to visit each row one by one, starting from the first to the last row, then print values in each row.

For column-wise traversal, you need to visit each column, starting from the first to the last, and then print each column's elements.

Below is the algorithm.

Algorithm

  • Create an 2D array(arr[][]) of size MxN, for representing the 2D Matrix.
     
  • For row-wise traversal, start a loop from i = 0 to(traversing row by row) and for each iteration of the loop(for each row), start a nested loop from j = 0 to N(traverse each elements of the row) and print the element at arr[i][j].
     
  • For column-wise traversal, start a loop from i=0 to N(traversing column by column) and fro each iteration of the loop(for each column), start a nested loop from j = 0 to M(traverse each elements of the column) and orint element ar arr[j][i].

Implementation

Now, we will implement the above algorithm in different languages.

C++ Code

#include<bits/stdc++.h>
using namespace std;
 
int main() {
 
    int m = 3;
    int n = 3;
 
    int arr[m][n] = {{1 , 2 , 3},
                    {4 , 5 , 6},
                    {7 , 8 , 9}};
 
    // Row-wise traversal
 
    cout << "Row-wise traversal: ";
 
    for(int i = 0 ; i < m ; i++) {
        // for each rows(i = 0 to m) we are printing the values
        for(int j = 0; j < n ; j++) {
            cout << arr[i][j] <<" ";
        }
    }
 
    //Column-wise traversal
 
    cout << "\nColumn-wise traversal: ";
 
    for(int i = 0; i < n ; i++) {
        // for each columns(i = 0 to n) we are printing values
        for(int j = 0 ;j < m ; j++) {
            cout << arr[j][i] <<" ";
        }
    }
 
    return 0;
 
}

Java Code

class Main{
    public static void main(String[] args) {
        // given matrix
        int m = 3;
        int n = 3;
        int[][] arr = {{1, 2, 3} , {4, 5, 6} , {7, 8, 9}};

        // Row-wise traversal
        System.out.print("Row-wise traversal: ");
        for(int i = 0; i < m ; i++) {
            for(int j = 0; j < n ; j++) {
                System.out.print(arr[i][j] + " ");
            }
        }

        // Column-wise traversal
        System.out.print("\nColumn-wise traversal: ");
        for(int i = 0; i < m ; i++) {
            for(int j = 0; j < n ; j++) {
                System.out.print(arr[j][i] + " ");
            }
        }
    }
}

Python  Code

m = 3
n = 3
arr =  [[1, 2, 3],
           [4, 5, 6],
           [7, 8, 9]]
# Row-wise traversal
print("Row-wise traversal:", end = " ")
for i in range(0 , m):
    for j in range(0 , n):
        print(arr[i][j],end=" ")

# Column-wise traversal
print("\nColumn-wise traversal:", end=" ")
for i in range(0 , m):
    for j in range(0 , n):
        print(arr[j][i], end=" ")

Output

Row-wise traversal: 1 2 3 4 5 6 7 8 9 
Column-wise traversal: 1 4 7 2 5 8 3 6 9 

Complexity Analysis

Time complexity: O(MN)

Space complexity: O(1) 

Row-wise vs Column-wise Traversal

As we saw earlier, both the row-wise and column-wise traversal has a time complexity O(MN). But, if we want to compare the performance between these traversals, you will find that one of the traversals becomes slower than the other. 

An algorithm's performance also depends on how the elements are accessed. In this case, it depends on how the matrix is stored in the memory.

  • If the matrix is stored in the memory in row-major order(often), consecutive elements of the rows are contiguous in memory. Reading memory in contiguous memory locations is faster than jumping to other locations. So, here row-major traversal will give better performance than the column-major traversal.
     
  • Similarly, suppose the matrix is stored in the memory in column-major order. In that case, the column-major traversal will perform better than the row-major traversal for the same reason mentioned above.

 

Also, see Array in Java

Frequently Asked Questions

What is row-major traversal?

While traversing a 2D matrix, if we traverse the matrix row by row, it is called row-major traversal.
 

What is column-major traversal?

While traversing a 2D matrix, if we traverse the matrix column by column, it is called column-major traversal.
 

Which one of the traversal among row-major and column-major gives better performance for traversing a matrix?

It depends on how the matrix is stored in the memory. If the matrix is stored in the memory in row-major order, then the row-major traversal will perform better than the column-major traversal and vice versa.
 

What is the time and space complexity of traversing a matrix?

Time complexity: O(MN)

Space complexity: O(1)

Conclusion

In this article, we have extensively discussed Row-wise vs Column-wise Traversal of a Matrix

We started with the basic introduction, then we discussed,

  • The Problem Statement
  • One Test Case
  • Solution
  • Finally, we discussed the difference between these two traversals.
     

We hope this blog has helped you enhance your knowledge regarding Row-wise vs Column-wise Traversal of a Matrix.

Recommended problems -

 

If you want to learn more, follow our articles on Operation On Matrices, How to Multiply Two Matrices, and  Minimum Sum Path in a Matrix.

Explore our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, interview bundle, follow guided paths for placement preparations, and much more.!

Please upvote this blog to help other ninjas grow.

Happy Reading!

Previous article
Print X’th element in the spiral form of a matrix
Next article
Find Sum of all Elements in a Matrix except the Elements in Row and/or Column of Given Cell
Live masterclass