algoadvance

Leetcode 1464. Maximum Product of Two Elements in an Array

Problem Statement

Leetcode Problem 1464: Maximum Product of Two Elements in an Array

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

Clarifying Questions

  1. Element Range: Are the array elements guaranteed to be non-negative integers?
    • Yes.
  2. Array Size: What is the range of the size of the array nums?
    • The array size will be at least 2 and can be up to 10^3.
  3. Constraints: Are there any constraints on the values of the array elements?
    • Each nums[i] is an integer in the range [1, 10^3].

Strategy

To find the maximum product of (nums[i] - 1) * (nums[j] - 1), the optimal approach is to identify the two largest elements in the array because reducing the maximum numbers by 1 and then multiplying gives the highest product.

  1. Traverse the array to find the maximum (first_max) and the second maximum (second_max) numbers.
  2. Compute the product as (first_max - 1) * (second_max - 1) and return it.

Code

public class Solution {
    public int maxProduct(int[] nums) {
        // Initialize the first and second maximums
        int firstMax = Integer.MIN_VALUE;
        int secondMax = Integer.MIN_VALUE;
        
        // Traverse through the array to find the two largest numbers
        for (int num : nums) {
            if (num > firstMax) {
                secondMax = firstMax;
                firstMax = num;
            } else if (num > secondMax) {
                secondMax = num;
            }
        }
        
        // Calculate and return the result
        return (firstMax - 1) * (secondMax - 1);
    }
}

Time Complexity

Example Walkthrough

Consider nums = [3, 4, 5, 2].

  1. Initialization: firstMax = Integer.MIN_VALUE, secondMax = Integer.MIN_VALUE.
  2. After processing element 3:
    • firstMax = 3, secondMax = Integer.MIN_VALUE.
  3. After processing element 4:
    • firstMax = 4, secondMax = 3.
  4. After processing element 5:
    • firstMax = 5, secondMax = 4.
  5. After processing element 2:
    • No changes.

Final product: (5 - 1) * (4 - 1) = 4 * 3 = 12.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI