Dustin's Blog 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="")