no sort, O(n) time, O(1) space, derived idea from maxTwoProduct


  • 0
    N

    The maximum products of three elements in an array, definitely contains the maximum number in the array. Then find the rest maxTwoProduct or minTwoProduct.

    public class Solution {
        public int maximumProduct(int[] nums) {
            
            // find the maximum number
            int maxIndex = 0;
            for (int i = 1; i < nums.length; i++) {
                if (nums[i] > nums[maxIndex]) {
                    maxIndex = i;
                }
            }
            
            // find maxTwoProduct and minTwoProduct
            int maxTwo = Integer.MIN_VALUE;
            int minTwo = Integer.MAX_VALUE;
            int startIndex = 0;
            if (maxIndex == 0) {
                startIndex = 1;
            }
            int cur_max = nums[startIndex];
            int cur_min = nums[startIndex];
            
            for (int i = startIndex + 1; i < nums.length; i++) {
                if (i == maxIndex) {
                    continue;
                }
                maxTwo = Math.max(maxTwo, Math.max(cur_max * nums[i], cur_min * nums[i]));
                cur_max = Math.max(cur_max, nums[i]);
                minTwo = Math.min(minTwo, Math.min(cur_max * nums[i], cur_min * nums[i]));
                cur_min = Math.min(cur_min, nums[i]);
            }
    
            return Math.max(maxTwo * nums[maxIndex], minTwo * nums[maxIndex]);
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.