Maximum Product of Two Elements in an Array

easy heap top k array

Problem

Given an array of integers nums, choose two different indices i and j. Return the maximum value of (nums[i] − 1) · (nums[j] − 1).

Inputnums = [3,4,5,2]

Output12

Picking i=1 and j=2 gives (4−1)·(5−1) = 3·4 = 12.

Inputnums = [1,5,4,5]

Output16

The two largest are 5 and 5: (5−1)·(5−1) = 16.

nums (comma-separated)

def max_product(nums):
    first = second = 0          # two largest seen so far
    for v in nums:
        if v > first:
            second = first      # old max slides down
            first = v
        elif v > second:
            second = v
    return (first - 1) * (second - 1)

function maxProduct(nums) {
  let first = 0, second = 0;       // two largest seen so far
  for (const v of nums) {
    if (v > first) {
      second = first;              // old max slides down
      first = v;
    } else if (v > second) {
      second = v;
    }
  }
  return (first - 1) * (second - 1);
}

int maxProduct(int[] nums) {
    int first = 0, second = 0;       // two largest seen so far
    for (int v : nums) {
        if (v > first) {
            second = first;          // old max slides down
            first = v;
        } else if (v > second) {
            second = v;
        }
    }
    return (first - 1) * (second - 1);
}

int maxProduct(vector<int>& nums) {
    int first = 0, second = 0;       // two largest seen so far
    for (int v : nums) {
        if (v > first) {
            second = first;          // old max slides down
            first = v;
        } else if (v > second) {
            second = v;
        }
    }
    return (first - 1) * (second - 1);
}

Explanation

Because (x − 1) grows with x and every value is at least 1, the product (nums[i] − 1)·(nums[j] − 1) is maximized by simply choosing the two largest elements. So the whole problem reduces to "find the top two values."

Finding the top k elements is the classic job of a max-heap / priority queue. Here k = 2 is tiny, so instead of a full heap we keep just two slots, first (the largest) and second (the runner-up) — a hand-rolled size-2 max-heap that we maintain in O(1) per element.

We scan once. For each value v: if v beats first, the old champion slides down into second and v becomes the new first. Otherwise, if v only beats second, it just replaces second. Anything smaller is ignored.

Starting both slots at 0 is safe because the constraint nums[i] ≥ 1 means real values always win the comparisons, and there are always at least two elements.

After the pass, the answer is (first − 1)·(second − 1). For [3,4,5,2] the top two are 5 and 4, giving (5−1)·(4−1) = 4·3 = 12.

This runs in O(n) time and O(1) space — strictly better than sorting, which a general heap-based top-k would also beat for small k.

Time: O(n) Space: O(1)