LeetCode 1464 - Maximum Product of Two Elements in an Array

The problem gives an integer array nums, and asks us to choose two different indices i and j. For those two elements, we compute the expression: Our goal is to return the maximum possible value of this expression.

leetcodeeasyarraysortingheap-(priority-queue)

LeetCode Problem 1464

Difficulty: 🟢 Easy
Topics: Array, Sorting, Heap (Priority Queue)

Solution

Problem Understanding

The problem gives an integer array nums, and asks us to choose two different indices i and j. For those two elements, we compute the expression:

$(nums[i]-1)(nums[j]-1)$

Our goal is to return the maximum possible value of this expression.

In simpler terms, we need to find the two numbers in the array that produce the largest product after subtracting 1 from each of them. Since subtraction by 1 preserves the relative ordering of positive numbers, the optimal pair will always be the two largest values in the array.

The input is an array of integers where:

  • The array length is between 2 and 500
  • Each element is between 1 and 1000

These constraints are relatively small, which means even a brute-force solution would work within limits. However, the problem is designed to test whether we can recognize the mathematical observation that only the two largest elements matter.

An important detail is that the two indices must be different. We cannot use the same element twice unless it appears multiple times in the array.

There are several edge cases worth thinking about early:

  • Arrays with exactly two elements, because there is only one possible pair
  • Arrays containing duplicate maximum values, such as [5,5]
  • Arrays containing many small values like 1, where subtracting 1 produces 0
  • Arrays where the maximum values appear late in the traversal, which tests whether the tracking logic updates correctly

The constraints guarantee that the array always contains at least two numbers, so we never need to handle empty arrays or single-element arrays.

Approaches

Brute-Force Approach

The most direct solution is to try every possible pair of indices (i, j) where i != j.

For each pair:

  1. Compute (nums[i] - 1) * (nums[j] - 1)
  2. Compare it against the current maximum
  3. Keep the largest result found

This approach is correct because it explicitly checks every valid pair, so the true maximum cannot be missed.

However, the time complexity is quadratic because for every element we compare against every other element. While the input size here is small enough that this would still pass, it is not the most efficient solution.

Optimal Approach

The key observation is that the expression depends only on the two largest numbers.

Suppose the two largest elements are:

  • max1
  • max2

Then the answer is:

$(max1-1)(max2-1)$

Why does this work?

Because all numbers are positive integers. If one number is larger than another, subtracting 1 still preserves the ordering. Therefore, maximizing the product simply means selecting the two largest values.

Instead of sorting the array, we can scan it once while tracking:

  • The largest value seen so far
  • The second-largest value seen so far

This gives an optimal linear-time solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Checks every possible pair
Optimal O(n) O(1) Tracks the two largest elements in one pass

Algorithm Walkthrough

Optimal One-Pass Algorithm

  1. Initialize two variables, largest and second_largest, to 0.

These variables will store the two biggest numbers encountered during traversal. 2. Iterate through every number in the array.

At each step, determine whether the current number should become the new largest or second largest value. 3. If the current number is greater than largest, update both variables.

The previous largest becomes second_largest, and the current number becomes the new largest. 4. Otherwise, if the current number is greater than second_largest, update only second_largest.

This ensures we always maintain the top two numbers seen so far. 5. After processing the entire array, compute:

$(largest-1)(second_largest-1)$ 6. Return the result.

Why it works

At every iteration, the algorithm maintains the invariant that:

  • largest is the biggest number seen so far
  • second_largest is the second-biggest number seen so far

Because every element is processed exactly once and the invariant is preserved after each update, the final values of largest and second_largest are guaranteed to be the two largest numbers in the array. Since the expression is maximized by choosing the two largest numbers, the algorithm always produces the correct answer.

Python Solution

from typing import List

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        largest = 0
        second_largest = 0

        for num in nums:
            if num > largest:
                second_largest = largest
                largest = num
            elif num > second_largest:
                second_largest = num

        return (largest - 1) * (second_largest - 1)

The implementation begins by initializing two tracking variables, largest and second_largest.

The loop processes each number exactly once. If the current number exceeds the current largest value, the previous largest value is demoted to second largest, and the current number becomes the new maximum.

If the number is not larger than the maximum but is still larger than the second-largest value, only second_largest is updated.

After the traversal completes, the algorithm computes the required expression using the two stored maximum values.

This implementation avoids sorting entirely, which keeps the runtime linear and the memory usage constant.

Go Solution

func maxProduct(nums []int) int {
    largest := 0
    secondLargest := 0

    for _, num := range nums {
        if num > largest {
            secondLargest = largest
            largest = num
        } else if num > secondLargest {
            secondLargest = num
        }
    }

    return (largest - 1) * (secondLargest - 1)
}

The Go implementation follows the same logic as the Python solution. The primary difference is syntax and iteration style.

Go uses a for _, num := range nums loop to iterate through the slice. Integer arithmetic is straightforward here because the constraints are small enough that overflow is not a concern with Go's standard int type.

Since the problem guarantees at least two elements, there is no need for additional nil or empty slice checks.

Worked Examples

Example 1

Input:

nums = [3,4,5,2]
Iteration Current Number largest second_largest
Start - 0 0
1 3 3 0
2 4 4 3
3 5 5 4
4 2 5 4

Final computation:

$(5-1)(4-1)=4\cdot3=12$

Output:

12

Example 2

Input:

nums = [1,5,4,5]
Iteration Current Number largest second_largest
Start - 0 0
1 1 1 0
2 5 5 1
3 4 5 4
4 5 5 5

Final computation:

$(5-1)(5-1)=4\cdot4=16$

Output:

16

Example 3

Input:

nums = [3,7]
Iteration Current Number largest second_largest
Start - 0 0
1 3 3 0
2 7 7 3

Final computation:

$(7-1)(3-1)=6\cdot2=12$

Output:

12

Complexity Analysis

Measure Complexity Explanation
Time O(n) The array is traversed exactly once
Space O(1) Only two tracking variables are used

The algorithm performs a single linear scan through the array. Each iteration performs only constant-time comparisons and assignments. No additional data structures proportional to input size are allocated, so the space usage remains constant.

Test Cases

from typing import List

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        largest = 0
        second_largest = 0

        for num in nums:
            if num > largest:
                second_largest = largest
                largest = num
            elif num > second_largest:
                second_largest = num

        return (largest - 1) * (second_largest - 1)

solution = Solution()

assert solution.maxProduct([3, 4, 5, 2]) == 12  # basic example
assert solution.maxProduct([1, 5, 4, 5]) == 16  # duplicate maximum values
assert solution.maxProduct([3, 7]) == 12  # minimum array size
assert solution.maxProduct([1, 1]) == 0  # smallest possible values
assert solution.maxProduct([10, 2, 5, 2]) == 36  # largest values separated
assert solution.maxProduct([9, 9, 8]) == 64  # equal largest elements
assert solution.maxProduct([1000, 1000]) == 998001  # upper constraint values
assert solution.maxProduct([2, 3]) == 2  # simple two-element case
assert solution.maxProduct([1, 2, 3, 4, 5]) == 12  # increasing order
assert solution.maxProduct([5, 4, 3, 2, 1]) == 12  # decreasing order
Test Why
[3,4,5,2] Validates the standard example
[1,5,4,5] Ensures duplicate maximums work correctly
[3,7] Tests minimum valid array length
[1,1] Verifies handling of zeros after subtraction
[10,2,5,2] Confirms algorithm finds non-adjacent maxima
[9,9,8] Checks repeated largest values
[1000,1000] Tests upper constraint boundaries
[2,3] Simple smallest non-trivial case
[1,2,3,4,5] Validates increasing order traversal
[5,4,3,2,1] Validates decreasing order traversal

Edge Cases

One important edge case is an array containing exactly two elements. In this situation, there is only one possible pair to choose from. Some implementations accidentally assume additional elements exist when updating tracking variables. The current solution handles this naturally because the traversal logic works correctly even with only two iterations.

Another important case involves duplicate maximum values, such as [5,5] or [1,5,4,5]. A buggy implementation might incorrectly overwrite one maximum and fail to preserve the second occurrence. This solution correctly updates second_largest whenever another value equal to the maximum appears.

Arrays containing many 1 values are also important. Since subtracting 1 from 1 produces 0, the final product may become zero. For example, [1,1] should return 0. The implementation handles this correctly because it directly computes the mathematical expression after identifying the two largest values.

A final edge case is when the maximum element appears near the end of the array. For example, [1,2,3,1000] requires updating both tracking variables late in traversal. The algorithm correctly shifts the previous maximum into second_largest whenever a new largest value appears.