Tutorialspoint.dev

Largest triplet product in a stream

Given a stream of integers represented as arr[]. For each index i from 0 to n-1, print the multiplication of largest, second largest, third largest element of the subarray arr[0…i]. If i < 2 print -1.

Examples:

Input : arr[] = {1, 2, 3, 4, 5}
Output :-1
        -1
         6
         24
         60
Explanation : for i = 2 only three elements 
are there {1, 2, 3} so answer is 6. For i = 3
largest three elements are {2, 3, 4} their
product is 2*3*4 = 24 ....so on            



We will use priority queue here.

  1. Insert arr[i] in the priority queue
  2. As the top element in priority queue is largest so pop it and store it as x. Now the top element in the priority queue will be the second largest element in subarray arr[0…i] pop it and store as y. Now the top element is third largest element in subarray arr[0…i] so pop it and store it as z.
  3. Print x*y*z
  4. Reinsert x, y, z.
// C++ implementation of largest triplet
// multiplication
#include<bits/stdc++.h>
using namespace std;
  
// Prints the product of three largest numbers
// in subarray arr[0..i]
void LargestTripletMultiplication(int arr[], int n)
{
    // call a priority queue
    priority_queue <int> q;
  
    // traversing the array
    for (int i = 0; i<n; i++)
    {
        // pushing arr[i] in array
        q.push(arr[i]);
  
        // if less than three elements are present
        // in array print -1
        if (q.size() < 3)
            cout << "-1" << endl;
        else
        {
            // pop three largest elements
            int x = q.top();
            q.pop();
            int y = q.top();
            q.pop();
            int z = q.top();
            q.pop();
  
            // Reinsert x, y, z in priority_queue
            int ans = x*y*z;
            cout << ans << endl;
            q.push(x);
            q.push(y);
            q.push(z);
        }
    }
    return ;
}
  
// Driver Function
int main()
{
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    LargestTripletMultiplication(arr, n);
    return 0;
}

Output:

-1
-1
6
24
60

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter