Repeat Triangle

Easy
0/40
Average time to solve is 15m
profile
Contributed by
3 upvotes
Asked in companies
WalmartSimple Intelligence

Problem statement

Ninja wants to build a triangle pattern for English alphabets for a given integer input.

Example, for ‘N’ = 4

Pattern:

ABCDDCBA
 ABCCBA
  ABBA
   AA
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’, denoting the number of alphabets.

Output Format:

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

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

Note:

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

Constraints:

1 <= T <= 5
1 <= N <= 26

Time Limit = 1 sec
Sample Input 1:
2
4
1
Sample Output 1:
ABCDDCBA
 ABCCBA
  ABBA
   AA
   AA
Explanation of Sample Input 1:
Test case 1:

In the first test case of sample input 1, we need to print a triangle-like pattern wherein each line, the number of alphabets will be decreasing from both sides till the last row.
Sample Input 2:
1
2
Sample Output 2:
BAAB
 AA
Explanation of Sample Input 2:
Test case 1:

In this test case, as ‘N’ is equal to 2, we consider the first two alphabets and then make the triangle-like pattern.
Hint

Observe that the left and right triangles look identical.

Approaches (1)
String Manupilation

Here we can first precompute two strings of all 26 alphabets. In our first-string ‘front’, we will store the characters from left to right, and in the second string ‘back’, we will store from right to left. Once our precomputed strings are ready, now we need to make the triangle using these strings only. For each row, we will add the calculated amount of space in a local string, and then using the substring function, we can extract the number of alphabets needed from both ‘front’ and ‘back’. Now, these local strings will be stored in an array of strings. Once we get the desired number of strings for the ‘N’ row, we can return our array of strings.

 

Algorithm:

 

  • Declare an array ‘arr’ of string type and resize it with ‘n’
  • Declare a string ‘front’ and ‘back’ where we shall precompute and store the alphabets in ascending and descending order respectively.
  • Run a loop from ‘i’ = 0 to ‘n’
    • Declare a local string for each row
    • Run a loop from ‘j’ = 0 to ‘i’
      • Add space to our local string to make the triangle-like pattern
    • Append substring of front and back to this local string
    • Push the local string to the array ‘arr’
  • Return the array ‘arr’.
Time Complexity

O(N ^ 2), where ‘N’ is the given input.

 

We are traversing ‘N’ rows in each test case. In each row, we are adding space in increasing order. So for each row, we are doing (1 + 2 + 3 + … + N - 1 + N) = (N * (N + 1)) / 2 computations. Therefore, our time complexity is O(N ^ 2).

Space Complexity

O(N^2),  where N is the given input.

 

As we are returning an array of size ‘N’ containing ‘N string”’ each of size beginning from ‘1’ to ‘N'.

Code Solution
(100% EXP penalty)
Repeat Triangle
Full screen
Console