# Problem

Consider a staircase of size `n = 4`:

``````   #
##
###
####
``````

Write a program that prints a staircase of size `n`.

# Solution

For every n size there are n elements to print which makes the overall complexity O(N^2).

## Naive solution

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="")
``````