I'm looking to learn more about algorithms and how to think like a programmer, by practicing coding problems. I subscribed to the mailinglist of dailycodingproblem.com so I will receive one such problem in my inbox every morning and see if I can solve it before the end of the day. Learn with me!

This problem was asked by Uber.

Problem:


Given an array of integers, return a new array such that each element at index i of the new array is the product of all the numbers in the original array except the one at i.
For example, if our input was [1, 2, 3, 4, 5], the expected output would be [120, 60, 40, 30, 24]. If our input was [3, 2, 1], the expected output would be [2, 3, 6].
Follow-up: what if you can't use division?

My thought process:

  • The "what if you can't use division" follow-up is actually a great nudge in the right direction, because it makes me realize that we can just calculate a variable arrayProduct and divide it by each element we pass over in the array to get to the solution. The higher order function reduce() will come in handy, here
  • Next thought is that this is a great use case for the map() higher order function in Javascript, because it creates a new array with the results of calling a function on each item of the original array.
  • Third thought is that if we can't use division, we're just going to have to loop over the entire array and calculate the product for each position separately.

Time to open up the code editor.

Solutions:

//using division
const arrayProduct = arr.reduce((product, currentValue) => {
  return product *= currentValue
})

let solutionArray = arr.map(i => arrayProduct/i)

As far as a solution without division goes, I only seem to be able to come up with inefficient and time-consuming solutions that look far from elegant.

//without division
function prodOfArrWithoutEl(list, elementIndex){
  let newArray = []
  for (let i = 0; i <= list.length-1; i++){
    if(i !== elementIndex){
      newArray.push(list[i])
    }
  }
  let arrayProduct = newArray.reduce((product, currentValue) => {
    return product *= currentValue
  })
  return arrayProduct
}


function calcSolution(list){
  let solutionArray2 = []
  for (let z = 0; z <= list.length-1; z++){
    let newElement = prodOfArrWithoutEl(list, z)
    solutionArray2.push(newElement)
  }
  console.log(solutionArray2)
  return solutionArray2
}

The time complexity of this solution is O(n2), quadratic time, which means that the number of operations increases exponentially with the number of inputs. So this solution is clearly incredibly inefficient and time-consuming.

Can you think of a better one?