Scale Engineer

Maximum Product of Two Elements in an Array

Easy
#1352Time: O(n^2), where n is the number of elements in `nums`. The nested loops result in a quadratic number of comparisons.Space: O(1), as we only use a constant amount of extra space for variables.3 companies
Algorithms
Sorting
Data structures
ArrayHeap (Priority Queue)
Companies
CiscoJ.P. MorganSamsung

Prompt

Given the 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).

 

Example 1:

Input: nums = [3,4,5,2]
Output: 12 
Explanation: If you choose the indices i=1 and j=2 (indexed from 0), you will get the maximum value, that is, (nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12.

Example 2:

Input: nums = [1,5,4,5]
Output: 16
Explanation: Choosing the indices i=1 and j=3 (indexed from 0), you will get the maximum value of (5-1)*(5-1) = 16.

Example 3:

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

 

Constraints:

  • 2 <= nums.length <= 500
  • 1 <= nums[i] <= 10^3

Approaches

3 approaches with complexity analysis and trade-offs.

This approach involves checking every possible pair of distinct elements in the array. We use nested loops to iterate through all pairs (i, j) where i is not equal to j. For each pair, we calculate the product (nums[i]-1)*(nums[j]-1) and keep track of the maximum product found so far.

Algorithm

  • Initialize a variable maxProduct to 0.
  • Use a nested loop to iterate through all pairs of distinct indices (i, j).
  • The outer loop runs from i = 0 to n-2.
  • The inner loop runs from j = i + 1 to n-1.
  • Inside the inner loop, calculate currentProduct = (nums[i] - 1) * (nums[j] - 1).
  • Update maxProduct by taking the maximum of maxProduct and currentProduct.
  • After the loops complete, return maxProduct.

Walkthrough

We initialize a variable maxProduct to 0. The outer loop iterates from the first element to the second-to-last element (index i). The inner loop iterates from the element after i to the last element (index j). This structure ensures that we consider each pair of distinct indices exactly once. Inside the inner loop, we compute the product (nums[i]-1) * (nums[j]-1). We then compare this product with the current maxProduct and update maxProduct if the current product is larger. After the loops finish iterating through all possible pairs, maxProduct will hold the maximum possible value.

class Solution {    public int maxProduct(int[] nums) {        int maxProduct = 0;        int n = nums.length;        for (int i = 0; i < n; i++) {            for (int j = i + 1; j < n; j++) {                int currentProduct = (nums[i] - 1) * (nums[j] - 1);                if (currentProduct > maxProduct) {                    maxProduct = currentProduct;                }            }        }        return maxProduct;    }}

Complexity

Time

O(n^2), where n is the number of elements in `nums`. The nested loops result in a quadratic number of comparisons.

Space

O(1), as we only use a constant amount of extra space for variables.

Trade-offs

Pros

  • Simple to understand and implement.

  • Guaranteed to find the correct answer as it checks all possibilities.

Cons

  • Highly inefficient for large arrays due to its O(n^2) time complexity.

  • Performs a lot of redundant calculations.

Solutions

class Solution {public  int maxProduct(int[] nums) {    int ans = 0;    int n = nums.length;    for (int i = 0; i < n; ++i) {      for (int j = i + 1; j < n; ++j) {        ans = Math.max(ans, (nums[i] - 1) * (nums[j] - 1));      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem