Smallest Element in a stream

In this article, we have explored the problem of finding the smallest element in a Stream of numbers. We have presented three approaches where in the efficient approach, we can solve the problem in O(1) time and O(1) space.

Table of content:

  1. Problem Statement
  2. Approach 1: Sorting
  3. Approach 2: Insertion Sort
  4. Approach 3: Efficient method [O(1) time]

Go through this article as a simpler version of this problem:

In summary:

Approach Time Complexity Space Complexity
Sorting O(N^2 logN) O(N)
Insertion Sort O(N^2) O(N)
Efficient Approach O(N) O(1)

Problem Statement

Given a stream of numbers, we have the find the smallest number whenever a new element is added from the stream.

A stream is a sequence of numbers where at time t(i), a number A(i) is added. At time J, the elements added include:

A(0), A(1), ..., A(J-1), A(J)

At every time J, we have to find the smallest element in the set of all numbers added.

There are three metrics:

  • Time Complexity for all operations
  • Time Complexity for a single operation
  • Space Complexity

We will tackle this problem with three approaches:

  • Approach 1: Sorting
  • Approach 2: Insertion Sort
  • Approach 3: Efficient method [O(1) time]

Approach 1: Sorting

The steps to find the smallest element using this approach are:

  1. Maintain a set of Numbers S
  2. For each time stamp t,
    2.1. add the new element E to the set S
    2.2. Sort the set using an efficient sorting algorithm
    2.3. Get the smallest element

Pseudocode:

S = {} // Empty set

for(i=0; i<N; i++)
{
    int new_element = get_number();
    // Add new_element to set S
    S.insert(new_element)
    // Sort in decreasing order
    // This step takes O(I logI) time
    // where I is the number of elements in S
    Arrays.sort(S);
    int answer = S[0];
    print answer;
}
  • Time Complexity: O(N logN) for each time stamp
  • Time Complexity: O(N^2 logN) for all N elements
  • Space Complexity: O(N)

Approach 2: Insertion Sort

The steps to find the smallest element using this approach are:

  1. Maintain a set of Numbers S
  2. For each time stamp t,
    2.1. add the new element E to the set S
    2.2. Sort the set using Insertion Sort
    2.3. Get the smallest element

This difference in this approach is that we are using Insertion Sort instead of a general sorting algorithm. This improves the time complexity because our array is almost sorted with only one element (new) which is out of order. The remaining elements are sorted.

So, in this case, Insertion sort can sort the last element in linear time O(N).

S = {} // Empty set

for(i=0; i<N; i++)
{
    int new_element = get_number();
    // Add new_element to set S
    S.insert(new_element)
    // Sort in decreasing order
    // This step takes O(I logI) time
    // where I is the number of elements in S
    Arrays.insertion_sort(S);
    int answer = S[0];
    print answer;
}
  • Time Complexity: O(N) for each time stamp
  • Time Complexity: O(N^2) for all N elements
  • Space Complexity: O(N)

Approach 3: Efficient method [O(1) time]

The steps to find the smallest element using this approach are:

  1. Maintain a set of Numbers S
  2. Maintain a variable SMALLEST = POSITIVE_INFINITY
  3. For each time stamp t,
    2.1. Let the new element be E
    2.2. If E < SMALLEST, then SMALLEST = E
    2.3. Report the answer as SMALLEST
S = {} // Empty set
int SMALLEST = POSITIVE_INFINITY

for(i=0; i<N; i++)
{
    int new_element = get_number();
    // Add new_element to set S
    if new_element < SMALLEST
        SMALLEST = new_element
    int answer = SMALLEST;
    print answer;
}
  • Time Complexity: O(1) for each time stamp
  • Time Complexity: O(N) for all N elements
  • Space Complexity: O(1)

In summary:

Approach Time Complexity Space Complexity
Sorting O(N^2 logN) O(N)
Insertion Sort O(N^2) O(N)
Efficient Approach O(N) O(1)

With this article at OpenGenus, you have the complete idea of finding the smallest element in a stream efficiently. Enjoy.