Rectangular Numbers
Ninja has a number ‘N’. He wants to print the pattern in such a way that the outer rectangle is of the number ‘N’ and the number goes on decreasing as we move inside the rectangles.

For example, if ‘N’ = 4, then pattern will be:

4 4 4 4 4 4 4 4 3 3 3 3 3 4 4 3 2 2 2 3 4 4 3 2 1 2 3 4 4 3 2 2 2 3 4 4 3 3 3 3 3 4 4 4 4 4 4 4 4

Input Format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run. The first line of each test case contains one integer ‘N’ for the number of rectangles.

Output Format:

For each case, return a 2-d list/array of integers denoting the pattern. The output of each test case will be printed in a separate line.

Note:

You do not need to input or print anything, and it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Rectangular Numbers

Ninja has a number ‘N’. He wants to print the pattern in such a way that the outer rectangle is of the number ‘N’ and the number goes on decreasing as we move inside the rectangles.

For example, if ‘N’ = 4, then pattern will be:

4 4 4 4 4 4 4 
4 3 3 3 3 3 4 
4 3 2 2 2 3 4 
4 3 2 1 2 3 4 
4 3 2 2 2 3 4 
4 3 3 3 3 3 4 
4 4 4 4 4 4 4

Input Format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run.

The first line of each test case contains one integer ‘N’ for the number of rectangles.

Output Format:

For each case, return a 2-d list/array of integers denoting the pattern.

The output of each test case will be printed in a separate line.

Note:

You do not need to input or print anything, and it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 100

Time limit: 1 sec.

Accepted Answer

The number of rows or columns to be printed for given n will be 2*n – 1.
We will print the matrix in two parts. First, print the upper half from rows from 0 to floor((2*n – 1)/2) and then second half from floor((2*n – 1)/2) + 1 to 2*n – 2.
Now for each row, print it in three parts. First part is decreasing sequence which will start from n and decrease by 1 in each iteration. The number of iterations will be equal to row number, the second part is a constant sequence where constant is n – i and it will be print 2*n – 1 – 2 * row number, and the third part is increasing sequence which is nothing but opposite of the first sequence.
For lower half, observe, it is a mirror image of upper half (excluding middle row). So, simply run a loop of the upper half from (2*n – 1)/2 to 0.

Accepted Answer

Pattern Observation

As we need to move rectangles for each number from N to 1, we start with a loop where N is decreasing after iteration of the loop. Inside the loop, we basically only need to choose the location of the border elements. So we can run a nested loop as we travel in the case of a 2D array and whenever we stand at the border indexes, we need to put the number in that index.

Algorithm:

Declare and Initialize size as 2 * ‘n’ - 1.
Declare and Initialize front as ‘0’ and back as ‘size’ - 1
Declare a 2D-array ‘arr’ with row and column as ‘size’
Run a while loop from ‘n’ to 0.
- Run a for loop ‘i’ = ‘front’ to ‘back’
  - Run a for loop ‘i’ = ‘front’ to ‘back’
    - If ‘i’ or ‘j’ is either equal to ‘front’ or ‘back’.
      - Then arr[i][j] = ‘n’
- Increase ‘front’ by 1
- Decrease ‘back’ by 1
- Decrease ‘n’ by 1
Return 2D array.

Space Complexity: O(n^2)Explanation:

O(N^2), where N is the number of rows and columns of the array.

We only need a 2D array to make the pattern, so space complexity is O(N^2).

Time Complexity: O(n^3)Explanation:

O(N^3) where N is the number of rows and columns of the array.

As we iterate through all N numbers, for each number we make a rectangular frame using two nested for loops. As the nested for loops have (2*N-1)*(2*N-1) iteration, so our time complexity comes down to O(N^3).

Java (SE 1.8)


import java.util.ArrayList;

public class Solution {
	public static int[][] rectangularNumbers(int n){
		
		// Declare and initialize size as 2*n-1
	    int size = 2 * n -1 ;

	    int front = 0 ;
	    int back = size -1 ;


	    // Declare a 2D array
	    int[][] arr=new int[size][size];

	    while( n != 0)
	    {
	        for (int i = front; i <= back; i++)
	        {
	            for (int j = front; j <= back; j++)
	            {

	                // If i or j is either equal to front or back
	                if( i == front || i == back || j == front || j == back)
	                {
	                    arr[i][j] = n;
	                }
	            }
	        }
	        front++;
	        back--;
	        n--;
	    }
	    
	    // Return the array arr
	    return arr;
	}
}

C++ (g++ 5.4)

/*

    Time Complexity: O(N ^ 3)

    Space Complexity: O(N ^ 2)



    Where 'N' is the total number of rows of the array.

*/



vector> rectangularNumbers(int n)

{

    // Declare and initialize size as 2 * n-1

    int size = 2 * n - 1;



    int front = 0;

    int back = size - 1;





    // Declare a 2D array arr

    vector> arr;



    // Resize the array in terms of rows

    arr.resize(size);



    for (int i = 0; i < size; ++i)

    {

        // Resize each array in terms of columns

        arr[i].resize(size);

    }





    while( n != 0)

    {

        for (int i = front; i <= back; i++)

        {

            for (int j = front; j <= back; j++)

            {



                // If 'i' or 'j' is either equal to 'front' or 'back'

                if( i == front || i == back || j == front || j == back)

                {

                    arr[i][j] = n;

                }

            }

        }



        front++;

        back--;

        n--;

    }

    

    // Return the array arr

    return arr;

}

Python (3.5)

'''

    Time Complexity: O(N ^ 3)

    Space Complexity: O(N ^ 2)



    Where N is the total number of rows of the array.

'''



def rectangularNumbers(n):



	# Declare and initialize size as 2 * n - 1.

	

	size = 2 * n -1

	front = 0

	

	back = size - 1 

	

	# Declare an array to store pattern.

	arr = []

	

	# Resize the arr in terms of rows

	arr = [None for i in range(size)]



	for i in range(size):

		

		# Resize each row in terms of columns size.

		arr[i] = [ None for i in range(size)]

		

	while( n != 0):



		for i in range(front, back + 1):



			for j in range(front, back + 1):

				

				# If 'i' or 'j' is either equal to 'front' or 'back'

				if( i == front or i == back or j == front or j == back):

					arr[i][j] = n

		

		front += 1

		back -= 1

		n -= 1

		

	# Return the array arr 

	return arr