Largest Triple Products – Revisited

!!! UPDATE UPDATE UPDATE !!!

I received a comment indicating an issue with the largestValues() function. The issue has been corrected. The code has been updated. Thanks for noting the issue.

Good morning! It is 04:15 AM and it is a relatively warm day. Last evening before going to bed I decided to hopefully get up a little earlier than usual. I have a permanent alarm on my phone for 06:00 AM. I use it as a fail-safe in case I do not naturally wake up before. Today I wanted to get this post done and take a look at a test I left running overnight. My wife has a doctor’s appointment early today and it is a 45 minute drive from home. She has to fast so I will follow suit. We should be leaving home around 06:45 AM.

On a separate note, I visited the ProtonMail web site. As we all know there are companies that offer free email services. They have redefined what the word free means. The cost is quite heavy regarding your privacy. In the past couple weeks I have been reading about email services. My wife and I are contemplating on opening accounts on a service in the near future. When that happens, you will see a new email address at the bottom of the posts.

The purpose of this post is to make some changes to the post Largest Triple Products based on the following comment I received:

“That’s nice but man, it’s a 3-element min-heap, you don’t really need to unleash PriorityQueue — which by the way cost you that horrific toArray() call inside the loop …”

First of all thanks for the comment. I agree that the implementation works and using a priority queue is somewhat expensive no matter what, but the conversion back to an array in the loop might be pushing it too much.

I was just going to reply to the comment and leave it there, but instead I decided to generate this update.

I would like to mention that the problem came from a Facebook site and the code is not tested with dozens of test cases or for performance. If I am not mistaken there were two or perhaps three unit test cases associated with it. I typically lean towards problems offered by HackerRank and LeetCode.

The solution works but is not the most efficient way to solve the problem. In general it is always best to generate a solution that works and then fine tune it. Of course there are cases in which a completely different approach might produce the best results. You should always be ready to discard the entire approach and start from scratch. In this case I will just concentrate on reducing the overhead of using the priority queue and the array conversion.

I also decided to start with the problem as I always do in this post. I considered just editing the previous post, but here we are.

I found the problem at Largest Triple Products

(https://www.facebookrecruiting.com/portal/coding_practice_question/?problem_id=510655302929581). The description follows:

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.

The idea is to compute the product of a rolling 3-element window which gets updated each time if a new larger element is found in the array. Since we already saw the problem will move on.

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

I will solve the problem using the Java programming language. The signature for the method of interest seems to match well the problem description. We are given an array of integer and need to return a new array in which the elements are generated as required by the problem statement.

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


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


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


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


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


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

The test code that I wrote provides a single input line with the integer values for the array to be used as an argument for the method in question.

The test code seems to read the input line, create and populate an array and display it to make sure all is well so far.

A couple lines are then displayed. It seems that the lines contain the largest elements when we consider the input elements 1, 2, and 3 and then 2, 3, and 4. The line for the last set of number which should be 3, 4 and 5 is not display. Keep in mind that the two lines are just displayed to visualize if things are going as expected with the code. At this point we are assuming they do.

We then display the results generated by two implementations. The results seem to match. The first line is generated by the previous edited implementation. The second line displays the results of the latest implementation.

You might check the rest of the test cases to verify that the requirements are met and that the two implementations produce the same results.

    /**
     * Test scaffolding
     * 
     * !!!! NOT PART OF SOLUTION !!!!
     * @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 (take 1) ****
        System.out.println("main <<<  output: " + Arrays.toString(findMaxProduct(arr)));

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

This code snippet represents the test code used to collect input to provide for the method in question. The method is called and the results displayed. Note that we save the first array and after the first call we replace it. This is done because the first array is modified by the method of interest.

    /**
     * Edited previous implementation.
     */
    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;

        PriorityQueue<Integer> maxVals = new PriorityQueue<Integer>( (a,b) -> (a - b) );

        maxVals.add(arr[0]);
        maxVals.add(arr[1]);
        maxVals.add(arr[2]);

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

            // ???? ????
            System.out.println("<<< maxVals: " + maxVals.toString());

            // **** 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;
    }

This is the edited implementation of the code that I generated in the previous post.

We start by performing some sanity checks followed by an initialization of some variables. Among them we have a priority queue. Note that the comparator is expressed in a simpler way this time around. We then populate the priority queue with the first three elements from the array.

We then traverse the array updating the priority queue which only contains three elements at a time.

You can see that we display the contents of the priority queue before we update it. This is why the last set of values is not displayed in the screen captures.

The core of the loop checks if the new value is larger that the largest value in the priority queue. If so, we remove the lowest value and add the new largest value. We extract the three values into an array and multiply them to generate the new product.

    /**
     * Updated implementation.
     */
    static int[] findMaxProduct1(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;
        
        // **** compute the largest three values and return them in the array ****
        int[] largest = new int[] {Integer.MIN_VALUE, Integer.MIN_VALUE, Integer.MIN_VALUE};
        for (int i = 0; i < 3; i++)
            largest = largestValues(largest, arr[i]);

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

            // **** update the top three largest values ****
            largest = largestValues(largest, arr[i]);

            // **** generate the product of the three lasget values ****
            prods[i] = largest[0] * largest[1] * largest[2];
        }

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

The updated implementation starts by performing some sanity checks and performing the initialization step. Note that we do not use a priority queue in this implementation. The queue has been replaced by an array of three elements which we initialize by loading the first three elements in the input array. This should help to visualize what we are doing in the largestValue() utility method. In the main loop we just check and if needed update the largest int[] array on each pass. We then just multiply the three elements and save them as we did in the previous implementation. Note that we do not have a priority queue and we do not need to convert the priority queue to an array. That should save some execution time.

    /**
     * Largest values in descending order.
     * 
     * Utility method.
     */
    static private int[] largestValues(int[] largest, int val) {

        // ???? ????
        // System.out.println("<<< val: " + val + " largest: " + Arrays.toString(largest));

        // **** update the top three values ****
        if (val > largest[0]) {
            largest[2] = largest[1];
            largest[1] = largest[0];
            largest[0] = val;
        }

        // **** update the top two values ****
        else if (val > largest[1]) {
            largest[2] = largest[1];
            largest[1] = val;
        }

        // **** update the top value ****
        else if (val > largest[2]) {
            largest[2] = val;
        }

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

        // **** return the top three values ****
        return largest;
    }

This utility method takes as an input an array of three values and updates it if needed with the specified value. This method eliminates the need for the priority queue and the conversion to an array so the caller can generate the product of the three values.

Thanks for the comment. Please keep them coming.

Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository (https://github.com/JohnCanessa/LargestTripleProducts).

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 one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.

One last thing, many thanks to all 7,254 subscribers to this blog!!!

Keep safe during the COVID-19 pandemic and help restart the world economy. I believe we can all see the light at the end of the tunnel.

Regards;

John

john.canessa@gmail.com