In an array of numbers find higest product with specific multiple

Question

The task was given an array of integers, find the maximum product between two numbers from the array, that is a multiple of 3.

</script>
arr = [-9, -11, 4, 6, 9, 7]; 
arr2 = [-11, 4, 6, 7]; 
arr3 = [11, 3, 5]

function findProduct(arr) {
  let maxProduct = 0;

  for(let i = 0; i < arr.length - 1; i++) {
    
    
    for(let j = i + 1; j < arr.length; j++) {
      let product = arr[i] * arr[j]

      if(product % 3 !== 0) continue;
      
      if(product > maxProduct) {
        maxProduct = product
      }
    }
  }

  return maxProduct
}

console.log(findProduct(arr))
console.log(findProduct(arr2))
console.log(findProduct(arr3))
</script>
´´´´

Answer 1

An O(N) time, O(1) extra space algorithm:

1. Traverse the array, keep track of two variables: max_multiple_of_three and min_multiple_of_three
2. Traverse the array, keep track of two variables: largest_number_in_array (which shouldn't have the same index as max_multiple of three) and smallest_number_in_array (which shouldn't have same index as min_multiple_of_three)
3. The answer will be either max_multiple_of_three * largest_number_in_array or min_multiple_of_three * smallest_number_in_array

Example 1:

arr = [-9, -11, 4, 6, 9, 7]

max_multiple_of_three = 9
min_multiple_of_three = -9
largest_number_in_array = 7
smallest_number_in_array = -11

ans = max(-9*-11, 9*7) = 99

Example 2:

arr = [-11, 4, 6, 7]

max_multiple_of_three = 6
min_multiple_of_three = 6
largest_number_in_array = 7
smallest_number_in_array = -11

ans = max(6*-11, 6*7) = 42