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 Language Help.

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

Need broader help or resources? Head to Language Help and Tips and Resources. If you are wanting feedback or inspiration for a project, check out Projects.

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 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;
2 Likes

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;
}

Finally an approach that passes all tests. Not the best possible runtime, I’m afraid, because it loops through all possible combinations. I really wish I knew what this last mysterious test is that failed on my other attempts.

function maxProductFinderK(numbers, size) {
  if(numbers.length===size) {
    return numbers.reduce((acc,el) => acc * el, 1); }
  else if(!numbers.length || numbers.length<size) {
    return 0;
  }
  
  let product;
  const getProduct = (arr) => arr.reduce((acc,el) => acc * el, 1);
  const getSlice = (indexes, arr) => indexes.map(idx => arr[idx]);

  let currentProduct;
  let indexes = new Array(size).fill(0).map((_,idx)=> idx);
  while(indexes[size-1] < numbers.length-2) {
    indexes = indexes.map(n => n+1);
    currentProduct = getProduct(getSlice(indexes, numbers));
    if(!product || currentProduct > product) product = currentProduct;
  }

  indexes = new Array(size).fill(0).map((_,idx)=> idx);
  let currentIdx = size-1;
  while(currentIdx >= 0) {
    currentProduct = getProduct(getSlice(indexes, numbers));
    if(!product || currentProduct > product) product = currentProduct;
    if(indexes[currentIdx]===numbers.length-(size-currentIdx)) currentIdx--
    indexes[currentIdx]++;
  }
  return product;
}

I gave it another go and eventually found the missing edge case:

Same idea as @gsudi8613629997 but different approach. Much better runtime than my above solution.

function maxProductFinderK(numbers, size) {
  if(!numbers.length || !size || numbers.length < size) return 0;
  // helper functions
  const getProduct = arr => arr && arr.reduce((acc,el) => acc * el, 1);
  const getLargestItem = (arr, sign) => arr.find(n => Math.sign(n)===sign);
  const getSmallestItemIndex = (arr, sign) => arr.lastIndexOf(arr.find(n => Math.sign(n)===sign));

  // sort by item size independant of Math.sign
  numbers.sort((a,b) => Math.abs(b)-Math.abs(a));

  const slice = numbers.slice(0, size);
  const rest = numbers.slice(size);
  let product = getProduct(slice);

  // if product of slice is positive it is the largest possible result
  if(product>0 || numbers.length===size) { return product; }
  else {
    // replace smallest positive item of slice with largest negative item of rest 
    const sliceCopy1 = [...slice];
    const largestNegative = getLargestItem(rest, -1);
    if (largestNegative) {
      sliceCopy1.splice(getSmallestItemIndex(slice, 1), 1, largestNegative);
    }
    
    // replace smallest negative item of slice with largest positive item of rest 
    const sliceCopy2 = [...slice];
    const largestPositive = getLargestItem(rest, 1);
    if (largestPositive) {
      sliceCopy2.splice(getSmallestItemIndex(slice, 1), 1, largestPositive);
    }

    product = Math.max(product, getProduct(sliceCopy1), getProduct(sliceCopy2));

    // if product is still negative
    if(product < 0) {
      product = getProduct(numbers.slice(numbers.length - size))
    }
    
  }

  return product;
}

Here is my solution. I didn’t use heaps at all though.
const maxProductFinderK = (list, k)=> {
mappedObj = {};
absList = list.map((num) => {
return num >= 0 ? num : num * -1;
})
for (let i = 0; i < list.length; i++) {
mappedObj[i] = {
real: list[i],
abs: absList[i]
}
}

let mappedList = Object.entries(mappedObj);
mappedList.sort((a,b) => b[1].abs - a[1].abs);
mappedList = mappedList.map(item => {
    return item[1].real;
});
mappedPositives = mappedList.filter(item => item >= 0);
mappedNegatives = mappedList.filter(item => item < 0);
let prodList = []

for (let i = 0; i < k; i++) {
    prodList.push(mappedList[i]);
    
}
prod = prodList.reduce((a,b) => a*b);


if (prod > 0) {
    return prod;
}  else if (list.every((num) => num < 0)) {
    negProdList = mappedList.slice(list.length - k);
    return negProdList.reduce((a,b) => a*b);

}
else {
        posProd = mappedPositives.reduce((a,b) => a*b)
        let maxNegative = Math.max(...prodList.filter((num) => num < 0));
        let maxNegativeIndex = prodList.indexOf(maxNegative);
        let prodListWithoutMaxNegative = [...prodList.slice(0, maxNegativeIndex), ...prodList.slice(maxNegativeIndex + 1)];
        
        let i = k-1;
        do {
            i += 1;
            
          } while ( mappedList[i] < 0);
          prodListWithoutMaxNegative = [...prodListWithoutMaxNegative, mappedList[i]];
          let smallProd = prodListWithoutMaxNegative.reduce((a,b) => a*b);
          const result = smallProd >= posProd ? smallProd : posProd;
          return result;
        
    
    
}

}

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

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

Not very elegant, but works :smiley:
Passed 5/5.

function maxProductFinderK(numbers, k) {
	numbers.sort((a, b) => Math.abs(b) - Math.abs(a));
	let product = [];
	let totalPositives = 0;
	let totalNegatives = 0;
	for (let i = 0; i < k; i++) {
		const numberAtIndex = numbers[i];
		numberAtIndex >= 0 ? totalPositives++ : totalNegatives++;
		product.push(numberAtIndex);
	}
	if (totalNegatives % 2 !== 0) {
		const indexOfNegative = product.findLastIndex(item => (item < 0 ? true : false));
		const indexOfPositive = product.findLastIndex(item => (item > 0 ? true : false));
		const posNumberIndex = numbers.findIndex((item, i) => (i >= k && item >= 0 ? true : false));
		const negNumberIndex = numbers.findIndex((item, i) => (i >= k && item < 0 ? true : false));

		if (totalPositives === 0) {
			// in product are only negative numbers [(--) / (-- or -+ or ++)]
			if (posNumberIndex < 0) {
				// numbers -> has no positives [(--) / (--)]
				let arr = [];
				for (let i = numbers.length - 1; i >= numbers.length - k; i--) {
					arr.push(numbers[i]);
				}
				product = arr;
			} else {
				// numbers -> has positives [(--) / (-+ or ++)]
				product.splice(indexOfNegative, 1, numbers[posNumberIndex]);
			}
		} else {
			// [(-+) / (-- or -+ or ++)]
			if (posNumberIndex < 0 && negNumberIndex >= 0) {
				// numbers -> has no positives but are negatives [(-+) / (--)]
				product.splice(indexOfPositive, 1, numbers[negNumberIndex]);
			} else if (negNumberIndex < 0 && posNumberIndex >= 0) {
				// numbers -> has no negatives but are positives [(-+) / (++)]
				product.splice(indexOfNegative, 1, numbers[posNumberIndex]);
			} else if (negNumberIndex >= 0 && posNumberIndex >= 0) {
				// numbers -> has both negatives and positives [(-+) / (-+)]
				let negativesProduct = product[indexOfNegative] * numbers[negNumberIndex];
				let positivesProduct = product[indexOfPositive] * numbers[posNumberIndex];
				if (negativesProduct > positivesProduct) {
					product.splice(indexOfPositive, 1, numbers[negNumberIndex]);
				} else {
					product.splice(indexOfNegative, 1, numbers[posNumberIndex]);
				}
			}
		}
	}

	return product.reduce((a, b) => a * b, 1);
}

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

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

This solution passed all 5 tests. Any suggestion of additional edge cases are appreciated.

The logic behind this solution is if we calculate the product of the largest n absolute values, then either we already have the max product (when it’s +ve or 0), or the product can be maximised by swapping one of its constituent integers with one in the remaining list. There are only two ways to optimised a negative product:

  1. swap the last -ve for the next +ve
  2. swap the last +ve for the next -ve

All there is left to do is compare and return the max product.

const maxProductFinderK = (numbers, n) => {
  
  // ||----- Setup
  // Sort absolute value of numbers in descending order
  numbers.sort((a, b) => Math.abs(b) - Math.abs(a));
  const head = numbers.slice(0, n);
  const tail = numbers.slice(n);
  // Product of first n elements in sorted array
  const prodN = head.reduce((acc, cur) => acc*cur, 1);
  
  
  // ||----- Simple case: prodN is already optimal if it's +ve or 0
  if(prodN >= 0) return prodN;
  
  
  // ||----- All other cases: prodN is -ve
  // Determine if prodN can be optimised by looking at all swap possibilities
  const nextNegative = tail.find(num => num < 0);
  const nextPositive = tail.find(num => num >= 0);
  const lastNegative = head.reverse().find(num => num < 0);
  const lastPositive = head.reverse().find(num => num >= 0);
  
  // Edge case: all -ve && n odd, then we look for the smallest absolute value
  if (lastNegative && nextNegative && !lastPositive && !nextPositive) {
    return numbers.slice(numbers.length - n).reduce((acc, cur) => acc*cur, 1);
  }
  
  // Two possible actions to optimise prodN when it is negative
  // Action 1: swap lastNegative for nextPositive
  const prod1 = prodN / lastNegative * nextPositive;
  // Action 2: swap lastPositive for nextNegative
  const prod2 = prodN / lastPositive * nextNegative;
  // prod1 exists implies nextPositive exists, and prod2 => nextNegative
  const prod1Exists = ![NaN, undefined].includes(prod1);
  const prod2Exists = ![NaN, undefined].includes(prod2);
  
  // Case 1: neither prod1 nor prod2 exists implies that prodN is optimal
  if (!prod1Exists && !prod2Exists) return prodN;
  // Case 2: both prod1 and prod2 exist, return the larger product
  if (prod1Exists && prod2Exists) return prod1 > prod2 ? prod1 : prod2;
  // Case 3: whichever one of prod1, prod2 that exists is the optimal product
  return prod1Exists ? prod1 : prod2;
  
}
1 Like

I’m using heaps. MaxHeaps and MinHeaps . But it’s the best if you only work with sorted array for space complexity and time complexity you don’t have to transfer array to 2 heaps.

I found a rule based on the problem of finding the largest product of 2 numbers and the greatest largest of 3 numbers in an array:

  1. The largest product of 2 numbers problem solution is choose Max of (product of 2 lasts number in the stored array) and (product of 2 firsts number int stored array).
    2.The greatest product of 3 numbers problem solution is choose Max of (arr[0]*arr[1]*arr[n-1]) and (arr[n-1]*arr[n-2]*arr[n-3]) with ‘arr’ is a stored array.

Based on that logic:

  • if ‘n’ is even number:
    While size > 0
    Multiply the Result by the Product of (Min1st * Min2nd) and Product of (Max1th*Max2th);
    then size-=2;

  • if ‘n’ is odd number:
    Initially, follow the same steps as when ‘n’ is even until ‘size’ equals 3 Then, the problem transitions to finding the greatest product of 3 numbers.

Here is my code:

const popHeap = (heap, isMaxHeap = true) => { const value = heap[0]; heap[0] = heap[heap.length - 1]; heap.pop(); heapify(heap, 0, isMaxHeap); return value; }; const heapify = (heap, current, isMaxHeap = true) => { let left = current * 2 + 1; let right = left + 1; let iterate = current; if (left < heap.length) { if (isMaxHeap) { iterate = heap[left] > heap[iterate] ? left : iterate; } else { iterate = heap[left] < heap[iterate] ? left : iterate; } } if (right < heap.length) { if (isMaxHeap) { iterate = heap[right] > heap[iterate] ? right : iterate; } else { iterate = heap[right] < heap[iterate] ? right : iterate; } } if (iterate != current) { swap(heap, iterate, current); heapify(heap, iterate, isMaxHeap); } }; const swap = (heap, x, y) => ([heap[x], heap[y]] = [heap[y], heap[x]]); function maxProductFinderK(numbers, size) { // Write your code here if (numbers.length == 1) return numbers[0]; const maxHeap = [...numbers]; const minHeap = [...numbers]; for (let i = Math.floor((numbers.length - 1) / 2); i >= 0; i--) { heapify(maxHeap, i); heapify(minHeap, i, false); } let k = size; let res = 1; if (size % 2 === 0) { let save = 0; while (k > 0) { let memPos = 0; let memNeg = 0; if (save !== 1) { memPos = popHeap(maxHeap) * popHeap(maxHeap); } if (save !== 2) { memNeg = popHeap(minHeap, false) * popHeap(minHeap, false); } if (memPos > memNeg) { res *= memPos; save = 2; } else { res *= memNeg; save = 1; } k -= 2; } } else { let save = 0; let memPos = 0; let memNeg = 0; while (k > 3) { if (save !== 1) { memPos = popHeap(maxHeap) * popHeap(maxHeap); } if (save !== 2) { memNeg = popHeap(minHeap, false) * popHeap(minHeap, false); } if (memPos > memNeg) { res *= memPos; save = 2; max = 0; } else { res *= memNeg; save = 1; } k -= 2; } // k have equal to 3 if (save === 1) { let max = popHeap(maxHeap); const productPos = memPos * max; const productNeg = popHeap(minHeap, false)*popHeap(minHeap, false)*popHeap(minHeap, false); res *= productPos > productNeg ? productPos : productNeg; } else if (save === 2) { let max = popHeap(maxHeap); const productPos = max*popHeap(maxHeap)*popHeap(maxHeap); const productNeg = memNeg*max; res *= productPos > productNeg ? productPos : productNeg; } else { let max = popHeap(maxHeap); let productPos = max*popHeap(maxHeap)*popHeap(maxHeap); let productNeg = popHeap(minHeap, false)*popHeap(minHeap, false)*max; res *= productPos > productNeg ? productPos : productNeg; } } return res; } console.log(maxProductFinderK([-8,-7,-2,10,20], 3)); // Leave this so we can test your code: module.exports = maxProductFinderK;