Arrow Pattern

Easy
0/40
Average time to solve is 10m
profile
Contributed by
17 upvotes

Problem statement

You are given an integer 'N'. Your task is to give a pattern with the following description:

1. The pattern will consist of 2 * ‘N’ - 1 lines.
2. The pattern will consist of ‘ ’ (space) and ‘*’ (asterisk) characters only.
3. The pattern will be an arrow pattern.
4. For a value 'i', the arrow pattern starts with 'i' ‘ ’ (space) characters and then has 'i' ‘*’ (asterisk) characters.
5. The value of 'i' starts from 1, increases till ‘N’ and then decreases till 1.


Please note that each line will consist of the same number of ‘ ’ and ‘*’ characters.


For a better understanding of the arrow, pattern refers to example and sample input-output.


For example:

If ‘N’ is 5 then the pattern will be (there is a space before the first asterisk):

 *
  **
   ***
    ****
     *****
    ****
   ***
  **
 *
Detailed explanation ( Input/output format, Notes, Images )

Input Format

The first line of input contains an integer 'T' representing the number of test cases.

Then each test case contains a single integer ‘N’ denoting the size of the pattern.


Output Format:

For each test case, print the 'N' strings denoting the pattern.

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


Constraints:

1 <= 'T' <= 10
1 <= 'N' <= 1000

Where ‘T’ is the number of test cases, ‘N’  is the size of the pattern.


Note:

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

Sample Input 1:

2
5
3


Sample Output 1:

 *
  **
   ***
    ****
     *****
    ****
   ***
  **
 *
 *
  **
   ***
  **
 *


Explanation of Sample Input 1:

Test Case 1:
Given ‘N’ = 5
We will print the pattern as the description of the arrow pattern.

Test Case 2:
Given ‘N’ = 3
We started 'i' with 1, increased it to 3, and then again decreased it to 1.


Sample Input 2:

2
1
2


Sample Output 2:

 *
 *
  **
 *


Explanation of Sample Input 2:

Test Case 1:
Given ‘N' = 1
There will be only 1 line that will contain a ‘ ’ and an ‘*’.

Test Case 2:
Given ‘N’ = 2
The first line will contain 1 ‘ ’ and 1 ‘*’, the second line will contain 2 ‘ ’ and 2 ‘*’ and the third line will contain 1 ‘ ’ and 1 ‘*’.
Hint

Can we maintain 2 strings for ‘ ‘ and ‘*’ characters? and then in each step either we need to increase the length by 1 or decrease the length by 1.

Approaches (1)
Pattern printing

The idea is here to maintain 2 strings 1 for ‘ ‘ characters and 1 for ‘*’ characters, now in each step till ‘N’ we will append 1 ‘ ‘ character in 1st string and 1 ‘*’  character in 2nd string. After ‘N’ in each step, we will remove 1 ‘ ‘ character from the 1st string and 1 ‘*’  character from the 2nd string. At each step, we will append concatenation of both strings to our pattern.

 

Algorithm:

 

  • Create 2 strings name ‘str1’ and ‘str2’, ‘str1’ is for ‘ ‘ characters and ‘str2’ is for ‘*’ characters. Also, create an array of strings for storing the pattern say ‘answer’.
  • Run a loop from ‘i’ = 1 to ‘i’ = 2 * ‘N’ - 1
  • If ‘i’ <= ‘N’ append ‘ ‘ to ‘str1’ and ‘*’ to ‘str2’ now append ‘str1’ + ‘str2’ to ‘answer’.
  • Else, remove 1 character from ‘str1’ and 1 character from ‘str2’ and append ‘str1’ + ‘str2’ to ‘answer’.
  • Return the ‘answer’ array that contains the pattern.
Time Complexity

O(N ^ 2), where N is the size of the pattern.

 

We are doing 2’N’-1 iterations and in each iteration, we will be concatenating 2 strings so it is an O(N) time operation and then we will append a string of length ‘N’ in the array so it is also an O(N) time operation. So in each iteration, we are taking O(N) time so the overall time complexity will be  O(N ^ 2).

Space Complexity

O(N ^ 2), where N is the size of the pattern.

 

As we will be storing the result in an array of strings that contains 2‘N’ - 1 strings of size ‘N’ so overall space complexity will be O(N ^ 2).

Code Solution
(100% EXP penalty)
Arrow Pattern
Full screen
Console