Maximum Product of Two Elements in an Array

Easy
261.

Maximum Product of Two Elements in an Array

Maximum Product of Two Elements in an Array is an easy coding problem on arrays, sorting and heap, asked in Amazon and Adobe interviews.

Given the array of integers nums, choose two different indices i and j and maximise (nums[i] - 1) * (nums[j] - 1).

Return that maximum value.

Example 1

Input
nums = [3,4,5,2]
Output
12
Explanation
Picking 5 and 4 gives (5-1)×(4-1) = 12.

Example 2

Input
nums = [1,5,4,5]
Output
16
Explanation
The two 5s sit at different indices.

Example 3

Input
nums = [3,7]
Output
12

Constraints

  • 2 <= nums.length <= 40
  • 1 <= nums[i] <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxProduct = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Product of Two Elements in an Array — Solution

Maximum Product of Two Elements in an Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Maximum Product of Two Elements in an Array is an easy coding problem on arrays, sorting and heap, asked in Amazon and Adobe interviews.

  • Difficulty: Easy
  • Topics: Arrays, Sorting, Heap
  • Asked at: Amazon, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given the array of integers nums, choose two different indices i and j and maximise (nums[i] - 1) * (nums[j] - 1).

Return that maximum value.

Example 1

Input: nums = [3,4,5,2]
Output: 12
Explanation: Picking 5 and 4 gives (5-1)×(4-1) = 12.

Example 2

Input: nums = [1,5,4,5]
Output: 16
Explanation: The two 5s sit at different indices.

Example 3

Input: nums = [3,7]
Output: 12

Constraints

  • 2 <= nums.length <= 40
  • 1 <= nums[i] <= 1000

Hints for Maximum Product of Two Elements in an Array

  1. Hint 1

    All values are at least 1, so (x - 1) is never negative — the two largest values win.

  2. Hint 2

    One pass carrying the largest and second largest is enough; no sort required.

  3. Hint 3

    Duplicated maxima are fine, since the indices only have to differ.

How to solve Maximum Product of Two Elements in an Array

All values are at least 1, so (x - 1) is non-negative and the two largest values give the maximum product.

Approach

  1. One pass keeping first and second largest.
  2. Return (first - 1) * (second - 1).

Why it works

With non-negative factors the product is maximised by maximising both, and indices only need to differ, so equal maxima are fine.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • When updating, demote the old first to second before overwriting.

Reference solution

Python

def maxProduct(nums) -> int:
    first = second = -1
    for x in nums:
        if x > first:
            first, second = x, first
        elif x > second:
            second = x
    return (first - 1) * (second - 1)

Java

public static int maxProduct(int[] nums) {
    int first = -1, second = -1;
    for (int x : nums) {
        if (x > first) {
            second = first;
            first = x;
        } else if (x > second) {
            second = x;
        }
    }
    return (first - 1) * (second - 1);
}

C++

int maxProduct(vector<int>& nums) {
    int first = -1, second = -1;
    for (int x : nums) {
        if (x > first) {
            second = first;
            first = x;
        } else if (x > second) {
            second = x;
        }
    }
    return (first - 1) * (second - 1);
}

JavaScript

var maxProduct = function(nums) {
    let first = -1, second = -1;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] > first) {
            second = first;
            first = nums[i];
        } else if (nums[i] > second) {
            second = nums[i];
        }
    }
    return (first - 1) * (second - 1);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms