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:
C++
// C++ Implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to create required matrix
void findMaximumDistinct(int n, vector<vector<int> >& v)
{
// l is left pointer and r is
// right pointer
int l = 1, r = n * n, t = 0;
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;
}
}
// Revrse the recent row for
// odd row
if (i % 2)
reverse(v[i].begin(), v[i].end());
}
}
// Driver Code
int 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;
}
return 0;
}
Time Complexity: O(n2)
Auxiliary Space: O(n2)