Largest Triple Products

Once again it is Friday during the COVID-19 pandemic. Not much to say due to the fact that outside work not much is changing. So far the COVID-19 vaccine development programs appear to be moving forward. Earlier this week UK started vaccinating people in nursing homes.

One of the sons of my best friend was married last year and moved to the UK. His wife and he had a baby boy about three months ago. My friend’s son, his spouse and newborn arrived earlier today for a month long visit. Hope they have a great time. Hopefully a month from now with the help of vaccines things will be getting better all over the world.

Earlier today I decided to solve the Largest Triple Products problem at Facebook. I have been solving a few problems from them and would like to finish the on-line set before the end of this month. With the holidays ahead it might be hard. That said; things will be quite different this holiday season.

You're given a list of n integers arr[0..(n-1)]. 
You must compute a list output[0..(n-1)] such that, 
for each index i (between 0 and n-1, inclusive), 
output[i] is equal to the product of the three largest elements out of arr[0..i] 
(or equal to -1 if i < 2, as arr[0..i] then includes fewer than three elements).

Note that the three largest elements used to form any product may have the same values as one another, 
but they must be at different indices in arr.

Input:
o n is in the range [1, 100,000].
o Each value arr[i] is in the range [1, 1,000].

Output:
Return a list of n integers output[0..(n-1)], as described above.

If you are interested in solving this problem, please visit the Facebook web site and read the requirements on-line.

In this case it appears that we get an array of integers. The idea is to return the product for the largest three numbers from the first element in the array to the current one. If you are having issues fully understanding the problem, take a look at the provided examples.

int[] findMaxProduct(int[] arr) {
}

The signature of the function / method indicates that we get the array of integers and have to return a new array in which for each element after the first two, we need to return the product of the three largest numbers we have already seen. This means that the first two returned values would be -1 because we have only seen two entries. When we hit the third entry, the result will be the product of the first three entries in the input array. From then on we need to maintain a running set of the largest integers.

1,2,3,4,5
main <<< arr: [1, 2, 3, 4, 5]
main <<< output: [-1, -1, 6, 24, 60]


2,1,2,1,2
main <<< arr: [2, 1, 2, 1, 2]
main <<< output: [-1, -1, 4, 4, 8]


1
main <<< arr: [1]
main <<< output: [-1]


1,2
main <<< arr: [1, 2]
main <<< output: [-1, -1]


1,2,3
main <<< arr: [1, 2, 3]
<<< maxVals: [1, 2, 3]
main <<< output: [-1, -1, 6]


1,2,3,4,3,2,1
main <<< arr: [1, 2, 3, 4, 3, 2, 1]
main <<< output: [-1, -1, 6, 24, 36, 36, 36]

I have solved the problem on my computer. Because of this I had to develop a test scaffolding. The test software needs to read the input line. Then it has to generate the associated array of integers. The values can then be used by the findMaxProduct() function which will return an array of products. The output is then displayed.

The first two test cases are the ones provided by Facebook. The other examples were used to verify end conditions.

For this problem I decided to use Java on a Windows 10 computer and the VSCode IDE. Since the solution is in Java it should run on any computer that supports the JVM.

    /**
     * Test scaffolding
     * 
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
        
        // **** open buffered reader ****
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // **** read and split strings with integers ****
        String[] strs = br.readLine().trim().split(",");

        // **** close buffered reader ****
        br.close();
        
        // **** create integer array with string values ****
        int[] arr = Arrays.stream(strs).mapToInt(Integer::parseInt).toArray();

        // ???? ????
        System.out.println("main <<< arr: " + Arrays.toString(arr));

        // **** find the max products and display result ****
        System.out.println("main <<< output: " + Arrays.toString(findMaxProduct(arr)));
    }

The test scaffolding reads the input line. It splits the integer values into a String array. The string array is used to generate an integer array with the associated values. The array is displayed to verify all is well so far.

No we are ready to invoke the function / method in question and display the returned values.

    /**
     * 
     */
    static int[] findMaxProduct(int[] arr) {

        // **** sanity check(s) ****
        if (arr.length == 1)
            return new int[] { -1 };

        if (arr.length == 2)
            return new int[] { -1, -1 };

        // **** initialization ****
        int[] prods = new int[arr.length];
        prods[0]    = prods[1] = -1;
        int prod    = arr[0] * arr[1] * arr[2];
        prods[2]    = prod;

        // **** priority heap (implemented with a priority queue) ****
        PriorityQueue<Integer> maxVals = new PriorityQueue<Integer>(new Comparator<Integer>() {
            @Override
            public int compare(Integer x, Integer y) {
                return Integer.compare(x, y);
            }
        });
        maxVals.add(arr[0]);
        maxVals.add(arr[1]);
        maxVals.add(arr[2]);

        // **** traverse array O(n) ****
        for (int i = 3; i < arr.length; i++) {

            // **** update max values (if needed) ****
            if (arr[i] > maxVals.peek()) {

                // **** remove from head of the queue (smallest value) ****
                maxVals.remove();

                // **** add new highest value ****
                maxVals.add(arr[i]);

                // **** compute the max product ****
                Integer[] tmp = (Integer[]) maxVals.toArray(new Integer[0]);
                prod = tmp[0] * tmp[1] * tmp[2];
            }

            // **** set the max product in the array ****
            prods[i] = prod;
        }

        // **** return array of max products ****
        return prods;
    }

We could use some logic and a set of variables and be able to track the set of largest values as we traverse the input array. Since the problem was under the title “heap”, we will use a priority heap. Since Java does not offer a priority heap, we will use a priority queue.

We start the function by performing some sanity checks. We then move into the initialization section.

We have to create a priority queue with a comparator. A priority queue will keep the values (three in this case) in ascending or descending order. In our case we went with ascending order. The lowest value will be at the head of the priority queue. The first three values are processed before we enter the loop.

In the loop we process the rest of the values in the input array.  We start by checking if the current array value (arr[i]) is larger than the one at the head of the priority queue. If so, we remove the smallest value in the set of three and add the new highest value. We then compute the product of the three largest values.

We then populate the associated entry in the output array.

The process repeats until there are no more input values to process.

I was going to solve the problem using a set of variables, but decided to skip it. If interested give it a try and let me know your thoughts.

Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.

Please note that we only have the samples and two tests cases to verify the operation of the solution. In general we would require a few dozen tests. If you find an issue with the solution, please let me know. I will make the necessary changes to better fir th erequirements.

If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.

Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset!

One last thing, many thanks to all 4,996 subscribers to this blog!!!

Keep safe during the COVID-19 pandemic and help restart the world economy.

Regards;

John

john.canessa@gmail.com