Jobs

Interviews

Discussions

Maximum Product of Two Elements in an Array

Easy

Apple

9 views

Topics:

ArraysGreedy Algorithms

Given the array of integers nums, you will choose two different indices i and j of that array. Return the maximum value of (nums[i]-1)*(nums[j]-1).

Example 1:

Input: nums = [3,4,5,2]
Output: 12 
Explanation: If you choose the indices i=1 and j=2 (indexed from 0), you will get the maximum value, that is, (nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12.

Example 2:

Input: nums = [1,5,4,5]
Output: 16
Explanation: Choosing the indices i=1 and j=3 (indexed from 0), you will get the maximum value of (5-1)*(5-1) = 16.

Example 3:

Input: nums = [3,7]
Output: 12

Constraints:

2 <= nums.length <= 500
1 <= nums[i] <= 10^3

Maximum Product of Two Elements in an Array

Easy

Apple

9 views

Topics:

ArraysGreedy Algorithms

Given the array of integers nums, you will choose two different indices i and j of that array. Return the maximum value of (nums[i]-1)*(nums[j]-1).

Example 1:

Input: nums = [3,4,5,2]
Output: 12 
Explanation: If you choose the indices i=1 and j=2 (indexed from 0), you will get the maximum value, that is, (nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12.

Example 2:

Input: nums = [1,5,4,5]
Output: 16
Explanation: Choosing the indices i=1 and j=3 (indexed from 0), you will get the maximum value of (5-1)*(5-1) = 16.

Example 3:

Input: nums = [3,7]
Output: 12

Constraints:

2 <= nums.length <= 500
1 <= nums[i] <= 10^3

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values within the array, and can the array contain negative numbers, zeros, or floating-point numbers?
What should I return if the array has fewer than two elements?
Are there any constraints on the size of the array?
If multiple pairs result in the same maximum product, can I return any one of those pairs?
Is the input array mutable, or should I avoid modifying it in place?

Brute Force Solution

Approach

To find the largest result you can get from multiplying two numbers from a collection, the most basic approach is to simply try every possible pair. We'll pick each number in turn and multiply it with every other number, remembering the biggest result we've seen so far.

Here's how the algorithm would work step-by-step:

Start with the first number in your collection.
Multiply it by every other number in the collection, one at a time.
Remember the largest product you found so far during those multiplications.
Now, move on to the second number in your collection.
Multiply it by every other number in the collection (including the first number).
Again, compare each product to the largest product you've found so far, and update your memory if you find an even bigger one.
Continue doing this for each number in the collection, making sure to multiply it by all the other numbers.
Once you've gone through all the numbers and all the pairs, the largest product you remembered is your answer.

Code Implementation

def maximum_product_of_two_elements(number_collection):

    maximum_product = float('-inf')

    # Iterate through each number in collection
    for first_index in range(len(number_collection)):

        # Iterate through all other numbers
        for second_index in range(len(number_collection)):

            # Avoid multiplying a number by itself
            if first_index != second_index:

                product = (number_collection[first_index] - 1) * \
                          (number_collection[second_index] - 1)

                # Track the largest product
                if product > maximum_product:

                    # We found a new maximum product
                    maximum_product = product

    return maximum_product

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The provided approach iterates through each of the n elements in the input array. For each element, it multiplies it with every other element in the array. This means that for each of the n elements, we perform approximately n multiplications. Thus, the total number of operations is proportional to n * n, resulting in a time complexity of O(n²).

Space Complexity

O(1) – The provided algorithm iterates through the input array and keeps track of the maximum product found so far. It only uses a single variable to store this maximum product, and no additional data structures that scale with the input size are used. Therefore, the auxiliary space required is constant and independent of the input array's size (N). This results in a space complexity of O(1).

Optimal Solution

Approach

The goal is to find two numbers in a set, subtract one from each, and then multiply the results to get the largest possible product. The best way to do this is to focus on finding the two biggest numbers quickly because those will give you the biggest results after the subtraction and multiplication.

Here's how the algorithm would work step-by-step:

First, find the largest number in the set.
Next, find the second-largest number in the set.
Subtract one from the largest number.
Subtract one from the second-largest number.
Multiply the two results from the previous two steps.
This product will be the largest possible product you can get by following the problem's rules.

Code Implementation

def maximum_product_of_two_elements(numbers):
    largest_number = 0
    second_largest_number = 0

    for number in numbers:
        if number > largest_number:
            # Current num is new max, shift the old max
            second_largest_number = largest_number
            largest_number = number
        elif number > second_largest_number:
            # Number is only greater than the second largest
            second_largest_number = number

    # Subtract 1 from the largest number as per the prompt
    largest_number_adjusted = largest_number - 1

    second_largest_number_adjusted = second_largest_number - 1

    # The maximum product is the product of these two adjusted numbers
    maximum_product = largest_number_adjusted * second_largest_number_adjusted

    return maximum_product

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – Finding the largest element requires iterating through the entire array of n elements once. Similarly, finding the second largest element also requires iterating through the array (or a significant portion of it in the worst case) once. These two iterations are performed sequentially, not nested. Therefore, the total number of operations scales linearly with the input size n, resulting in a time complexity of O(n).

Space Complexity

O(1) – The provided approach identifies the largest and second largest elements. It only uses a few variables to store these numbers during traversal of the input array of size N. No additional data structures that scale with the input size are created. Therefore, the auxiliary space remains constant regardless of the size of the input array, resulting in O(1) space complexity.

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 or throw an IllegalArgumentException as there are no elements to multiply.
Array with only two elements	Return (nums[0]-1) * (nums[1]-1) directly as these are the only possible elements.
Array with all identical values	The algorithm should still correctly identify the two largest (same) values and return (value-1)*(value-1).
Array with negative numbers	The algorithm should correctly handle negative numbers, since it searches for the two largest elements regardless of sign.
Array containing zero	The zero values will be handled like any other number, since it searches for the two largest numbers.
Large array with many elements	Ensure the algorithm's time complexity remains efficient, ideally O(n), to avoid performance issues.
Integer overflow when multiplying	Consider using long to store the result of the multiplication to prevent integer overflow, if necessary.
Array containing maximum integer value	The (num-1) calculation should not cause issues or wraparound, as that could affect maximum finding.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values within the array, and can the array contain negative numbers, zeros, or floating-point numbers?
What should I return if the array has fewer than two elements?
Are there any constraints on the size of the array?
If multiple pairs result in the same maximum product, can I return any one of those pairs?
Is the input array mutable, or should I avoid modifying it in place?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the first number in your collection.
Multiply it by every other number in the collection, one at a time.
Remember the largest product you found so far during those multiplications.
Now, move on to the second number in your collection.
Multiply it by every other number in the collection (including the first number).
Again, compare each product to the largest product you've found so far, and update your memory if you find an even bigger one.
Continue doing this for each number in the collection, making sure to multiply it by all the other numbers.
Once you've gone through all the numbers and all the pairs, the largest product you remembered is your answer.

Code Implementation

def maximum_product_of_two_elements(number_collection):

    maximum_product = float('-inf')

    # Iterate through each number in collection
    for first_index in range(len(number_collection)):

        # Iterate through all other numbers
        for second_index in range(len(number_collection)):

            # Avoid multiplying a number by itself
            if first_index != second_index:

                product = (number_collection[first_index] - 1) * \
                          (number_collection[second_index] - 1)

                # Track the largest product
                if product > maximum_product:

                    # We found a new maximum product
                    maximum_product = product

    return maximum_product

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, find the largest number in the set.
Next, find the second-largest number in the set.
Subtract one from the largest number.
Subtract one from the second-largest number.
Multiply the two results from the previous two steps.
This product will be the largest possible product you can get by following the problem's rules.

Code Implementation

def maximum_product_of_two_elements(numbers):
    largest_number = 0
    second_largest_number = 0

    for number in numbers:
        if number > largest_number:
            # Current num is new max, shift the old max
            second_largest_number = largest_number
            largest_number = number
        elif number > second_largest_number:
            # Number is only greater than the second largest
            second_largest_number = number

    # Subtract 1 from the largest number as per the prompt
    largest_number_adjusted = largest_number - 1

    second_largest_number_adjusted = second_largest_number - 1

    # The maximum product is the product of these two adjusted numbers
    maximum_product = largest_number_adjusted * second_largest_number_adjusted

    return maximum_product

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 or throw an IllegalArgumentException as there are no elements to multiply.
Array with only two elements	Return (nums[0]-1) * (nums[1]-1) directly as these are the only possible elements.
Array with all identical values	The algorithm should still correctly identify the two largest (same) values and return (value-1)*(value-1).
Array with negative numbers	The algorithm should correctly handle negative numbers, since it searches for the two largest elements regardless of sign.
Array containing zero	The zero values will be handled like any other number, since it searches for the two largest numbers.
Large array with many elements	Ensure the algorithm's time complexity remains efficient, ideally O(n), to avoid performance issues.
Integer overflow when multiplying	Consider using long to store the result of the multiplication to prevent integer overflow, if necessary.
Array containing maximum integer value	The (num-1) calculation should not cause issues or wraparound, as that could affect maximum finding.