Given an integer N, the task is to fill a matrix M of size NxN, starting from the main diagonal and then alternating between the lower and upper triangular diagonals, in an increasing fashion such that each number from 1 to N2 appears only once.
Examples:
Input: N = 4
Output:
1 8 13 16
5 2 9 14
11 6 3 10
15 12 7 4
Explanation:
First filling the main diagonal:
1
2
3
4
Next, fill the lower diagonal below the main diagonal
1
5 2
6 3
7 4
Next, fill the upper diagonal above the main diagonal
1 8
5 2 9
6 3 10
7 4
Following the same pattern and altering between
upper and lower triangular matrix,
we get the final matrix as
1 8 13 16
5 2 9 14
11 6 3 10
15 12 7 4
Input: N = 3
Output:
1 6 9
4 2 7
8 5 3
Approach: Follow the below steps to solve the problem:
- Initialize a variable cur to 1. This will keep track of the current number
- Initialize a variable d to 1. This keeps track of the diagonals.
- Iterate from 1 to (N+N-1) using d. This is the number of diagonals.
- If d is even, initialize two variables r and c to d/2 and 0 respectively.
- Otherwise, initialize the two variables r and c to 0 and d/2 respectively.
- Iterate till r and c both are less than N
- Update the matrix M as M[r]=cur.
- Increment cur, r, and c.
- After exiting the inner loop, increment d.
- Finally, display the matrix M.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Function to fill the matrix diagonally alternating// between upper and lower diagonalsvoid fillMatrix(int N){ // variables to keep track of // diagonals and current number int d = 1, cur = 1; // Matrix int M[N][N]; // Iterating over all diagonals while (d <= 2 * N - 1) { int r, c; // For lower triangle if (d % 2 == 0) r = d / 2, c = 0; // For upper triangle else r = 0, c = d / 2; // Placing the current number // in appropriate position while (r < N && c < N) { M[r] = cur; cur++; r++; c++; } d++; } // Displaying the matrix for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cout << M[i][j] << " "; } cout << endl; }}// Driver codeint main(){ // Input int N = 4; // Function calling fillMatrix(N); return 0;} |
Java
// Java implementation of the above approachimport java.io.*;class GFG { static void fillmatrix(int m[][], int n) { int r, c; int num = 1, d = 1; // 2*n-1 is no of diagonals while (d <= 2 * n - 1) { // If d%2==0 switch to // lower triangular diagonal if (d % 2 == 0) { r = d / 2; c = 0; while (r < n && c < n) { m[r] = num++; r++; c++; } } // If d%2==1 switch to // upper triangular diagonal else { r = 0; c = d / 2; while (c < n && r < n) { m[r] = num++; r++; c++; } } d++; } } // Utility function to display the matrix static void display(int m[][], int n) { int i, j; for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { System.out.printf(m[i][j] + " "); } System.out.println(); } } public static void main(String[] args) { int n = 4; int[][] m = new int[4][4]; fillmatrix(m, n); display(m, n); }} |
Python3
# Python3 implementation of the above approach# Function to fill the matrix diagonally # alternating between upper and lower diagonalsdef fillMatrix(N): # Variables to keep track of # diagonals and current number d = 1 cur = 1 # Matrix M = [[0 for i in range(N)] for i in range(N)] # Iterating over all diagonals while (d <= 2 * N - 1): r, c = 0, 0 # For lower triangle if (d % 2 == 0): r = d // 2 c = 0 # For upper triangle else: r = 0 c = d // 2 # Placing the current number # in appropriate position while (r < N and c < N): M[r] = cur cur += 1 r += 1 c += 1 d += 1 # Displaying the matrix for i in M: print(*i)# Driver codeif __name__ == '__main__': # Input N = 4 # Function calling fillMatrix(N)# This code is contributed by mohit kumar 29 |
C#
// C# implementation of the above approachusing System.IO;using System;class GFG{ static void fillmatrix(int[, ] m, int n){ int r, c; int num = 1, d = 1; // 2*n-1 is no of diagonals while (d <= 2 * n - 1) { // If d%2==0 switch to // lower triangular diagonal if (d % 2 == 0) { r = d / 2; c = 0; while (r < n && c < n) { m[r, c] = num++; r++; c++; } } // If d%2==1 switch to // upper triangular diagonal else { r = 0; c = d / 2; while (c < n && r < n) { m[r, c] = num++; r++; c++; } } d++; }}// Utility function to display the matrixstatic void display(int[,] m, int n){ int i, j; for(i = 0; i < n; i++) { for(j = 0; j < n; j++) { Console.Write(m[i, j] + " "); } Console.WriteLine(); }}// Driver codestatic void Main(){ int n = 4; int[,] m = new int[4, 4]; fillmatrix(m, n); display(m, n);}}// This code is contributed by abhinavjain194 |
Javascript
<script> // Javascript implementation of the above approach function fillmatrix(m, n) { let r, c; let num = 1, d = 1; // 2*n-1 is no of diagonals while (d <= 2 * n - 1) { // If d%2==0 switch to // lower triangular diagonal if (d % 2 == 0) { r = parseInt(d / 2, 10); c = 0; while (r < n && c < n) { m[r] = num++; r++; c++; } } // If d%2==1 switch to // upper triangular diagonal else { r = 0; c = parseInt(d / 2, 10); while (c < n && r < n) { m[r] = num++; r++; c++; } } d++; } } // Utility function to display the matrix function display(m, n) { let i, j; for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { document.write(m[i][j] + " "); } document.write("</br>"); } } let n = 4; let m = new Array(4); for(let i = 0; i < m.length; i++) { m[i] = new Array(m.length); for(let j = 0; j < m.length; j++) { m[i][j] = 0; } } fillmatrix(m, n); display(m, n); // This code is contributed by divyeshrabadiya07.</script> |
Output
1 8 13 16 5 2 9 14 11 6 3 10 15 12 7 4
Time Complexity: O(N2)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
