Maximum Product of Two Elements in an Array: Finding the Top Two
You are given an array of integers nums. Pick any two different indices i and j, and return the maximum value of (nums[i] - 1) * (nums[j] - 1). All values in the array are positive, so you never need to worry about negative numbers or zeros making the product behave unexpectedly.
This is LeetCode 1464: Maximum Product of Two Elements in an Array.
Why this problem matters
At first glance, this problem looks almost trivial. Find two numbers, subtract one from each, multiply them. But it is a clean exercise in recognizing when a greedy observation lets you skip brute force entirely. The brute force approach checks every pair of indices, which is O(n^2). The greedy approach runs in O(n) by noticing that you only ever need the two largest elements.
That leap from "check all pairs" to "just track the two biggest" is a pattern that shows up constantly in array problems. Variations of the same idea appear in Best Time to Buy and Sell Stock, Kth Largest Element, and many other problems where the answer depends on a small number of extreme values rather than on every possible combination.
This problem also gives you a chance to practice the single-pass tracking technique. Instead of sorting the entire array (which works but costs O(n log n)), you can maintain two variables and update them as you walk through the array once. That micro-skill transfers directly to harder problems.
The key insight
Since all values are positive and subtracting 1 preserves their relative order, the maximum product always comes from the two largest elements. If a and b are the two largest values in the array, then (a - 1) * (b - 1) is guaranteed to be the largest possible product. You do not need to check any other pairs.
This means the entire problem reduces to: find the two largest elements. You can do that in one pass by maintaining two variables, max1 and max2, and updating them as you scan.
The solution
def maxProduct(nums: list[int]) -> int:
max1 = max2 = 0
for num in nums:
if num >= max1:
max2 = max1
max1 = num
elif num > max2:
max2 = num
return (max1 - 1) * (max2 - 1)
The loop maintains two variables. max1 holds the largest value seen so far, and max2 holds the second largest. When a new value is at least as large as max1, the old max1 gets demoted to max2, and the new value takes over as max1. If the new value is only bigger than max2 (but not max1), it replaces max2 alone.
After the loop finishes, you have the two largest values and can compute the product in one line.
Initializing max1 and max2 to 0 works here because the problem guarantees all values are at least 1. For a more general version where values could be negative, you would initialize to negative infinity instead.
Visual walkthrough
Here is how the algorithm processes the array [3, 4, 5, 2] step by step.
After walking through all four elements, max1 = 5 and max2 = 4. The final answer is (5 - 1) * (4 - 1) = 12. The entire scan takes one pass with no extra memory.
Complexity analysis
| Approach | Time | Space |
|---|---|---|
| Single Pass | O(n) | O(1) |
Time: you visit each element exactly once, performing a constant number of comparisons per element. That gives O(n) total.
Space: you only store two variables (max1 and max2) regardless of the input size, so space is O(1).
The building blocks
1. Tracking the running maximum
best = 0
for num in nums:
if num > best:
best = num
This is the simplest form of single-pass tracking. You keep one variable and update it whenever you see something larger. The "maximum product" problem just extends this by tracking two values instead of one.
2. Maintaining the top-k values in a single pass
max1 = max2 = 0
for num in nums:
if num >= max1:
max2 = max1
max1 = num
elif num > max2:
max2 = num
When you need more than one extreme value, you "cascade" the updates. The current best gets bumped down to second best, and the new value takes first place. This pattern generalizes to top-3, top-4, and beyond, though for larger k you would typically switch to a heap.
Edge cases
- Array of length 2. The only pair is
(nums[0] - 1) * (nums[1] - 1). The algorithm handles this naturally since both values will be assigned tomax1andmax2during the loop. - All elements are the same. If every value is
v, thenmax1 = max2 = v, and the answer is(v - 1) * (v - 1). No special handling needed. - Very large values. With
nums[i]up to 10^3, the maximum product is999 * 999 = 998001, which fits comfortably in a 32-bit integer. No overflow concern in Python.
From understanding to recall
The idea behind this problem is simple: find the two biggest, subtract one from each, multiply. But interview pressure can make even simple ideas slippery. You might second-guess whether you need to sort, or whether negative numbers could matter, or whether you should use a heap. The way to make the right approach automatic is to practice it at spaced intervals. Drill the "track-top-two" pattern a few times over a couple of weeks, and it will be the first thing that comes to mind when you see a problem that depends on extreme values.
Related posts
- Contains Duplicate - another easy array problem that teaches a fundamental single-pass pattern
- Kth Largest Element - extends the "find extreme values" idea to arbitrary k using heaps and quickselect
- Best Time to Buy and Sell Stock - single-pass tracking of a running minimum to maximize profit
Recognizing that only the two largest values matter is the entire solve for this problem. Once you see it, the code writes itself. CodeBricks helps you build that recognition through spaced repetition drills on the underlying building blocks, so patterns like "track the top two" fire automatically when you need them.