1464. Maximum Product of Two Elements in an Array

EasyArraySortingHeap (Priority Queue)
Leetcode Link

Problem Description

In this LeetCode problem, we are given an array of integers called nums. Our goal is to select two different indices i and j within this array. We are then asked to calculate the product of the values at these indices, decreased by 1. Specifically, we need to find (nums[i] - 1) * (nums[j] - 1) that results in the maximum possible value. To clarify, since i and j must be different, the elements nums[i] and nums[j] must be distinct elements—even if they have the same value.

Intuition

The key intuition here is that in order to maximize the product (nums[i] - 1) * (nums[j] - 1), we need to identify the two largest numbers in the array nums. This is because the product of any other pair would be less than or equal to the product of the two largest numbers.

The thought process starts with initializing two variables, which will hold the two largest numbers found while iterating through the array. As we go through each number in the array:

  • If we find a number greater than the largest number we've found so far (a), then we shift the previous largest number to be the second-largest (b) and update the largest number (a) with the new number.
  • If the current number is not larger than a but is larger than b, we just update the second-largest number (b).

Once we have the two largest numbers, we subtract 1 from each (as per the problem statement) and return their product. By following this approach, we do not need to worry about which indices we chose; we only need the values to compute the desired maximum product.

Learn more about Sorting and Heap (Priority Queue) patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of these properties could exist for a graph but not a tree?

Solution Approach

The solution uses a straightforward linear scan algorithm to iterate through the array of numbers. We use two variables, a and b, to keep track of the largest and second-largest numbers in the array, respectively. There's no need for any additional data structure as we only need to maintain these two variables through the iteration.

Here's a step-by-step walkthrough of the implementation:

  1. Initialize two variables, a and b, both set to 0. These will be used to track the largest (a) and second largest (b) numbers in the array.

  2. Loop through each value v in the array nums.

  3. Check if the current value v is greater than our current largest value a.

    • If v is larger than a, then we need to update both a and b. Set b to the old value of a (because a is going to be replaced with a larger value, and thus the previous a becomes the second-largest), and a to v.

  4. If v is not larger than a but is larger than b, then just update b to be v, because we found a new second-largest number.

  5. Once the loop is over, we have identified the two largest values in the array. We calculate the result as (a - 1) * (b - 1) and return it.

  6. Return the computed product as the solution.

In terms of complexity:

  • Time Complexity is O(n) because we go through the array of numbers exactly once.
  • Space Complexity is O(1) as we are using a fixed amount of space regardless of the input array size.

The elegance of this approach lies in its simplicity and efficiency, as there is no need for sorting or additional data structures like heaps or trees, which would increase the complexity of the solution.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

Example Walkthrough

Consider an example array nums given as [3, 4, 5, 2].

Following the solution approach:

  1. Initialize two variables a and b to 0. So initially, a = 0 and b = 0.

  2. Loop through each value v in the array nums.

  3. Start with the first value 3:

    • Is 3 greater than a (which is 0)? Yes.
    • Update b to the current a, so now b = 0.
    • Update a to the current value v, now a = 3.

  4. Move to the second value 4:

    • Is 4 greater than a (which is 3)? Yes.
    • Update b to the current a, so now b = 3.
    • Update a to the current value v, now a = 4.

  5. Now, look at the third value 5:

    • Is 5 greater than a (which is 4)? Yes.
    • Update b to the current a, so b = 4.
    • Update a to 5, the current value v.

  6. Finally, consider the last value 2:

    • Is 2 greater than a (which is 5)? No.
    • Is 2 greater than b (which is 4)? No.
    • So no updates to a or b occur because 2 is neither the largest nor the second-largest number found so far.

  7. After the loop, our two largest values have been found: a = 5 and b = 4.

  8. Calculate the result as (a - 1) * (b - 1), which is (5 - 1) * (4 - 1) = 4 * 3 = 12.

  9. Return the product 12 as the solution.

In this example, the selected values are 5 (at index 2) and 4 (at index 1). Subtracting 1 from each and then multiplying, we get the maximum possible product value 12 as the output for this input array.

Solution Implementation

1from typing import List
2
3class Solution:
4    def maxProduct(self, nums: List[int]) -> int:
5        # Initialize the two largest numbers as 0
6        max_num1 = max_num2 = 0
7      
8        # Loop through each number in the list
9        for value in nums:
10            # If the current value is greater than the first maximum number
11            if value > max_num1:
12                # Update the first and second maximum numbers
13                max_num1, max_num2 = value, max_num1
14            # Else if the current value is only greater than the second maximum number
15            elif value > max_num2:
16                # Update the second maximum number
17                max_num2 = value
18      
19        # Return the product of the two highest numbers after subtracting 1 from each
20        return (max_num1 - 1) * (max_num2 - 1)
21
1class Solution {
2    public int maxProduct(int[] nums) {
3        // Initialize two variables to store the largest and second largest values
4        // We start with the smallest possible values for integers
5        int maxVal = Integer.MIN_VALUE;
6        int secondMaxVal = Integer.MIN_VALUE;
7
8        // Iterate through each value in the nums array
9        for (int value : nums) {
10            // Check if the current value is greater than the largest value found so far
11            if (value > maxVal) {
12                // If it is, the current largest becomes the second largest,
13                // and the current value becomes the new largest
14                secondMaxVal = maxVal;
15                maxVal = value;
16            } else if (value > secondMaxVal) {
17                // If the current value is not larger than the largest but is larger
18                // than the second largest, update the second largest
19                secondMaxVal = value;
20            }
21        }
22
23        // Return the product of the largest and second largest values decreased by 1
24        // This is because the problem statement likely intended for a pair of values
25        // whose product is maximized after each is decreased by 1
26        return (maxVal - 1) * (secondMaxVal - 1);
27    }
28}
29
1#include <vector> // Include the necessary header for vector
2
3class Solution {
4public:
5    // Function to calculate the maximum product of (the max number - 1) and (the second max number - 1) in a vector
6    int maxProduct(vector<int>& nums) {
7        int maxNum = 0; // Initialize the maximum number to 0
8        int secondMaxNum = 0; // Initialize the second maximum number to 0
9      
10        // Iterate through each number in the vector
11        for (int value : nums) {
12            // If current value is greater than the maximum number found so far
13            if (value > maxNum) {
14                secondMaxNum = maxNum; // Assign the old maximum to be the second maximum
15                maxNum = value; // Update the maximum number to the current value
16            } 
17            // Else if current value is not greater than maxNum but greater than secondMaxNum
18            else if (value > secondMaxNum) {
19                secondMaxNum = value; // Update the second maximum number to the current value
20            }
21        }
22      
23        // Calculate and return the product of (maxNum - 1) and (secondMaxNum - 1)
24        return (maxNum - 1) * (secondMaxNum - 1);
25    }
26};
27
1/**
2 * Finds the maximum product of (num1 - 1) * (num2 - 1) where num1 and num2 
3 * are the two largest numbers in the array.
4 * @param nums Array of numbers.
5 * @returns The maximum product.
6 */
7function maxProduct(nums: number[]): number {
8    let firstMax = 0; // Holds the largest number found in the array
9    let secondMax = 0; // Holds the second largest number found in the array
10
11    // Iterate through each number in the provided array
12    for (const num of nums) {
13        if (num > firstMax) {
14            // If the current number is greater than firstMax, update secondMax to firstMax
15            // and then update firstMax to the current number
16            secondMax = firstMax;
17            firstMax = num;
18        } else if (num > secondMax) {
19            // If the current number is not greater than firstMax but is greater than secondMax,
20            // update secondMax to the current number
21            secondMax = num;
22        }
23    }
24
25    // Return the product of (firstMax - 1) and (secondMax - 1)
26    return (firstMax - 1) * (secondMax - 1);
27}
28
Not Sure What to Study? Take the 2-min Quiz：

Which of the following array represent a max heap?

Time and Space Complexity

The time complexity of the given code is O(n), where n is the length of the input array nums. This is because the code includes a single for-loop that iterates over all elements in the array once to find the two largest elements.

The space complexity of the solution is O(1). This is constant space because the solution only uses a fixed amount of extra space to store the largest (a) and the second-largest (b) values in the array, regardless of the input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which algorithm should you use to find a node that is close to the root of the tree?

Recommended Readings

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

Heap Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫