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 M (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;
}
You can also try this code with Online C++ Compiler
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] + " ");
}
}
}
}
You can also try this code with Online Java Compiler
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=" ")
You can also try this code with Online Python Compiler
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!
84+ registered