Getting Greedy

An In-Depth Look into the Greedy Algorithm

A greedy algorithm is an algorithm which forms a solution by choosing the best looking option at every step. For example, when assigning coins as change for 87 cents. We select the highest coin denomination if it fits into 87 cents, subtract it from the total, and iterate over again. Each time the highest coin that can fit into the running total is selected. That’s the basis of the greedy algorithm.

We have to be wary, as sometimes the greedy algorithm doesn’t provide the most optimal solution. If you were trying to fit as much luggage into an airplane without going over a specified carrying capacity, the greedy algorithm wouldn’t neccessarily provide an optimal solution.

Given an array of integers, return an array of integers that are the product of all other numbers in the array besides the number at each index. For example, [2, 3, 4] => [12, 8, 6]. No division allowed.

It’s important to ask yourself what you need at each iteration and what you need to keep track of. In this case, we would need to keep a seperate array with the solution.

See the full solution below or check out InterviewCake.com .

Solution

V

V

V

function getProductsOfAllIntsExceptAtIndex(intArray) {
  if (intArray.length < 2) {
    throw new Error('Getting the product of numbers at other indices requires at least 2 numbers');
  }