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:
- Problem Statement
- Approach 1: Sorting
- Approach 2: Insertion Sort
- 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:
- Maintain a set of Numbers S
- 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:
- Maintain a set of Numbers S
- 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:
- Maintain a set of Numbers S
- Maintain a variable LARGEST = NEGATIVE_INFINITY
- 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.