algoadvance

Leetcode 1464. Maximum Product of Two Elements in an Array

Problem Statement

You are given an integer array nums. The goal is to find the maximum product of two elements in the array. To do this, you pick two different indices i and j such that the product ((nums[i] - 1) * (nums[j] - 1)) is maximized, where (i \neq j).

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

Clarifying Questions

  1. Input Size: What is the range of the input array size?
    • The array length can be between 2 and 500.
  2. Element Range: What are the range of the elements in the array?
    • Each element in the array is a positive integer between 1 and 10,000.
  3. Uniqueness: Are all the elements in the array unique?
    • The problem does not specify that the elements are unique, so they may be repeated.

Strategy

Steps:

  1. Initialize two variables max1 and max2 to store the largest and the second-largest elements in the array.
  2. Iterate through the array and update max1 and max2 accordingly.
  3. Calculate the product ((max1 - 1) \cdot (max2 - 1)) and return the result.

Code

Here’s the implementation in C++:

#include <vector>
#include <algorithm>

int maxProduct(std::vector<int>& nums) {
    int max1 = 0, max2 = 0;
    for (int num : nums) {
        if (num > max1) {
            max2 = max1;
            max1 = num;
        } else if (num > max2) {
            max2 = num;
        }
    }
    return (max1 - 1) * (max2 - 1);
}

Explanation of the Code

  1. Initialization: We start with max1 and max2 initialized to zero.
  2. Iteration: We iterate through each number in the array:
    • If the current number num is greater than max1, we update max2 to be max1 and then set max1 to num.
    • Else if num is larger than max2, update max2 to be num.
  3. Result Calculation: Finally, we return the product of ((max1 - 1) \cdot (max2 - 1)).

Time Complexity

The time complexity of this solution is (O(n)), where (n) is the number of elements in the array. This efficiency is because we only need a single pass through the array to determine the two largest elements. The space complexity is (O(1)) as we are using a fixed amount of additional space regardless of the input size.

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