Largest Element in a stream

In this article, we have explored the problem of finding the largest 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 largest 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 largest 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 largest 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 largest 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 increasing 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 largest 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 largest 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 increasing 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 largest element using this approach are:

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

for(i=0; i<N; i++)
{
    int new_element = get_number();
    // Add new_element to set S
    if new_element > LARGEST
        LARGEST = new_element
    int answer = LARGEST;
    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 largest element in a stream efficiently. Enjoy.