JavaScript Challenge - Max Product Finder

This community-built FAQ covers the “Max Product Finder” code challenge in JavaScript. You can find that challenge here, or pick any challenge you like from our list.

Top Discussions on the JavaScript challenge Max Product Finder

There are currently no frequently asked questions or top answers associated with this challenge – that’s where you come in! You can contribute to this section by offering your own questions, answers, or clarifications on this challenge. Ask a question or post a solution by clicking reply (reply) below.

If you’ve had an “aha” moment about the concepts, formatting, syntax, or anything else with this challenge, consider sharing those insights! Teaching others and answering their questions is one of the best ways to learn and stay sharp.

Join the Discussion. Help a fellow learner on their journey.

Ask or answer a question about this exercise by clicking reply (reply) below!
You can also find further discussion and get answers to your questions over in #get-help.

Agree with a comment or answer? Like (like) to up-vote the contribution!

Need broader help or resources? Head to #get-help and #community:tips-and-resources. If you are wanting feedback or inspiration for a project, check out #project.

Looking for motivation to keep learning? Join our wider discussions in #community

Learn more about how to use this guide.

Found a bug? Report it online, or post in #community:Codecademy-Bug-Reporting

Have a question about your account or billing? Reach out to our customer support team!

None of the above? Find out where to ask other questions here!

Below is my very wordy and probably over complicated attempt at this challenge.
I think I know what I’m missing to pass the 5th out of the 5 tests but I just don’t think that I have the brain power for it anymore at the moment.

Please, someone help me finish this!


function maxProductFinderK(array,k){

neg = ;

pos = ;

answer = 0;

usedNeg =

usedPos =

//functions for multiplying & moving to used array

function timesNeg(){

return Math.abs(answer) * Math.abs(neg[0]);

}

function timesPos(){

return Math.abs(answer) * pos[0];

}

//seperate negative and positive integers

for (let i=0; i < array.length; i++){

if (array[i] < 0) {

neg.push(array[i]);

}else{

  pos.push(array[i]);

  }

  }

//sort negative and postive arrays from largest absolute value

neg.sort(function(a,b) {

return a-b;

})

pos.sort(function(a,b){

return b-a;

})

//END OF FUNCTIONS*/

//**********K = ARRAY LENGTH */

if (k == array.length){

if (k==2){

  answer = array[0] * array[1];

  return answer

}else{

  answer = array[0] * array[1];

  array.shift;

  array.shift;

  for (i = 2; i < k; i++){

    answer = answer * array[0];

    array.shift();

}

return answer;

//**IF THERE ARE NO POSITIVES or NO NEGATIVES/

}

}else if (pos.length == 0 || neg.length == 0){

if (k==2){

  answer = array[0] * array[1];

  return answer

}else{

  answer = array[0] * array[1];

  array.shift;

  array.shift;

  for (i = 2; i < k; i++){

    answer = answer * array[0];

    array.shift();

}

return answer;

}

// IF THERE IS ONLY ONE NEGATIVE******

}else if (neg.length < 2 && pos.length > 1){

if (k==2){

  answer = pos[0] * pos[1];

  return answer;

}else{

  answer = pos[0] * pos[1];

  pos.shift;

  pos.shift;

  for (i = 2; i <k; i++){

    answer = answer * pos[0];

    pos.shift;

  }

  return answer;

}

// **IF THERE IS ONLY ONE POSITIVE

}else if (pos.length < 2 && neg.length > 1){

if (k==2){

  answer = neg[0] * neg[1];

  return answer;

}else{

  answer = neg[0] * neg[1];

  usedNeg.push(neg.shift());

  usedNeg.push(neg.shift());

}

for (i = 2; i < k; i++){

    answer = answer * neg[0];

    neg.shift();

}

if (answer < 0 && k == array.length) {

  answer = answer;

  }else if(answer < 0 && k == array.length -1){

    usedNegSorted = usedNeg.sort(function(a,b){

      return b-a;

      })

      answer /= usedNegSorted[0];

      answer = answer * pos[0];

      

      }else if (answer < 0 && k < array.length){

        answer /= usedNeg.slice(-1)[0];

        answer = answer * pos[0];

      }

      return answer;

}

//***********IF ITS A NORMAL ARRAY*******/

if (k==2){

if (neg[0]*neg[1] > pos[0]*pos[1]){

  answer = neg[0]*neg[1];

}else{

  answer = pos[0]*pos[1];

}

//if more that two variables used, starts with first two variable

}else{

if (neg[0]*neg[1] > pos[0]*pos[1]){

  answer = neg[0]*neg[1];

  usedNeg.push(neg.shift());

  usedNeg.push(neg.shift());

}else{

  answer = pos[0]*pos[1];

  usedPos.push(pos.shift());

  usedPos.push(pos.shift());

}

//continues after first 2

for (i = 2; i < k; i++){

if (timesNeg() > timesPos()){

  answer = answer * neg[0];

  usedNeg.push(neg.shift());

}else{

  answer = answer * pos[0];

  usedPos.push(pos.shift());

}

}

}

if (answer < 0 && k == array.length) {

answer = answer;

}else if(answer < 0 && k == array.length -1){

usedNegSorted = usedNeg.sort(function(a,b){

return b-a;

})

answer /= usedNegSorted[0];

answer = answer * pos[0];

}else if (answer < 0 && k < array.length){

answer /= usedNeg.slice(-1)[0];

answer = answer * pos[0];

}

return answer;

}

console.log(maxProductFinderK([-8, 6, -7, 3, -2, 1, -9], 3))

// Leave this so we can test your code:

module.exports = maxProductFinderK;

I didn’t use heaps. I iterated through the combinations instead.
I made lots of helper functions, like these:
I used generator functions to make an iterator to go through all the combinations, and another function to get the product of each combination. Form there, I found the maximum of the products.

Creating the structures and logic to generate the combinations was particularly difficult for me to figure out.

code for my solution
function next(n_1, k_1, kArray) {
  // n_1 is maximum value that can be in array
  // k_1 = kArray.length - 1;
  let currentIndex = k_1;
  if (kArray[k_1] != n_1) {
    kArray[k_1]++;
    return;
  }
  /* code to "carry" to next position is below */
  let i = k_1;  // to keep track of index where can stop
  let maxPossible = n_1;
  while((kArray[i] == maxPossible) && (i > 0)) {
    i--;
    maxPossible--;
  }
  let value = kArray[i];
  while (i <= k_1) {
    value++;
    kArray[i] = value;
    i++;
  }
  return (value <= n_1);
}

function* byIndexIterator(array, indexArray) {
  for (let j of indexArray) {
    yield array[j];
  }
}

function* combinationsGenerator(array, size) {
  const length = array.length;
  let indicesToUse = new Array(size);
  for (let i = 0; i < size; i++) {
    indicesToUse[i] = i;
  }
  let maxFirstIndex = length - size;
  while (indicesToUse[0] <= maxFirstIndex) {
    yield byIndexIterator(array, indicesToUse);
    next(length - 1, size - 1, indicesToUse);
  }
}

function productOf(nums) {
  let productSoFar = 1;
  for (let n of nums) {
    productSoFar = productSoFar * n;
  }
  return productSoFar;
}

function maxProductFinderK(numbers, size) {
  if (size < 1) {
    return NaN;
  }
  else if (size == 1) {
    return Math.max(...numbers);
  }
  let maxProduct; // = undefined;
  for (let combination of combinationsGenerator(numbers, size)) {
    let product = productOf(combination);
    if ((maxProduct == undefined) || (product > maxProduct)) {
      maxProduct = product;
    }
  }
  return maxProduct;
}


console.log(maxProductFinderK([-8, 6, -7, 3, 2, 1, -9], 3));  // 432
1 Like

Solution using heaps:

class MaxHeap {
  constructor() {
    this.heap = [null];
    this.size = 0;
  }

  getAbsHeapValue(index) {
    return Math.abs(this.getHeapValue(index));
  }

  getHeapValue(index) {
    return this.heap[index];
  }

  add(value) {
    this.heap.push(value);
    this.size++;
    this.bubbleUp();
  }

  bubbleUp() {
    let current = this.size;
    while (current > 1 && this.getAbsHeapValue(getParent(current)) < this.getAbsHeapValue(current)) {
      this.swap(current, getParent(current));
      current = getParent(current);
    }
  }

  popMax() {
    if (this.size === 0) {
      return null;
    }

    const max = this.heap[1];
    this.heap[1] = this.heap[this.size];
    this.heap.pop();
    this.size--;
    this.heapify();
    return max;
  }

  heapify() {
    let current = 1;
    let leftChild = getLeft(current);
    let rightChild = getRight(current);    

    while (this.canSwap(current, leftChild, rightChild)) {   
      if (this.exists(leftChild) && this.exists(rightChild)) {
        if (this.getAbsHeapValue(leftChild) > this.getAbsHeapValue(rightChild)) {
          this.swap(current, leftChild);
          current = leftChild;
        } else {
          this.swap(current, rightChild);
          current = rightChild;
        }
      } else {
        this.swap(current, leftChild);
        current = leftChild;
      }

      leftChild = getLeft(current);
      rightChild = getRight(current);
    }    
  }

  exists(index) {
    return index <= this.size;
  }

  canSwap(current, left, right) {
    return (this.exists(left) && this.getAbsHeapValue(current) < this.getAbsHeapValue(left) || this.exists(right) && this.getAbsHeapValue(current) < this.getAbsHeapValue(right));
  }

  swap(a, b) {
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
  }
}

getParent = current => Math.floor((current / 2));
getLeft = current => current * 2;
getRight = current => current * 2 + 1;

function maxProductFinderK(numbers, size) {
  let maxHeap = new MaxHeap();
  for (let i=0; i < numbers.length; i++) {
    maxHeap.add(numbers[i]);
  }

  let maxNumbers = [];
  while (maxNumbers.length < size) {
    maxNumbers.push(maxHeap.popMax());
  }

  let numberOfNegatives = maxNumbers.filter(x => x < 0).length;
  console.log(`${maxNumbers} has ${numberOfNegatives} negatives`);
  while (numberOfNegatives % 2 !== 0 && maxHeap.size > 0) {
  
    maxNumbers = maxNumbers.sort((a,b) => b-a);
    
    let newNumber = maxHeap.popMax(); 
    let replaced = maxNumbers.pop();
    maxNumbers.push(newNumber);
    console.log(`replacing ${replaced} by ${newNumber}`);      
    numberOfNegatives = maxNumbers.filter(x => x < 0).length;   
  }

  let product = maxNumbers.reduce((partialProduct, a) => partialProduct * a, 1);

  return product;
}

console.log(maxProductFinderK([-9, -5, -6, -3], 3));

// Leave this so we can test your code:
module.exports = maxProductFinderK;

Wow, looking through this solutions, it seems mine is not the most complicated. In fact, I might have one of the shortest. My algorythm is quite easy. I take the absolut value of every number and multiply from the highest to the lowest, until if I have multiplied the amount of factors in question. If the value is positive, I have the solution, if it is negative, there are three possible cases:

  1. all numbers are negative → so i multiply the numbers with the smallest absolute value instead of the highest
  2. (+3.) I swap the last negative number with the next positive number or vice versa. if there is at least one positive value the solution should be always positive.

Long story short, here is the solution:

function maxProductFinderK(numbers, size) {
    // Write your code here
    let numbersPositive;
    let factorsCount = 0;
    let symbol = 1;
    let maxProduct = 1;
    let lastMinusKey = 0;
    let plusCount = 0;
    let lastPlusKey = 0;

    if (numbers.length === size) {
        return numbers.reduce((sum, current) => sum *= current, 1)
    };

    numbersPositive = numbers.reduce((all, current) => { all.set((current < 0) ? current * -1 : current, (current < 0) ? "-" : "+"); plusCount = (current > 0) ? plusCount + 1 : plusCount; return all; }, new Map());
    numbersPositive = new Map([...numbersPositive.entries()].sort((a, b) => b[0] - a[0])); //We have now a sorted Map with the number as key and the symbol as value sorted from highest to lowest


    
    /* If the product is negative, we have to calculate the smallest absolute value */
    if (plusCount === 0 && size % 2 === 1) {
        numbersPositive = new Map([...numbersPositive.entries()].sort());
        for (let [key, value] of numbersPositive.entries()) {
            maxProduct *= key;
            if (++factorsCount === size) {
                return maxProduct * -1;
            }
        }
    }

    /* After we have sorted out some special cases, we can apply the real algorythm */ 
    for (let [key, value] of numbersPositive.entries()) {
        if (factorsCount < size) {        
            factorsCount++;
            maxProduct *= key;
            if (value === "-") {
                symbol *= -1;
                lastMinusKey = key;
            } else {
                lastPlusKey = key;
                plusCount--;
            }
            if (factorsCount === size && symbol === -1) {
                if (plusCount > 0) {
                    maxProduct /= lastMinusKey;
                } else {
                    maxProduct /= lastPlusKey;
                }
                continue;
            }
        }

        /*   We have to sort out two more specal cases if we have multiplied 
         *   the amount of numbers in question, but our symbol is negative: 
         *   1. We remove the last negative value and multiply the next positive value instead
         *   2. We remove the last positive value and multiply the next negative value instead
         *    --> In fact, they are the same case but opposites */
        
        if (factorsCount === size && symbol === -1 && (value === "+" || plusCount === 0)) {
            factorsCount++;
            maxProduct *= key;
        }
    }
    return maxProduct;
}


//console.log(maxProductFinderK([-8, 6, -1], 3))
console.log(maxProductFinderK([-1,-2,-3,4], 2))

// Leave this so we can test your code:
module.exports = maxProductFinderK;
1 Like

I did not use Heaps.
My solution works and it is pretty simple. I wrote 1 function and asked it to return the maxProduct. I broke things down into cases where maxProduct is calculated differently.

Because we can presume the numbers.length >= size,

  1. When numbers.length = size, we multiply all numbers to get maxProduct.

  2. Else is when numbers.length > size, there are 3 cases. To see these cases, I split numbers into 2 different arrays: negInts (negative integers) and nonNegInts (non-negative integers). Then, I sorted them into increasing order and decreasing order accordingly so that it’s easy to select the biggest and the smallest.

2.1. We have no negative integer.

2.2. We have only negative integer(s). This leads to 2 cases of whether size is even. If size is even, we get a positive maxProduct by multiplying the smallest negative integers. If else, size is odd, we get a negative maxProduct by multiplying the greatest negative integers.

2.3. We have both negative integer(s) and non-negative integer(s). At this point, I realize that the maxProduct must not be negative; therefore, the amount of negative integers to be used must only be 0 or even. Meaning, if i is the amount of negative integers, i must be from 0 and i += 2. From here, the amount of non-negative integers to be used is from subtracting i from size.

Full solution here
function maxProductFinderK(numbers, size) {
  // Write your code here
  let negInts = numbers.filter(num => num < 0)
  negInts.sort((a, b) => (a - b))
  let nonNegInts = numbers.filter(num => num >= 0)
  nonNegInts.sort((a, b) => (b - a));
  console.log(negInts, nonNegInts)

  let maxProduct = !NaN;

  if (numbers.length === size) {
    for (let i = 0; i < size; i++) {
      maxProduct *= numbers[i]
    }

  } else {
    if (negInts.length === 0) {
      for (let i = 0; i < size; i++) {
        maxProduct *= nonNegInts[i]
      }
    } else if (nonNegInts.length === 0) {
        if (size % 2 === 0) { 
          for (let i = 0; i <  size; i++) {
            maxProduct *= negInts[i]
          }
        } else { //maxProduct is a negative interger
          for (let i = 0; i < size; i++) {
            maxProduct *= negInts[negInts.length - 1 - i];
          } 
        }
      } else if (negInts.length > 0 && nonNegInts.length > 0) {
        for (let i = 0; i < size + 1 && i < negInts.length + 1; i += 2) { //Only 0 amount or even amounts of negInts can be used to make a positive product, p.
            let p = 1;       

            if (i === 0) { //Only use nonNegInts
              for (let k = 0; k < size; k++) {
                p *= nonNegInts[k]
              }
            } else {
              for (let j = 0; j < i; j++) {
                      p *= negInts[j];
              }
              for (let k = 0; k < size - i; k++) {
                    p *= nonNegInts[k];
              }
            }
          if (p > maxProduct) {
            maxProduct = p
          } else if (p === 0 && maxProduct === !NaN) {
            maxProduct = p
          }
        }
      }
  }

return maxProduct
}

console.log(maxProductFinderK([-8, 6, -7, 3, 2, 1, -9], 3))

// Leave this so we can test your code:
module.exports = maxProductFinderK;
1 Like

Is there any way to see the tests that are performed? I keep hitting 3 / 5 and i’m running out of edge cases to come up with!

In the spirit of Heaps practice, i’ve implemented my solution creating two heaps:

  • one maxHeap for all the positive values
  • one minHeap for all the negative values

This results in :
posHeap = [ null, 6, 3, 2, 1 ];
negHeap = [ null, -9, -7, -8 ];

The algorithm then compares the root of the both heaps, determines the largest absolute value ( so -9 > 6) , pops this value from the corresponding root and sums this with the product.
Then there is a lot of checking to make sure the final product is positive.

As you can see in the screenshot below, this works quit nicely:
Schermafbeelding 2022-09-20 om 12.36.23

For edge cases, i’ve accounted for:

  • Negative numbers only
  • Positive numbers only
  • Size 1 or 0 as input

I’ve tried a variety of combinations of negative and positive numbers and requested sizes. All get a positive result.
Stll i cannot get past the 3/5 checkmark.
tests

Anyone has a suggestion in what direction to look to pass test 4 & 5?
Or is this just a matter of time / complexity implementation to pass the test?

Full code below in the editor.
There are a lot commented out console.log statements, used for debugging each step.

Hope you can help me out !

function maxProductFinderK(numbers, size) { // Write your code here let posHeap = new maxHeap(); let negHeap = new minHeap(); for (let n of numbers) { if (n > 0){ posHeap.add(n) } else { negHeap.add(n) } } console.log(posHeap); console.log(negHeap); let product = 1; //size = 1 if (size === 0){ return 0; } if (size === 1){ maxHeap.size > 0? product = posHeap.popMax(): product = 0; return product; } else //negatives only if (posHeap.size < 1){ let counter = 1; if (size%2 === 0){ while (counter <= size){ product = product * negHeap.popMin(); counter ++ ; } } else { while (counter < size){ product = product*negHeap.popMin(); counter++; } } return product; } else { for (let i = 1; i <= size;i++){ if (negHeap.size < 1 ){ let poppedMax = posHeap.popMax(); console.log('POS only ' + product + '*' +poppedMax); product = product *poppedMax; } else if (posHeap.size === 0){ let poppedNeg = negHeap.popMin(); product = product * poppedNeg; } else { let poppedValue; if (i === size && product > 0){ poppedValue = posHeap.popMax(); } else if (i === size && product < 0){ poppedValue = negHeap.popMin(); } else { if (posHeap.heap[1] > negHeap.heap[1]*-1){ poppedValue = posHeap.popMax() } else if (posHeap.heap[1] < negHeap.heap[1]*-1) { if (i === size-1 && negHeap.size <=1 && product > 0){ poppedValue = posHeap.popMax(); } else { poppedValue = negHeap.popMin(); } } } console.log('multiply ' + product + '*' +poppedValue); product = product * poppedValue; } console.log('iteration '+ i + ': ' + product) console.log(posHeap); console.log(negHeap); } } return product; } class maxHeap { constructor(){ this.heap = [null]; this.size = 0 } popMax(){ if (this.size === 0){ return null } this.swap(1, this.size); const max = this.heap.pop(); this.size--; this.heapify(); return max; } add(value){ this.heap.push(value); this.size++ this.bubbleUp(); } bubbleUp() { let current = this.size; while (current > 1 && this.heap[current] > this.heap[getParent(current)]) { this.swap(current, getParent(current)); current = getParent(current); } } swap(a, b) { [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]]; } exists(index) { return index <= this.size; } canSwap(current, leftChild, rightChild) { // Check that one of the possible swap conditions exists return ( this.exists(leftChild) && this.heap[current] < this.heap[leftChild] || this.exists(rightChild) && this.heap[current] < this.heap[rightChild] ); } heapify() { let current = 1; let leftChild = getLeft(current)-1; let rightChild = getRight(current)-1; // console.log(rightChild); while (this.canSwap(current, leftChild, rightChild)) { // console.log(this.heap[leftChild]); // console.log(this.heap[rightChild]); if (this.exists(leftChild) && this.exists(rightChild)){ // console.log('left + right = true'); if (this.heap[leftChild] > this.heap[rightChild]) { // console.log('swapping curr: ' + this.heap[current] + 'with left: ' + this.heap[leftChild]) this.swap(current, leftChild); current = leftChild; } else if (this.heap[leftChild] < this.heap[rightChild]) { // console.log('swapping curr: ' + this.heap[current] + 'with right: ' + this.heap[rightChild]) this.swap(current, rightChild); current = rightChild; } else { this.swap(current, leftChild); current = leftChild; } } else { this.swap(current, leftChild); console.log('swapping this?') current = leftChild; } leftChild = getLeft(current); rightChild = getRight(current); } } } class minHeap { constructor(){ this.heap = [null]; this.size = 0 } popMin(){ if (this.size === 0){ return null; } this.swap(1, this.size); const min = this.heap.pop(); this.size--; this.heapify(); return min; } add(value){ this.heap.push(value); this.size++ this.bubbleUp(); } bubbleUp(){ let current = this.size; while (current > 1 && this.heap[getParent(current)] > this.heap[current]){ this.swap(current, getParent(current)); current = getParent(current); } } swap(a, b) { [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]]; } exists(index) { return index <= this.size; } canSwap(current, leftChild, rightChild) { // Check that one of the possible swap conditions exists return ( this.exists(leftChild) && this.heap[current] > this.heap[leftChild] || this.exists(rightChild) && this.heap[current] > this.heap[rightChild] ); } heapify() { // console.log('Heapify'); let current = 1; let leftChild = getLeft(current)-1; let rightChild = getRight(current)-1; while (this.canSwap(current, leftChild, rightChild)) { if (this.exists(leftChild) && this.exists(rightChild)){ if (this.heap[leftChild] < this.heap[rightChild]) { this.swap(current, leftChild) current = leftChild; } else if (this.heap[leftChild] > this.heap[rightChild]){ this.swap(current, rightChild); current = rightChild; } else { this.swap(current, leftChild); current = leftChild; } } else { this.swap(current, leftChild); current = leftChild; } leftChild = getLeft(current); rightChild = getRight(current); } } } const getParent = current => Math.floor((current / 2)); const getLeft = current => (current * 2 )+ 1; const getRight = current => (current * 2) + 2; //original = 432 console.log(maxProductFinderK([-8, -6, -7, 3, 2, 1, -9], 3)) // // only positives = 504 // console.log(maxProductFinderK([8, 6, 7, 3, 2, 1, 9], 7)) // // only negatives = 3024 // console.log(maxProductFinderK([-8, -7, -3, -2, -1, -9], 7)) // Leave this so we can test your code: module.exports = maxProductFinderK;

Hi! I have found a broken case:
Try this: maxProductFinderK([ 0, -1, -9, 11], 2);

EDIT: If one of your factors is zero, the maximum product can never be below zero.

1 Like

Thanks for pointing this out! I will try this asap

Variant with recursion.

function maxProductFinderK(numbers, size) {
  let max = -Infinity;
  function getNextFactor(factor, result, excludes) {
    if (factor > size) {
      if (result > max) max = result;
      return;
    }
    for (let i = 0; i < numbers.length; i++) {
      if (excludes.has(i)) continue;
      const excludesNew = new Set(excludes);
      excludesNew.add(i);
      getNextFactor(factor + 1, result * numbers[i], excludesNew);
    }
  }
  getNextFactor(1, 1, new Set());
  return max;
}