Given an integer N. Return a N x N matrix such that each element (Coordinates(i, j))is having maximum absolute difference possible with the adjacent element (i.e., (i + 1, j), (i – 1, j), (i, j + 1), (i, j – 1)). Also, It should contain distinct elements ranging from 1 to N2.
Examples:
Input: N = 2
Output: 4 1
2 3Input: N = 3
Output: 1 3 4
9 2 7
5 8 6
Approach: The problem can be solved based on the following idea:
The distinct numbers don’t exceed N2 – 1, because the minimum difference between two elements is at least 1, and the maximum difference does not exceed N2 – 1 (the difference between the maximum element N2 and the minimum element 1).
Follow the below steps to implement the idea:
- Initialize an empty 2D matrix v of size N*N and bool check = true.
- Start adding the elements from 1 to N2 i.e., l and r pointers respectively.
- If check = true, start adding the elements from the r pointer in decreasing order until the row is filled and change the check = false.
- If check = false, start adding the elements from the l pointer in increasing order until the row is filled and change the check = true.
- Repeat this until all matrix is filled.
Below is the implementation of the above approach:
Java
// Java code for the above approachimport java.util.Arrays;import java.util.Scanner;public class Main { static void findMaximumDistinct(int n, int[][] v) { // l is left pointer and r is // right pointer int l = 1, r = n * n; boolean check = true; // Creating matrix by nested for loop for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { // Inserting one element from // starting and one element // from ending (1 to n^2-1) if (check == false) { // Inserting the value // from starting v[i][j] = l++; check = true; } else { // Inserting the value // from ending v[i][j] = r--; // Checking the bool for // alternatingly insertion check = false; } } // Reverse the recent row for // odd row if (i % 2 == 1) { for (int j = 0; j < n / 2; j++) { int temp = v[i][j]; v[i][j] = v[i][n - j - 1]; v[i][n - j - 1] = temp; } } } } // Driver Code public static void main(String[] args) { int n = 3; int[][] v = new int[n][n]; // Function call findMaximumDistinct(n, v); // Displaying the matrix for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { System.out.print(v[i][j] + " "); } System.out.println(); } }}// This code is contributed by lokeshpotta20. |
Python3
# Python code for the above approachdef findMaximumDistinct(n, v): # l is left pointer and r is # right pointer l = 1 r = n * n check = True # Creating matrix by nested for loop for i in range(n): for j in range(n): # Inserting one element from # starting and one element # from ending (1 to n^2-1) if check == False: # Inserting the value # from starting v[i][j] = l l += 1 check = True else: # Inserting the value # from ending v[i][j] = r r -= 1 # Checking the bool for # alternatingly insertion check = False # Reverse the recent row for # odd row if i % 2 == 1: for j in range(n // 2): temp = v[i][j] v[i][j] = v[i][n - j - 1] v[i][n - j - 1] = temp# Driver coden = 3v = [[0 for i in range(n)] for j in range(n)]# Function callfindMaximumDistinct(n, v)# Displaying the matrixfor i in range(n): for j in range(n): print(v[i][j], end = " ") print()# This code is contributed by lokesh. |
C#
// C# Implementation of the above approachusing System;using System.Linq;// Function to create required matrixclass Program { public static void findMaximumDistinct(int n, int[][] v) { // l is left pointer and r is // right pointer int l = 1, r = n * n; bool check = true; // Creating matrix by nested for loop for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { // Inserting one element from // starting and one element // from ending (1 to n^2-1) if (check == false) { // Inserting the value // from starting v[i][j] = l; l++; check = true; } else { // Inserting the value // from ending v[i][j] = r; r--; // Checking the bool for // alternatingly insertion check = false; } } // Reverse the recent row for odd row if (i % 2 != 0) { v[i] = v[i].Reverse().ToArray(); } } } // Drive Code public static void Main() { int n = 3; int[][] v = new int[n][]; for (int i = 0; i < n; i++) { v[i] = new int[n]; } // Function Call findMaximumDistinct(n, v); // Displaying the matrix for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { Console.Write(v[i][j] + " "); } Console.WriteLine(); } }}// This Code is Contributed by nikhilsainiofficial546 |
Javascript
// JavaScript code for the above approachfunction findMaximumDistinct(n, v){ // l is left pointer and r is right pointer let l = 1, r = n * n; let check = true; // Creating matrix by nested for loop for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { // Inserting one element from starting // and one element from ending (1 to n^2-1) if (check === false) { // Inserting the value from starting v[i][j] = l++; check = true; } else { // Inserting the value from ending v[i][j] = r--; // Checking the bool for alternatingly insertion check = false; } } // Reverse the recent row for odd row if (i % 2 === 1) { for (let j = 0; j < n / 2; j++) { let temp = v[i][j]; v[i][j] = v[i][n - j - 1]; v[i][n - j - 1] = temp; } } }}// Driver Codelet n = 3;let v = new Array(n).fill(0).map(() => new Array(n));// Function callfindMaximumDistinct(n, v);// Displaying the matrixfor (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { console.log(v[i][j] + " "); } console.log("<br>");}// This code is contributed by lokeshmvs21. |
C++14
// C++ code for the above approach#include<bits/stdc++.h>using namespace std;void findMaximumDistinct(int n, vector<vector<int>>& v){ // l is left pointer and r is // right pointer int l = 1, r = n * n; bool check = true; // Creating matrix by nested for loop for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { // Inserting one element from // starting and one element // from ending (1 to n^2-1) if (check == false) { // Inserting the value // from starting v[i][j] = l++; check = true; } else { // Inserting the value // from ending v[i][j] = r--; // Checking the bool for // alternatingly insertion check = false; } } // Reverse the recent row for // odd row if (i % 2 == 1) { for (int j = 0; j < n / 2; j++) { int temp = v[i][j]; v[i][j] = v[i][n - j - 1]; v[i][n - j - 1] = temp; } } }}// Driver Codeint main(){ int n = 3; vector<vector<int>> v(n, vector<int>(n)); // Function call findMaximumDistinct(n, v); // Displaying the matrix for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cout<<v[i][j] << " "; } cout<<endl; }} |
Output
9 1 8 3 7 2 6 4 5
Time Complexity: O(n2)
Auxiliary Space: O(n2)
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!
Share your thoughts in the comments
