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 the largest, second largest, and 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

Input: arr[] = {-5, -2, 0, 3, 6, 7}
Output: -1 -1 0 0 0 126
Explanation: For i = 2: Three elements are {-5, -2, 0}, so their product = 0.
For i = 3: Three largest elements are {-2, 0, 3}, product = 0.
For i = 4: Three largest elements are {0, 3, 6}, product = 0.
For i = 5: Three largest elements are {3, 6, 7}, product = 3*6*7 = 126.

Input: arr[] = {2, 2, 2, 2, 2}
Output: -1 -1 8 8 8
Explanation: For i = 2: Three elements {2, 2, 2}, so 2*2*2 = 8.
For i = 3 and onwards, the largest three elements are always {2, 2, 2}, so output remains 8.

Using Heap - O(n * logn) Time and O(n) Space

The idea is to maintain the three largest elements encountered so far using a heap data structure. For every element in the input, if fewer than three elements are available, the output is -1. Otherwise, the product of the three largest elements is calculated and stored.

Steps to implement the above idea:

• Initialize a max-heap to track the largest elements and a result list for storing outputs.
• Traverse the input array and push each element into the max-heap.
• If the heap size is less than 3, append -1 to the result list.
• When the heap size is at least 3, extract the three largest elements from the heap.
• Calculate the product of these three elements, append it to the result list, and push them back into the heap.
• Finally, return or print the result list containing the outputs.

// C++ implementation of largest triplet
// multiplication
#include <bits/stdc++.h>
using namespace std;

vector<int> largestTripletProducts(vector<int>& arr) {
    priority_queue<int> pq;
    vector<int> result;
    
    for (int i = 0; i < arr.size(); i++) {
        pq.push(arr[i]);

        // If there are less than 3 elements, push -1
        if (pq.size() < 3) {
            result.push_back(-1);
        } else {
            // Extract top 3 elements
            int first = pq.top(); pq.pop();
            int second = pq.top(); pq.pop();
            int third = pq.top(); pq.pop();

            result.push_back(first * second * third);

            // Push them back
            pq.push(first);
            pq.push(second);
            pq.push(third);
        }
    }
    return result;
}

void printArr(vector<int>& arr) {
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
}

// Driver Code
int main() {
    vector<int> arr = {1, 2, 3, 4, 5};
    vector<int> result = largestTripletProducts(arr);
    printArr(result);
    return 0;
}

// Java implementation of largest triplet
// multiplication
import java.util.*;

class GfG {
    static List<Integer> largestTripletProducts(int[] arr) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        List<Integer> result = new ArrayList<>();

        for (int i = 0; i < arr.length; i++) {
            pq.add(arr[i]);

            // If there are less than 3 elements, push -1
            if (pq.size() < 3) {
                result.add(-1);
            } else {
                // Extract top 3 elements
                int first = pq.poll();
                int second = pq.poll();
                int third = pq.poll();

                result.add(first * second * third);

                // Push them back
                pq.add(first);
                pq.add(second);
                pq.add(third);
            }
        }
        return result;
    }

    static void printArr(List<Integer> arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        List<Integer> result = largestTripletProducts(arr);
        printArr(result);
    }
}

# Python3 implementation of largest triplet
# multiplication
import heapq

def largest_triplet_products(arr):
    # Max heap (invert values to use Python's min-heap as max-heap)
    max_heap = []
    result = []

    for num in arr:
        # Push the current number (negative for max-heap simulation)
        heapq.heappush(max_heap, -num)

        # If there are less than 3 elements, append -1
        if len(max_heap) < 3:
            result.append(-1)
        else:
            # Extract the top 3 elements
            first = -heapq.heappop(max_heap)
            second = -heapq.heappop(max_heap)
            third = -heapq.heappop(max_heap)

            # Calculate the product
            result.append(first * second * third)

            # Push them back into the heap
            heapq.heappush(max_heap, -first)
            heapq.heappush(max_heap, -second)
            heapq.heappush(max_heap, -third)

    return result

def print_arr(arr):
    print(" ".join(map(str, arr)))

# Driver code
if __name__ == "__main__":
    arr = [1, 2, 3, 4, 5]
    result = largest_triplet_products(arr)
    print_arr(result)

// C# implementation of largest triplet
// multiplication
using System;
using System.Collections.Generic;

class GfG {
    static List<int> LargestTripletProducts(int[] arr) {
        SortedSet<int> pq = new SortedSet<int>(Comparer<int>.Create((a, b) => b - a));
        List<int> result = new List<int>();

        for (int i = 0; i < arr.Length; i++) {
            pq.Add(arr[i]);

            // If there are less than 3 elements, push -1
            if (pq.Count < 3) {
                result.Add(-1);
            } else {
                // Extract top 3 elements
                int[] top3 = new int[3];
                pq.CopyTo(top3, 0, 3);

                result.Add(top3[0] * top3[1] * top3[2]);
            }
        }
        return result;
    }

    static void PrintArr(List<int> arr) {
        foreach (int num in arr) {
            Console.Write(num + " ");
        }
        Console.WriteLine();
    }

    public static void Main() {
        int[] arr = {1, 2, 3, 4, 5};
        List<int> result = LargestTripletProducts(arr);
        PrintArr(result);
    }
}

// javascript implementation of largest triplet
// multiplication
function largestTripletProducts(arr) {
    // Use a max heap simulated with an array
    let maxHeap = [];
    let result = [];

    for (let num of arr) {
        // Push the current number into the heap
        maxHeap.push(num);

        // Sort in descending order to simulate a max-heap
        maxHeap.sort((a, b) => b - a);

        // If there are less than 3 elements, push -1
        if (maxHeap.length < 3) {
            result.push(-1);
        } else {
            // Extract the top 3 largest elements
            let first = maxHeap[0];
            let second = maxHeap[1];
            let third = maxHeap[2];

            // Calculate the product
            result.push(first * second * third);
        }
    }
    return result;
}

function printArr(arr) {
    console.log(arr.join(" "));
}

// Example usage
let arr = [1, 2, 3, 4, 5];
let result = largestTripletProducts(arr);
printArr(result);

-1 -1 6 24 60 

Without Using Heap - O(n) Time and O(1) Space

The idea is to track the three largest elements encountered so far using three variables. For each element in the input, update these variables if the current element is larger than any of them. If fewer than three elements exist or the third largest is uninitialized, append -1. Otherwise, calculate the product of the three largest and store it in the result.

Steps to implement the above idea:

• Initialize three variables to store the largest, second largest, and third largest values, starting with the smallest possible values.
• Create a result list to store the output for each step.
• Traverse the input array, updating the three variables whenever a new larger element is encountered.
• If fewer than three elements have been processed or the third variable remains uninitialized, append -1 to the result.
• Otherwise, calculate the product of the three largest variables and append it to the result.
• Finally, print the result list containing the products or -1 values.

// C++ implementation using three variables
#include <bits/stdc++.h>
using namespace std;

void largestTripletProducts(vector<int>& arr) {
    int first = INT_MIN, second = INT_MIN, third = INT_MIN;
    vector<int> result;

    for (int num : arr) {
        if (num > first) {
            third = second;
            second = first;
            first = num;
        } else if (num > second) {
            third = second;
            second = num;
        } else if (num > third) {
            third = num;
        }

        if (arr.size() < 3) {
            result.push_back(-1);
        } else if (third == INT_MIN) {
            result.push_back(-1);
        } else {
            result.push_back(first * second * third);
        }
    }
    
    for (int num : result) {
        cout << num << " ";
    }
    cout << endl;
}

// Driver Code
int main() {
    vector<int> arr = {1, 2, 3, 4, 5};
    largestTripletProducts(arr);
    return 0;
}

// Java implementation using three variables
import java.util.*;

class GfG {
    static List<Integer> largestTripletProducts(int[] arr) {
        int first = Integer.MIN_VALUE, second = Integer.MIN_VALUE, third = Integer.MIN_VALUE;
        List<Integer> result = new ArrayList<>();

        for (int num : arr) {
            if (num > first) {
                third = second;
                second = first;
                first = num;
            } else if (num > second) {
                third = second;
                second = num;
            } else if (num > third) {
                third = num;
            }

            if (result.size() < 2) {
                result.add(-1);
            } else if (third == Integer.MIN_VALUE) {
                result.add(-1);
            } else {
                result.add(first * second * third);
            }
        }
        return result;
    }

    static void printArr(List<Integer> arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        List<Integer> result = largestTripletProducts(arr);
        printArr(result);
    }
}

# Python implementation using three variables

def largest_triplet_products(arr):
    first = second = third = float('-inf')
    result = []

    for num in arr:
        if num > first:
            third = second
            second = first
            first = num
        elif num > second:
            third = second
            second = num
        elif num > third:
            third = num

        if len(result) < 2:
            result.append(-1)
        elif third == float('-inf'):
            result.append(-1)
        else:
            result.append(first * second * third)

    return result

def print_arr(arr):
    print(" ".join(map(str, arr)))

# Driver code
if __name__ == "__main__":
    arr = [1, 2, 3, 4, 5]
    result = largest_triplet_products(arr)
    print_arr(result)

// C# implementation using three variables
using System;
using System.Collections.Generic;

class GfG {
    static List<int> LargestTripletProducts(int[] arr) {
        int first = int.MinValue, second = int.MinValue, third = int.MinValue;
        List<int> result = new List<int>();

        for (int i = 0; i < arr.Length; i++) {
            if (arr[i] > first) {
                third = second;
                second = first;
                first = arr[i];
            } else if (arr[i] > second) {
                third = second;
                second = arr[i];
            } else if (arr[i] > third) {
                third = arr[i];
            }

            if (i < 2) {
                result.Add(-1);
            } else {
                result.Add(first * second * third);
            }
        }
        return result;
    }

    static void PrintArr(List<int> arr) {
        foreach (int num in arr) {
            Console.Write(num + " ");
        }
        Console.WriteLine();
    }

    public static void Main() {
        int[] arr = {1, 2, 3, 4, 5};
        List<int> result = LargestTripletProducts(arr);
        PrintArr(result);
    }
}

// JavaScript implementation using three variables
function largestTripletProducts(arr) {
    let first = Number.MIN_SAFE_INTEGER, 
        second = Number.MIN_SAFE_INTEGER, 
        third = Number.MIN_SAFE_INTEGER;
    let result = [];

    for (let i = 0; i < arr.length; i++) {
        if (arr[i] > first) {
            third = second;
            second = first;
            first = arr[i];
        } else if (arr[i] > second) {
            third = second;
            second = arr[i];
        } else if (arr[i] > third) {
            third = arr[i];
        }

        if (i < 2) {
            result.push(-1);
        } else {
            result.push(first * second * third);
        }
    }
    return result;
}

function printArr(arr) {
    console.log(arr.join(" "));
}

// Example usage
let arr = [1, 2, 3, 4, 5];
let result = largestTripletProducts(arr);
printArr(result);

-1 -1 6 24 60