Consider a staircase of size
n = 4:
# ## ### ####
Write a program that prints a staircase of size
For every n size there are n elements to print which makes the overall complexity O(N^2).
In the simple case string concatenation is used to build a row and then the row is printed.
Time = O(N^2) Space = O(N)
Staircase naive in Python 3
def staircase(n): for i in range(1, n + 1): spaces = " " * (n - i) stairs = "#" * i print(spaces + stairs)
Space optimized solution
Since N inputs must be evaluated N times the time complexity must be N^2.
Storage can be reduced to constant time by comparing whether the column is within a boundary value.
The model is a square matrix where every value past the diagonal is filled.
0001 0011 0111 1111
This is determined by
boundary = size - (row + 1).
Time = O(N^2) Space = O(1)
Staircase optimized in Python 3
def staircase(n): for x in range(n**2): i, j = divmod(x, n) if j >= (n - (i + 1)): print("#", end="") if j == (n - 1): print() else: print(" ", end="")