Rectangular Numbers

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
14 upvotes
Asked in companies
QualcommAdobeHSBC

Problem statement

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
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
2
2
1
Sample Output 1:
2 2 2
2 1 2
2 2 2
1
Explanation Of Sample Input 1:
Test case 1:

For the first test case of sample output 1, as the number is 2, so the outermost rectangle is of number 2. The moment we get inside the rectangle, we reduce the number by 1 and make another rectangle.

Test case 2:   

For the second test case of sample output 1, as the number is 1, so the outermost rectangle is of number 1.
Sample Input 2:
1
4
Sample Output 2:
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
Explanation Of Sample Input 2:
Test case 1:

For the first test case of sample output 2, as the number is 4, so the outermost rectangle is of number 24. The moment we get inside the rectangle, we reduce the number by 1 and make another rectangle. This process goes on till we reach 1.
Hint

Make rectangular boundaries and move inside the boundaries.

Approaches (1)
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.
Time Complexity

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).

Space Complexity

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).
 

Code Solution
(100% EXP penalty)
Rectangular Numbers
Full screen
Console