Leetcode 1464: Maximum product of two elements in an array

In this Leetcode problem, we are asked to compute the maximum product of 2 elements in the array, knowing that the elements are positive.

Problem statement

Solution

1. According to the constraints, all numbers are positive ( >0 )
2. Therefore the problem is equivalent to finding the 2 highest numbers in the array (a, b), and return the given product (a - 1)(b - 1)
3. We maintain a and b by iterating through the array
4. We maintain a ≤ b at each step
5. Algorithm is O(n), with n the size of the array; it is more efficient than sorting the array directly.

public int maxProduct(int[] nums) {
    int a = 0;
    int b = 0;
    for (int num : nums) {
        if (num > a) {
            a = num;
        }
        if (a > b) {
            // swap to maintain a <= b
            int ret = a;
            a = b;
            b = ret;
        }
    }
    return (a - 1) * (b - 1);
}

Happy coding :)

What’s next:

• Checkout the solution for another problem: Rearrange words in a sentence
• Contact me: poitevinpm@gmail.com
• Looking to interview for a software engineer position? Contact me :)