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