Maximum Product of Two Elements in an Array

Maximum Product of Two Elements in an Array - Problem

Given an array of integers nums, you will choose two different indices i and j of that array.

Return the maximum value of (nums[i]-1) * (nums[j]-1).

Input & Output

Example 1 — Basic Case

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

› Output: 12

💡 Note: Choose indices 1 and 2: (4-1) * (5-1) = 3 * 4 = 12

Example 2 — Minimum Size

$ Input: nums = [1,5]

› Output: 0

💡 Note: Only two elements: (1-1) * (5-1) = 0 * 4 = 0

Example 3 — All Same Values

$ Input: nums = [3,3,3,3]

› Output: 4

💡 Note: All elements equal: (3-1) * (3-1) = 2 * 2 = 4

Constraints

2 ≤ nums.length ≤ 500
1 ≤ nums[i] ≤ 10³

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array of integers

Find Largest Two

Identify the two largest values

Calculate Product

Return (max1-1) * (max2-1)

Key Takeaway

🎯 Key Insight: Maximum product always comes from the two largest elements in the array

Asked in

a Amazon 15 M Microsoft 8

The key insight is that maximum product comes from the two largest elements in the array. Best approach is the one-pass solution tracking the largest and second-largest elements. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ One Pass - Track Two Largest	O(n)	O(1)	Find two largest elements in single pass without sorting
Sort and Pick Top Two	O(n log n)	O(1)	Sort the array and multiply the two largest elements
Brute Force - Check All Pairs	O(n²)	O(1)	Try every possible pair of indices and find the maximum product

One Pass - Track Two Largest — Algorithm Steps

Initialize first and second largest variables
Iterate through array updating largest values
Return (first-1) * (second-1)

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set first=0, second=0 to track largest values

Iterate

Update first and second as we find larger elements

Calculate

Multiply (first-1) * (second-1)

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize) {
    int first = 0, second = 0;
    
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] > first) {
            second = first;
            first = nums[i];
        } else if (nums[i] > second) {
            second = nums[i];
        }
    }
    
    return (first - 1) * (second - 1);
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int count = 0;
    char* token = strtok(line + 1, ",]");
    
    while (token != NULL) {
        nums[count++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, count);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the array

✓ Linear Growth

Space Complexity

O(1)

Only two variables to track largest elements

✓ Linear Space

25.0K Views

Medium Frequency

~10 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

One Pass - Track Two Largest — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler