DDSA Solutions

1464. Maximum Product of Two Elements in an Array

EasyView on LeetCode
ArraySortingHeap (Priority Queue)

Problem Overview

You need max (nums[i]−1)*(nums[j]−1) over distinct indices.

Intuition

You need max (nums[i]−1)*(nums[j]−1) over distinct indices. Because x ↦ x−1 is strictly increasing for the positive values in the constraints, the product of the two largest decremented values is best - so find the two largest elements and multiply (max1−1)*(max2−1).

Algorithm

  1. 1Initialize max1 = max2 = 0.
  2. 2For each num: if num > max1, shift max1 into max2 and set max1 = num; else if num > max2, set max2 = num.
  3. 3Return (max1 − 1) * (max2 − 1).

Example Walkthrough

Input: nums = [3, 4, 5, 2]

  1. 1.Scan: max1 becomes 3, then 4, then 5; max2 ends at 4.
  2. 2.Product (5−1)*(4−1) = 4*3 = 12.

Output: 12

Common Pitfalls

  • •Must use two different indices - do not square the single largest element.
  • •Update max2 when promoting a new max1; otherwise the previous max is lost.
  • •Constraints guarantee n ≥ 2 and positive nums, so the zero initialization is safe.
  • •Sorting also works but is O(n log n); one pass is enough.
1464.cs
C#
public class Solution
{
    // Approach: The product (a−1)*(b−1) is maximized by the two largest values
    // in the array. Track max1 and max2 in one pass, then return (max1−1)*(max2−1).
    // Complexity: O(n) time and O(1) space.
    public int MaxProduct(int[] nums)
    {
        int max1 = 0;
        int max2 = 0;

        foreach (int num in nums)
        {
            if (num > max1)
            {
                max2 = max1;
                max1 = num;
            }
            else if (num > max2)
                max2 = num;
        }

        return (max1 - 1) * (max2 - 1);
    }
}
Was this solution helpful?

Related Problems