2D-Arrays III
Now that we've explored fundamental matrix operations—such as printing row-wise and column-wise, calculating sums, and identifying maximum and minimum values—let's dive deeper into specific matrix structures. One important concept is the classification of matrices based on their triangular properties. This leads us to the study of upper and lower triangular matrices, which play a significant role in our understanding towards it !!
Q9. Upper Triangle and Lower Triangle Matrix
Example
Input
matrixA[][] = {{10,20,30,40}, {50,60,70,80}, {90,100,110,120}, {130,140,150,160}}
Output
Upper Triangular Matrix:= {{10, 20, 30, 40},{0, 60, 70, 80},{0, 0, 110, 120},{0, 0, 0, 160}}
Lower Triangular Matrix: {{10,0,0,0}, {50,60,0,0}, {90,100,110,0}, {130,140,150,160}}
Intuition
Think of the upper triangle and lower triangle as dividing the matrix into two parts:
- The upper triangle is like a "roof" that includes the diagonal and all values to the right.
- The lower triangle is like a "foundation" that includes the diagonal and all values to the left.
What are Upper and Lower Triangles?
When we talk about the upper triangle and lower triangle, we are referring to parts of a square matrix (a matrix with the same number of rows and columns).
The upper triangle of a matrix consists of all the elements on or above the main diagonal.
The main diagonal runs from the top-left to the bottom-right of the matrix (i.e., positions where the row index = column index). For example, in Matrix A: {{1,2,3},{4,5,6},{7,8,9}}. The Main Diagonal is 1,5,9.
The upper triangle includes these diagonal elements and everything to their right i.e. {{1,2,3},{0,5,6},{0,0,9}}. Here, we set the elements below the diagonal to zero.
The lower triangle of a matrix consists of all the elements on or below the main diagonal. For the same Matrix A= {{1,2,3},{4,5,6},{7,8,9}}, the lower triangle includes these diagonal elements 1,5,9 and everything to their left which is represented as {{1,0,0},{4,5,0},{7,8,9}} .Here, we set the elements above the diagonal to zero.
Approach: Upper Triangle
Initialize Result Matrix: Create a new matrix result with the same dimensions as the input matrix. Fill all entries with 0.
Iterate Through Rows and Columns: For every cell (i, j) in the matrix:
If i <= j (the row index is less than or equal to the column index), copy the value from the input matrix to result[i][j]. Otherwise, leave the cell as 0.
Return the Result Matrix: Output the result matrix, which represents the upper triangle.
Approach: Lower Triangle
Initialize Result Matrix: Create a new matrix result with the same dimensions as the input matrix. Fill all entries with 0.
Iterate Through Rows and Columns: For every cell (i, j) in the matrix:
If i >= j (the row index is greater than or equal to the column index), copy the value from the input matrix to result[i][j]. Otherwise, leave the cell as 0.
Return the Result Matrix: Output the result matrix, which represents the lower triangle.
Dry-Run
Row 0: i = 0
- matrix[0][0] = 10
- matrix[0][1] = 20
- matrix[0][2] = 30
- matrix[0][3] = 40
Resulting row: [10, 20, 30, 40]
Row 1: i = 1
- matrix[1][0] = 50 (set to 0 because i > j)
- matrix[1][1] = 60
- matrix[1][2] = 70
- matrix[1][3] = 80
Resulting row: [0, 60, 70, 80]
Row 2: i = 2
- matrix[2][0] = 90 (set to 0 because i > j)
- matrix[2][1] = 100 (set to 0 because i > j)
- matrix[2][2] = 110
- matrix[2][3] = 120
Resulting row: [0, 0, 110, 120]
Row 3: i = 3
- matrix[3][0] = 130 (set to 0 because i > j)
- matrix[3][1] = 140 (set to 0 because i > j)
- matrix[3][2] = 150 (set to 0 because i > j)
- matrix[3][3] = 160
Resulting row: [0, 0, 0, 160]
So, the upper triangular matrix is: {{10, 20, 30, 40}, {0, 60, 70, 80}, {0, 0, 110, 120}, {0, 0, 0, 160}}
Lower Triangular Matrix
Row 0: i = 0
- matrix[0][0] = 10 (copy)
- matrix[0][1] = 20 (set to 0 because i < j)
- matrix[0][2] = 30 (set to 0 because i < j)
- matrix[0][3] = 40 (set to 0 because i < j)
Resulting row: [10, 0, 0, 0]
Row 1: i = 1
- matrix[1][0] = 50
- matrix[1][1] = 60
- matrix[1][2] = 70 (set to 0 because i < j)
- matrix[1][3] = 80 (set to 0 because i < j)
Resulting row: [50, 60, 0, 0]
Row 2: i = 2
- matrix[2][0] = 90
- matrix[2][1] = 100
- matrix[2][2] = 110
- matrix[2][3] = 120 (set to 0 because i < j)
Resulting row: [90, 100, 110, 0]
Row 3: i = 3
- matrix[3][0] = 130
- matrix[3][1] = 140
- matrix[3][2] = 150
- matrix[3][3] = 160
Resulting row: [130, 140, 150, 160]
So, the lower triangle matrix is: {{10, 0, 0, 0}, {50, 60, 0, 0}, {90, 100, 110, 0}, {130, 140, 150, 160}}
Code in all Languages
1. C++ Try on Compiler
// C++ code to generate upper and lower triangle matrices
#include <iostream>
#include <vector>
using namespace std;
void printMatrix(const vector<vector<int>>& matrix) {
for (const auto& row : matrix) {
for (int elem : row) {
cout << elem << " ";
}
cout << endl;
}
}
vector<vector<int>> upperTriangle(const vector<vector<int>>& matrix, int n) {
vector<vector<int>> result(n, vector<int>(n, 0));
// Copy elements on or above the main diagonal
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i <= j) {
result[i][j] = matrix[i][j];
}
}
}
return result;
}
vector<vector<int>> lowerTriangle(const vector<vector<int>>& matrix, int n) {
vector<vector<int>> result(n, vector<int>(n, 0));
// Copy elements on or below the main diagonal
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i >= j) {
result[i][j] = matrix[i][j];
}
}
}
return result;
}
int main() {
// Prompt user for matrix size
int n;
cout << "Enter the size of the square matrix: ";
cin >> n;
// Declare and initialize the matrix with user input
vector<vector<int>> matrix(n, vector<int>(n));
cout << "Enter the matrix elements:" << endl;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> matrix[i][j];
}
}
// Generate and print the upper triangle matrix
cout << "Upper Triangle:" << endl;
vector<vector<int>> upper = upperTriangle(matrix, n);
printMatrix(upper);
// Generate and print the lower triangle matrix
cout << "Lower Triangle:" << endl;
vector<vector<int>> lower = lowerTriangle(matrix, n);
printMatrix(lower);
return 0;
}2. Java Try on Compiler
// Java code to generate upper and lower triangle matrices
import java.util.Scanner;
public class MatrixTriangles {
public static void main(String[] args) {
// Create a Scanner for user input
Scanner scanner = new Scanner(System.in);
// Prompt user for matrix size
System.out.print("Enter the size of the square matrix: ");
int n = scanner.nextInt();
// Declare and initialize the matrix with user input
int[][] matrix = new int[n][n];
System.out.println("Enter the matrix elements:");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = scanner.nextInt();
}
}
// Generate and print the upper triangle matrix
System.out.println("Upper Triangle:");
int[][] upperTriangle = upperTriangle(matrix, n);
for (int[] row : upperTriangle) {
for (int elem : row) {
System.out.print(elem + " ");
}
System.out.println();
}
// Generate and print the lower triangle matrix
System.out.println("Lower Triangle:");
int[][] lowerTriangle = lowerTriangle(matrix, n);
for (int[] row : lowerTriangle) {
for (int elem : row) {
System.out.print(elem + " ");
}
System.out.println();
}
scanner.close();
}
// Function to generate the upper triangle of the matrix
public static int[][] upperTriangle(int[][] matrix, int n) {
int[][] result = new int[n][n];
// Copy elements on or above the main diagonal
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i <= j) {
result[i][j] = matrix[i][j];
} else {
result[i][j] = 0; // Set elements below the diagonal to 0
}
}
}
return result;
}
// Function to generate the lower triangle of the matrix
public static int[][] lowerTriangle(int[][] matrix, int n) {
int[][] result = new int[n][n];
// Copy elements on or below the main diagonal
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i >= j) {
result[i][j] = matrix[i][j];
} else {
result[i][j] = 0; // Set elements above the diagonal to 0
}
}
}
return result;
}
}3. Python Try on Compiler
# Python code to generate upper and lower triangle matrices
def upper_triangle(matrix, n):
# Create a new matrix for the result
result = [[0] * n for _ in range(n)]
# Copy elements on or above the main diagonal
for i in range(n):
for j in range(n):
if i <= j:
result[i][j] = matrix[i][j]
return result
def lower_triangle(matrix, n):
# Create a new matrix for the result
result = [[0] * n for _ in range(n)]
# Copy elements on or below the main diagonal
for i in range(n):
for j in range(n):
if i >= j:
result[i][j] = matrix[i][j]
return result
# Main function
if __name__ == "__main__":
# Prompt user for matrix size
n = int(input("Enter the size of the square matrix: "))
# Declare and initialize the matrix with user input
matrix = []
print("Enter the matrix elements:")
for i in range(n):
row = list(map(int, input().split()))
matrix.append(row)
# Generate and print the upper triangle matrix
print("Upper Triangle:")
upper = upper_triangle(matrix, n)
for row in upper:
print(" ".join(map(str, row)))
# Generate and print the lower triangle matrix
print("Lower Triangle:")
lower = lower_triangle(matrix, n)
for row in lower:
print(" ".join(map(str, row)))4. JavaScript Try on Compiler
const readline = require("readline-sync");
function upperTriangle(matrix, n) {
let result = Array.from({ length: n }, () => Array(n).fill(0));
// Copy elements on or above the main diagonal
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (i <= j) {
result[i][j] = matrix[i][j];
}
}
}
return result;
}
function lowerTriangle(matrix, n) {
let result = Array.from({ length: n }, () => Array(n).fill(0));
// Copy elements on or below the main diagonal
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (i >= j) {
result[i][j] = matrix[i][j];
}
}
}
return result;
}
// Main function
(function main() {
// Prompt user for matrix size
const n = parseInt(readline.question("Enter the size of the square matrix: "));
// Declare and initialize the matrix with user input
let matrix = [];
console.log("Enter the matrix elements row by row:");
for (let i = 0; i < n; i++) {
let row = readline.question().split(" ").map(Number);
matrix.push(row);
}
// Generate and print the upper triangle matrix
console.log("Upper Triangle:");
const upper = upperTriangle(matrix, n);
upper.forEach(row => console.log(row.join(" ")));
// Generate and print the lower triangle matrix
console.log("Lower Triangle:");
const lower = lowerTriangle(matrix, n);
lower.forEach(row => console.log(row.join(" ")));
})();
Time Complexity: O(n^2)
Upper Triangle Matrix:
- We are iterating over the matrix of size n x n twice—once for rows and once for columns.
- For each element (i, j) in the matrix, we perform a constant-time operation (either copying the element or setting it to zero).
- The time complexity for generating the upper triangle matrix is proportional to the number of elements in the matrix, which is O(n^2).
Lower Triangle Matrix:
- Similarly, we are iterating over the matrix of size n x n twice (once for rows and once for columns).
- Again, for each element (i, j), we perform a constant-time operation (either copying the element or setting it to zero).
- The time complexity for generating the lower triangle matrix is also O(n^2).
Overall Time Complexity:
Since both the upper triangle and lower triangle matrices require O(n^2) time, the total time complexity of the algorithm is:
Space Complexity: O(n^2)
Auxiliary Space Complexity: Auxiliary space refers to the extra space or temporary space used by the algorithm, excluding the space used for input data.
Upper Triangle Matrix:
- We create a result matrix of size n x n to store the upper triangle.
- This matrix requires O(n^2) space.
Lower Triangle Matrix:
- We create another result matrix of size n x n to store the lower triangle.
- This matrix also requires O(n^2) space.
Since we are creating two separate matrices for the upper and lower triangles, the auxiliary space required is: O(n^2) + O(n^2) = O(n^2).
Total Space Complexity
Total space complexity accounts for both the space used by the input matrix and the auxiliary space required by the algorithm.
Input Matrix: The input matrix is a n x n matrix, so it requires O(n^2) space.
Auxiliary Space: As mentioned earlier, the upper triangle and lower triangle matrices each require O(n^2) space, and they are created separately.
The overall Total Space Complexity: O(n^2) + O(n^2) = O(n^2).
Having explored triangular matrices, let's now shift our focus to another essential matrix traversal – printing diagonals. Diagonals reveal important patterns and symmetries within matrices and are crucial in various algorithms. We'll start by printing diagonal from the top-left to the bottom-right, reinforcing our understanding of matrix indexing and traversal techniques.
Q10. Print the left Diagonal and the right Diagonal
Examples
int[][] matrix = { {10, 20, 30, 40}, {50, 60, 70, 80}, {90, 100, 110, 120}, {130, 140, 150, 160} };
Output: Left diagonal: {10,60,110,160} , Right Diagonal: {40,70,100,130}
Intuition
We call a diagonal left Diagonal which starts from the top-left and goes to the bottom-right.
We call a diagonal Right Diagonal which starts from the top-right and goes to the bottom-left.
The left diagonal is often called as the Main Diagonal and the Right Diagonal is often called the anti-diagonal.
We call left diagonal Left Diagonal that starts at matrix[0][0] → 10 then Moves to matrix[1][1] → 60 then to matrix[2][2] → 110 then ends at matrix[3][3] → 160
We call Right Diagonal (↙) that starts at matrix[0][3] → 40 then moves to matrix[1][2] → 70 then to matrix[2][1] → 100 then ends at matrix[3][0] → 130.
What did we observe ??
We observed that The left diagonal has elements where the row and column are the same → matrix[i][i]
The right diagonal has elements where the column decreases as the row increases → matrix[i][n-1-i]
Square matrix is a matrix where the number of rows is equal to the number of columns.
Approach
Step 1: We will loop through the matrix row by row i.e we will declare an outer loop that runs from i=0 to i=mat.length .
Step 2: For each row i: The Left diagonal is the element when numbe of rows==cols i.e i==j at matrix[i][i] and the right diagonal is the element at matrix[i][n-1-i].
Step 3: Alongside the traversal, we will print the diagonals.
Dry-Run
Left Diagonal (Top-Left to Bottom-Right):
Formula: matrix[i][i]
Row 0: i = 0
- matrix[0][0] = 10 (copy)
- Resulting Diagonal So Far: [10]
Row 1: i = 1
- matrix[1][1] = 60 (copy)
- Resulting Diagonal So Far: [10, 60]
Row 2: i = 2
- matrix[2][2] = 110 (copy)
- Resulting Diagonal So Far: [10, 60, 110]
Row 3: i = 3
- matrix[3][3] = 160 (copy)
- Resulting Diagonal So Far: [10, 60, 110, 160]
Right Diagonal (Top-Right to Bottom-Left):
Formula: matrix[i][n-1-i]
(where n = matrix.length = 4)
Row 0: i = 0
- matrix[0][3] = 40 (copy)
- Resulting Diagonal So Far: [40]
Row 1: i = 1
- matrix[1][2] = 70 (copy)
- Resulting Diagonal So Far: [40, 70]
Row 2: i = 2
- matrix[2][1] = 100 (copy)
- Resulting Diagonal So Far: [40, 70, 100]
Row 3: i = 3
- matrix[3][0] = 130 (copy)
- Resulting Diagonal So Far: [40, 70, 100, 130]
Final Result:
Left Diagonal: [10, 60, 110, 160]
Right Diagonal: [40, 70, 100, 130]
Code in all Languages
1. C++ Try on Compiler
#include <iostream>
using namespace std;
int main() {
// Ask for matrix size
int n;
cout << "Enter matrix size (n x n): ";
cin >> n;
// Initialize matrix
int matrix[n][n];
// Take matrix input
cout << "Enter matrix elements:" << endl;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> matrix[i][j];
}
}
// Print left diagonal
cout << "Left Diagonal: ";
for (int i = 0; i < n; i++) {
cout << matrix[i][i] << " ";
}
cout << endl;
// Print right diagonal
cout << "Right Diagonal: ";
for (int i = 0; i < n; i++) {
cout << matrix[i][n - 1 - i] << " ";
}
cout << endl;
return 0;
}
2. Java Try on Compiler
import java.util.Scanner;
public class MatrixDiagonals {
public static void main(String[] args) {
// Create scanner to take input from user
Scanner sc = new Scanner(System.in);
// Ask for matrix size
System.out.print("Enter matrix size (n x n): ");
int n = sc.nextInt();
// Initialize matrix
int[][] matrix = new int[n][n];
// Take matrix input
System.out.println("Enter matrix elements:");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = sc.nextInt();
}
}
// Print left diagonal
System.out.print("Left Diagonal: ");
for (int i = 0; i < n; i++) {
System.out.print(matrix[i][i] + " ");
}
System.out.println();
// Print right diagonal
System.out.print("Right Diagonal: ");
for (int i = 0; i < n; i++) {
System.out.print(matrix[i][n - 1 - i] + " ");
}
sc.close();
}
}
3. Python Try on Compiler
# Function to print diagonals of a matrix
def print_diagonals(matrix, n):
# Print left diagonal
print("Left Diagonal:", end=" ")
for i in range(n):
print(matrix[i][i], end=" ")
print()
# Print right diagonal
print("Right Diagonal:", end=" ")
for i in range(n):
print(matrix[i][n - 1 - i], end=" ")
print()
# Main method to take input
if __name__ == "__main__":
# Take matrix size from user
n = int(input("Enter matrix size (n x n): "))
# Initialize matrix
matrix = []
# Take matrix input row by row
print("Enter matrix elements:")
for i in range(n):
row = list(map(int, input().split()))
matrix.append(row)
# Call function to print diagonals
print_diagonals(matrix, n)
4. JavaScript Try on Compiler
const readline = require('readline');
// Create readline interface to take input
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
// Initialize matrix and size
let matrix = [];
let n = 0;
let rowCount = 0;
// Ask for matrix size
rl.question('Enter matrix size (n x n): ', (size) => {
n = parseInt(size);
console.log('Enter matrix elements row by row:');
// Read each row of the matrix
rl.on('line', (input) => {
matrix.push(input.split(' ').map(Number));
rowCount++;
// When matrix input is complete
if (rowCount === n) {
// Print left diagonal
let leftDiagonal = [];
for (let i = 0; i < n; i++) {
leftDiagonal.push(matrix[i][i]);
}
console.log('Left Diagonal:', leftDiagonal.join(' '));
// Print right diagonal
let rightDiagonal = [];
for (let i = 0; i < n; i++) {
rightDiagonal.push(matrix[i][n - 1 - i]);
}
console.log('Right Diagonal:', rightDiagonal.join(' '));
rl.close();
}
});
});
Time Complexity: O(n²)
Outer Loop (to take input):
Runs n times (for each row).
Inner Loop (to fill matrix): Runs n times for each row.
Total: O(n^2) for matrix input.
Diagonal Extraction:
Left Diagonal: Single loop running n times → O(n).
Right Diagonal: Another single loop running n times → O(n).
Total for diagonals: O(n) + O(n) = O(2n) ≈ O(n).
Overall Time Complexity: O(n^2) + O(n) ≈ O(n^2)
The dominant term is O(n^2) from matrix input, so the overall time complexity is O(n²).
Space Complexity: O(1)
Auxiliary Space Complexity refers to the extra space required by an algorithm apart from the input space.
- Matrix Storage: No extra data structures are created except for storing the matrix.
- Variables: A few int or float variables for loop counters and size O(1)
- Diagonals: IThey are directly printed so no space is required
Hence, the total auxiliary space complexity is O(1).
Total Space Complexity (Input + Auxiliary Space):
- Matrix Storage: O(n^2) for the matrix (since an n x n matrix is stored)
- Auxiliary Space: O(n) for diagonals or O(1) if directly printed.
The overall Total Space Complexity is: O(n^2) + O(n) ≈ O(n^2)
Now that we have learnt to print the two diagonals that is the diagonal from top left to bottom right and the other from top-right to bottom left. Have you ever wondered that how can we traverse a 2d-array diagonally. Let's learn it in the upcoming articles !!
Q.11 Print all Diagonals from Top-Left to Bottom-Right
Examples
Input
int[][] matrix = { {10, 20, 30, 40}, {50, 60, 70, 80}, {90, 100, 110, 120}, {130, 140, 150, 160} };
Output: {130} {90, 140} {50, 100, 150} {10, 60, 110, 160} {20, 70, 120} {30, 80} {40}
Approach
Here, our objective is to print all possible diagonals from top-left to Bottom-right. We will print all diagonals starting from: The leftmost column. The top row (excluding the first diagonal starting from the top-left corner).
Step 1: Start from the Leftmost Column
First, we focus on diagonals starting from the leftmost column of the matrix. For each row r: We begin at matrix[r][0].
We set two variables: row = r (to track the current row) and col = 0 (since we are starting in the first column).
We then move diagonally through the matrix: While row < n and col < n:
- Add matrix[row][col] to our diagonal collection.
- Increase both row and col to move diagonally down and right.
Once we’ve collected all elements for this diagonal, we print them.
Step 2: Start from the Top Row
Next, we look at diagonals starting from the top row of the matrix. For each column c (starting from the second column): We begin at matrix[0][c].
We set two variables: row = 0 (since we are in the first row). col = c (to track the starting column).
We then move diagonally through the matrix:
- While row < n and col < n: Add matrix[row][col] to our diagonal collection.
- Increase both row and col to move diagonally down and right.
Once we’ve collected all elements for this diagonal, we print them.
Dry-Run
Step 1: Start Diagonals from the Leftmost Column
1st Iteration (r = 0):
- Starting at matrix[0][0] → {10}
- Move diagonally:
- row = 1, col = 1 → matrix[1][1] = 60
- row = 2, col = 2 → matrix[2][2] = 110
- row = 3, col = 3 → matrix[3][3] = 160
- Diagonal: {10, 60, 110, 160}
2nd Iteration (r = 1):
- Starting at matrix[1][0] → {50}
- Move diagonally:
- row = 2, col = 1 → matrix[2][1] = 100
- row = 3, col = 2 → matrix[3][2] = 150
- Diagonal: {50, 100, 150}
3rd Iteration (r = 2):
- Starting at matrix[2][0] → {90}
- Move diagonally:
- row = 3, col = 1 → matrix[3][1] = 140
- Diagonal: {90, 140}
4th Iteration (r = 3):
- Starting at matrix[3][0] → {130}
- No more diagonal elements.
- Diagonal: {130}
Step 2: Start Diagonals from the Top Row
1st Iteration (c = 1):
- Starting at matrix[0][1] → {20}
- Move diagonally:
- row = 1, col = 2 → matrix[1][2] = 70
- row = 2, col = 3 → matrix[2][3] = 120
- Diagonal: {20, 70, 120}
2nd Iteration (c = 2):
- Starting at matrix[0][2] → {30}
- Move diagonally:
- row = 1, col = 3 → matrix[1][3] = 80
- Diagonal: {30, 80}
3rd Iteration (c = 3):
- Starting at matrix[0][3] → {40}
- No more diagonal elements.
- Diagonal: {40}
Final Output:
Here are all the diagonals printed in order:
{130}
{90, 140}
{50, 100, 150}
{10, 60, 110, 160}
{20, 70, 120}
{30, 80}
{40}
Code in all Languages
1. C++ Try on Compiler
#include <iostream>
#include <vector>
using namespace std;
// Function to print all diagonals of a matrix
void printAllDiagonals(vector<vector<int>>& matrix, int n) {
// Print diagonals starting from the leftmost column
for (int r = 0; r < n; r++) {
// Start a new diagonal
int row = r, col = 0;
vector<int> diagonal;
// Collect diagonal elements
while (row < n && col < n) {
diagonal.push_back(matrix[row][col]);
row++;
col++;
}
// Print the collected diagonal
for (int elem : diagonal) cout << elem << " ";
cout << endl;
}
// Print diagonals starting from the top row
for (int c = 1; c < n; c++) {
// Start a new diagonal
int row = 0, col = c;
vector<int> diagonal;
// Collect diagonal elements
while (row < n && col < n) {
diagonal.push_back(matrix[row][col]);
row++;
col++;
}
// Print the collected diagonal
for (int elem : diagonal) cout << elem << " ";
cout << endl;
}
}
// Main function
int main() {
// Hardcoded input
vector<vector<int>> hardcodedMatrix = {{10, 20, 30, 40},
{50, 60, 70, 80},
{90, 100, 110, 120},
{130, 140, 150, 160}};
int size = 4;
cout << "Diagonals for hardcoded matrix:" << endl;
printAllDiagonals(hardcodedMatrix, size);
// Scanned input
cout << "\nEnter the size of the square matrix: ";
cin >> size;
vector<vector<int>> scannedMatrix(size, vector<int>(size));
cout << "Enter the elements of the matrix:" << endl;
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
cin >> scannedMatrix[i][j];
}
}
cout << "\nDiagonals for scanned matrix:" << endl;
printAllDiagonals(scannedMatrix, size);
return 0;
}
2. Java Try on Compiler
import java.util.Scanner;
public class DiagonalPrinter {
// Function to print all diagonals of a matrix
public static void printAllDiagonals(int[][] matrix, int n) {
// Print diagonals starting from the leftmost column
for (int r = 0; r < n; r++) {
// Start a new diagonal
int row = r, col = 0;
StringBuilder diagonal = new StringBuilder();
// Collect diagonal elements
while (row < n && col < n) {
diagonal.append(matrix[row][col]).append(" ");
row++;
col++;
}
// Print the collected diagonal
System.out.println(diagonal.toString());
}
// Print diagonals starting from the top row
for (int c = 1; c < n; c++) {
// Start a new diagonal
int row = 0, col = c;
StringBuilder diagonal = new StringBuilder();
// Collect diagonal elements
while (row < n && col < n) {
diagonal.append(matrix[row][col]).append(" ");
row++;
col++;
}
// Print the collected diagonal
System.out.println(diagonal.toString());
}
}
public static void main(String[] args) {
// Hardcoded input
int[][] hardcodedMatrix = {
{10, 20, 30, 40},
{50, 60, 70, 80},
{90, 100, 110, 120},
{130, 140, 150, 160}
};
int size = 4;
System.out.println("Diagonals for hardcoded matrix:");
printAllDiagonals(hardcodedMatrix, size);
// Scanned input
Scanner scanner = new Scanner(System.in);
System.out.print("\nEnter the size of the square matrix: ");
size = scanner.nextInt();
int[][] scannedMatrix = new int[size][size];
System.out.println("Enter the elements of the matrix:");
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
scannedMatrix[i][j] = scanner.nextInt();
}
}
System.out.println("\nDiagonals for scanned matrix:");
printAllDiagonals(scannedMatrix, size);
scanner.close();
}
}
3. Python Try on Compiler
# Function to print all diagonals of a matrix
def print_all_diagonals(matrix, n):
# Print diagonals starting from the leftmost column
for r in range(n):
# Start a new diagonal
row, col = r, 0
diagonal = []
# Collect diagonal elements
while row < n and col < n:
diagonal.append(matrix[row][col])
row += 1
col += 1
# Print the collected diagonal
print(diagonal)
# Print diagonals starting from the top row
for c in range(1, n):
# Start a new diagonal
row, col = 0, c
diagonal = []
# Collect diagonal elements
while row < n and col < n:
diagonal.append(matrix[row][col])
row += 1
col += 1
# Print the collected diagonal
print(diagonal)
# Main function
def main():
# Hardcoded input
hardcoded_matrix = [
[10, 20, 30, 40],
[50, 60, 70, 80],
[90, 100, 110, 120],
[130, 140, 150, 160]
]
size = 4
print("Diagonals for hardcoded matrix:")
print_all_diagonals(hardcoded_matrix, size)
# Scanned input
size = int(input("\nEnter the size of the square matrix: "))
print("Enter the elements of the matrix:")
scanned_matrix = []
for _ in range(size):
scanned_matrix.append(list(map(int, input().split())))
print("\nDiagonals for scanned matrix:")
print_all_diagonals(scanned_matrix, size)
# Run the main function
main()
4. JavaScript Try on Compiler
const readline = require("readline-sync");
// Function to print all diagonals of a matrix
function printAllDiagonals(matrix, n) {
// Print diagonals starting from the leftmost column
for (let r = 0; r < n; r++) {
let row = r, col = 0;
let diagonal = [];
while (row < n && col < n) {
diagonal.push(matrix[row][col]);
row++;
col++;
}
console.log(diagonal);
}
// Print diagonals starting from the top row
for (let c = 1; c < n; c++) {
let row = 0, col = c;
let diagonal = [];
while (row < n && col < n) {
diagonal.push(matrix[row][col]);
row++;
col++;
}
console.log(diagonal);
}
}
// Main function
function main() {
// Hardcoded input
const hardcodedMatrix = [
[10, 20, 30, 40],
[50, 60, 70, 80],
[90, 100, 110, 120],
[130, 140, 150, 160]
];
console.log("Diagonals for hardcoded matrix:");
printAllDiagonals(hardcodedMatrix, 4);
// Scanned input
const size = parseInt(readline.question("\nEnter the size of the square matrix: "));
const scannedMatrix = [];
console.log("Enter the elements of the matrix row by row:");
for (let i = 0; i < size; i++) {
scannedMatrix.push(readline.question().split(" ").map(Number));
}
console.log("\nDiagonals for scanned matrix:");
printAllDiagonals(scannedMatrix, size);
}
// Run the main function
main();
Time Complexity: O(n^2)
The printAllDiagonals function prints all diagonals of a square matrix of size n×n
First loop (for diagonals starting from the leftmost column): Therefore, for each diagonal, the number of elements collected is at most n, and since the loop runs n times, the total time spent here is O(n^2).
This loop runs n times (once for each row in the first column).
For each iteration, it collects elements from the diagonal, which can have at most n elements. In the worst case, when starting from the topmost row or leftmost column, we can collect all n elements of the diagonal.
Second loop (for diagonals starting from the top row):Again, the number of elements collected is at most n, and since the loop runs n−1times, the total time spent here is O(n^2).
- This loop runs n−1 times (from column 1 to column n−1).
- For each iteration, it collects elements from a diagonal, which can also have at most n elements.
Total time complexity: Combining both loops, we get O(n^2)+O(n^2)=O(n^2)
Space Complexity: O(n^2)
Auxiliary Space Complexity
Auxiliary space refers to the extra space used by the algorithm, excluding the input space.
For each diagonal:
- A new vector is created to store the diagonal elements. In the worst case, this vector will store nnn elements.
- The space complexity for each diagonal is O(n), and this vector is used temporarily during each loop iteration.
Since the maximum number of diagonals is 2n−1 (one for each row and one for each column), the auxiliary space complexity for storing the diagonals is O(n) for each diagonal, and since only one diagonal is stored at a time, the total auxiliary space complexity is O(n).
Auxiliary space complexity: O(n).
Total Space Complexity
Total space complexity includes both the space used by the input matrix and the auxiliary space used during computation.
Input matrix: The matrix is of size n×n, which requires O(n^2) space.
Auxiliary space: As explained earlier, the auxiliary space used by the algorithm is O(n).
Total space complexity: O(n^2) (due to the matrix storage).