algoadvance

Leetcode 628. Maximum Product of Three Numbers

Problem Statement

Given an integer array nums, find three numbers whose product is maximum and return the maximum product.

Example

Input: nums = [1,2,3]
Output: 6

Input: nums = [1,2,3,4]
Output: 24

Input: nums = [-1,-2,-3]
Output: -6

Constraints

Clarifying Questions

  1. Should we account for very large products that might cause overflow issues?
    • The problem statement does not specify data type overflow handling specifically, so we will assume that standard integer operations in C++ are sufficient.
  2. Can the array contain duplicate values?
    • Yes, the array can contain duplicate values.
  3. Do we need to handle input validation (e.g., ensuring there are at least three numbers)?
    • The constraints guarantee that the array will contain at least three numbers, so input validation is not required.

Strategy

  1. Sorting the Array:
    • Sort the array and then consider both ends of the sorted array to find the maximum product.
  2. Two Possible Scenarios:
    • Top Three Positive or Largest Negatives: The maximum product will either be the product of the three largest numbers.
    • Product involving the largest and smallest elements: The product of the two smallest numbers (which could be negative) and the largest number (which could be positive) might also be the maximum product.

By sorting the array, we can easily access the largest and smallest values to compute both scenarios and then return the maximum of the two products.

Code

#include <iostream>
#include <vector>
#include <algorithm>

class Solution {
public:
    int maximumProduct(std::vector<int>& nums) {
        std::sort(nums.begin(), nums.end());
        
        int n = nums.size();
        
        int product1 = nums[n-1] * nums[n-2] * nums[n-3];
        int product2 = nums[0] * nums[1] * nums[n-1];
        
        return std::max(product1, product2);
    }
};

int main() {
    Solution solution;
    std::vector<int> nums1 = {1, 2, 3};
    std::cout << "Maximum product of nums1: " << solution.maximumProduct(nums1) << std::endl;

    std::vector<int> nums2 = {1, 2, 3, 4};
    std::cout << "Maximum product of nums2: " << solution.maximumProduct(nums2) << std::endl;

    std::vector<int> nums3 = {-1, -2, -3};
    std::cout << "Maximum product of nums3: " << solution.maximumProduct(nums3) << std::endl;

    return 0;
}

Time Complexity

Therefore, the overall time complexity is O(n log n).

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