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.

Clarifying Questions

  1. Q: What are the constraints on the array nums?
    • A: At least three integers in the array. The array length will be between 3 and 10^4, and values will range between -1000 to 1000.
  2. Q: Can the numbers be both positive and negative?
    • A: Yes, the array can contain both positive and negative numbers including zero.
  3. Q: What if all numbers are negative?
    • A: The solution should still return the maximum product among any three selected numbers.

Strategy

  1. Sort the Array:
    • The simplest approach is to sort the array first.
    • After sorting, the potential candidates for the maximum product will be the largest three numbers or the two smallest numbers (most negative) and the largest number.
  2. Calculate Candidate Products:
    • From the sorted array, compute the product of the last three elements: nums[len-1] * nums[len-2] * nums[len-3].
    • Compute the product of the two smallest elements and the largest element: nums[0] * nums[1] * nums[len-1].
  3. Return the Maximum:
    • Return the maximum value between the two computed products.

Code

public class Solution {
    public int maximumProduct(int[] nums) {
        // Sort the array
        Arrays.sort(nums);
        
        int n = nums.length;
        // Candidate 1: product of the three largest numbers
        int candidate1 = nums[n-1] * nums[n-2] * nums[n-3];
        // Candidate 2: product of the two smallest numbers and the largest number
        int candidate2 = nums[0] * nums[1] * nums[n-1];
        
        // Return the maximum of the two candidates
        return Math.max(candidate1, candidate2);
    }
}

Time Complexity

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

This method ensures that we correctly identify the maximum product by considering both positive and negative numbers efficiently.

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