Find the Nearest Smaller Element on Left Side in an Array – Understand the Challenge to Solve it Efficiently

The Nearest Smaller Element problem explained:

Given an array (that is a list) of integers, for each element find all the nearest element smaller on the left side of it.

The naive solution has time complexity O(n^2). Can you solve it in O(n)? Well, you need to have a Stack to do that.

The naive solution is for each element to check all the elements on the left of it, to find the first one which is smaller.

The worst case run time for that would be O(n^2). For an array of length n, it would take: 0 + 1 + 2 + 3 + … + (n-1) comparisons. = (n-1)*n/2 = O(n^2) comparisons.

But with a stack we can improve that.

Want to learn more about Stacks?

Check out my Course on Linked Lists, Stacks and Queues

Bubble Sort Explained, Implemented in Python and Time Complexity Analysis

What will we cover?

  • What is Bubble sort and how does it work?
  • How to implement it in Python
  • How to evaluate the time complexity of the Bubble sort algorithm

What is Bubble sort and how does it work?

In this video the Bubble sort algorithm is explained. On a high level, it takes an unsorted list and returns it sorted.

How to implement Bubble sort in Python

Well, notice the above description. It is straight forward and simple to implement. That is one of the beauties of the algorithm. Simple to understand. Simple to implement.

def bubble_sort(my_list):
    for i in range(len(my_list), 1, -1):
        for j in range(1, i):
            if my_list[j-1] > my_list[j]:
                my_list[j-1], my_list[j] = my_list[j], my_list[j-1]

An simple illustration of how you can use it.

import random


def generate_random_list(n):
    my_list = []
    for i in range(n):
        my_list.append(random.randint(0, n))
    return my_list


def bubble_sort(my_list):
    for i in range(len(my_list), 1, -1):
        for j in range(1, i):
            if my_list[j-1] > my_list[j]:
                my_list[j-1], my_list[j] = my_list[j], my_list[j-1]



my_list = generate_random_list(20)
print(my_list)
bubble_sort(my_list)
print(my_list)

Evaluating the performance of Bubble sort

First of the algorithm has two for-loops. An outer and an inner for-loop. With an input of a list of length N, the loops will be iterated the following number of times.

  • Outer for-loop: N times
  • Inner for-loop: N-1 + N-2 + N-3 + … + 1 + 0 times

Knowing the formula

  • N-1 + N-2 + … + 1 + 0 = (N-1)*N/2

We can add that the time complexity of Bubble sort is O(n^2).

But let’s try to experiment with real running data, to see if we can confirm that complexity.

To get run-times from the algorithm the cProfile library comes in handy. It is easy to use and gives good insights. A simple way to get run-times is to set it like this.

import random
import cProfile


def generate_random_list(n):
    return [random.randint(0, 4*n) for i in range(n)]


def bubble_sort(my_list):
    for i in range(len(my_list), 1, -1):
        for j in range(1, i):
            if my_list[j-1] > my_list[j]:
                my_list[j-1], my_list[j] = my_list[j], my_list[j-1]


def profile_bubble_sort(n):
    my_list = generate_random_list(n)
    bubble_sort(my_list)


cProfile.run("profile_bubble_sort(10000)")

It will result in an output in the following manner.

         56372 function calls in 11.056 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000   11.056   11.056 <string>:1(<module>)
        1    0.000    0.000   11.055   11.055 BubbleSortProfiling.py:16(profile_bubble_sort)
        1    0.000    0.000    0.034    0.034 BubbleSortProfiling.py:5(generate_random_list)
        1    0.008    0.008    0.034    0.034 BubbleSortProfiling.py:6(<listcomp>)
        1   11.021   11.021   11.021   11.021 BubbleSortProfiling.py:9(bubble_sort)
    10000    0.010    0.000    0.022    0.000 random.py:200(randrange)
    10000    0.005    0.000    0.027    0.000 random.py:244(randint)
    10000    0.007    0.000    0.012    0.000 random.py:250(_randbelow_with_getrandbits)
        1    0.000    0.000   11.056   11.056 {built-in method builtins.exec}
        1    0.000    0.000    0.000    0.000 {built-in method builtins.len}
    10000    0.001    0.000    0.001    0.000 {method 'bit_length' of 'int' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
    16364    0.003    0.000    0.003    0.000 {method 'getrandbits' of '_random.Random' objects}

You get the time spend in Bubble sort by looking the highlighted line. In the column cumtime you get the time spend in total in the function.

By collecting the run-time for various sizes of lists, we get the following graph.

The graph has a O(n^2) growth as expected.