Starting from the End: Solving “Product Except Self”

Jun 2

Today we continue our series exploring LeetCode problems and comparing Haskell and Rust solutions. We’re staying in the realm of list/vector manipulation, but the problems are going to start getting more challenging!

If you want to learn more about problem solving in Haskell, you should take a closer look at Solve.hs! You’ll particularly learn how to translate common ideas from loop-based into Haskell’s recursive ideas!

The Problem

Today’s problem is Product of Array Except Self. The idea is that we are given a vector of n integers. We are supposed to return another vector of n integers, where output[i] is equivalent to the product of all the input integers except for input[i].

The key constraint here is that we are not allowed to use division. If we could use division, the answer would be simple! We would find the product of the input numbers and then divide this product by each input number to find the corresponding value. But division is more expensive than most other numeric operations, so we want to avoid it if possible!

The Algorithm

The approach we’ll use in this article relies on “prefix products” and “suffix products”. We’ll make two separate vectors called prefixes and suffixes, where prefixes[i] is the product of all numbers strictly before index i, and suffixes[i] is the product of all numbers strictly after index i.

Then, we can easily produce our results. The value output[i] is simply the product of prefixes[i] and suffixes[i].

As an example, our input might be [3, 4, 5]. The prefixes vector should be [1, 3, 12], and the suffixes vector should be [20, 5, 1]. Then our final output should be [20, 15, 12].

prefixes: [1, 3, 12]
suffixes: [20, 5, 1]
output: [20, 15, 12]

Rust Solution

Here’s our Rust solution:

impl Solution {
    pub fn product_except_self(nums: Vec<i32>) -> Vec<i32> {
        let n = nums.len();
        let mut prefixes = vec![0; n];
        let mut suffixes = vec![0; n];
        let mut totalPrefix = 1;
        let mut totalSuffix = 1;

        // Loop 1: Populate prefixes & suffixes
        for i in 0..n {
            prefixes[i] = totalPrefix;
            totalPrefix *= nums[i];
            suffixes[n - i - 1] = totalSuffix;
            totalSuffix *= nums[n - i - 1];
        }

        let mut results = vec![0; n];

        // Loop 2: Populate results
        for i in 0..n {
            results[i] = prefixes[i] * suffixes[i];
        }
        return results;
    }
}

The two for-loops provide this solution with its shape. The first loop generates our vectors prefixes and suffixes. We keep track of a running tally of the totalPrefix and the totalSuffix. Each of these is initially 1.

let n = nums.len();
let mut prefixes = vec![0; n];
let mut suffixes = vec![0; n];
let mut totalPrefix = 1;
let mut totalSuffix = 1;

On each iteration, we assign the current “total prefix” to the prefixes vector in the front index i, and then the “total suffix” to the suffixes vector in the back index n - i - 1. Then we multiply each total value by the input value (nums) from that index so it’s ready for the next iteration.

// Loop 1: Populate prefixes & suffixes
for i in 0..n {
    prefixes[i] = totalPrefix;
    totalPrefix *= nums[i];
    suffixes[n - i - 1] = totalSuffix;
    totalSuffix *= nums[n - i - 1];
}

And now we calculate the result, by taking the product of prefixes and suffixes at each index.

let mut results = vec![0; n];

// Loop 2: Populate results
for i in 0..n {
    results[i] = prefixes[i] * suffixes[i];
}
return results;

Haskell Solution

In Haskell, we can follow this same template. However, a couple differences stand out. First, we don’t use for-loops. We have to use recursion or recursive helpers to accomplish these loops. Second, when constructing prefixes and suffixes, we want to use lists instead of modifying mutable vectors.

When performing recursion and accumulating linked lists, it can be tricky to reason about which lists need to be reversed at which points in our algorithm. For this reason, it’s often very helpful in Haskell to start from the end of our algorithm.

Let’s write out a template of our solution that leaves prefixes and suffixes as undefined stubs. Then the first step we’ll work through is how to get the solution from that:

productOfArrayExceptSelf :: V.Vector Int -> V.Vector Int
productOfArrayExceptSelf inputs = solution ???
  where
    n = V.length inputs

    solution :: ??? -> V.Vector Int

    prefixes :: [Int]
    prefixes = undefined

    suffixes :: [Int]
    suffixes = undefined

So given prefixes and suffixes, how do we find our solution? The ideal case is that both these lists are already in reverse-index order with respect to the input vector (i.e. n - 1 to 0). Then we don’t need to do an additional reverse to get our solution.

We can then implement solution as a simple tail recursive helper function that peels one element off each input and multiplies them together. When we’re out of inputs, it returns its result:

productOfArrayExceptSelf :: V.Vector Int -> V.Vector Int
productOfArrayExceptSelf inputs = solution (prefixes, suffixes, [])
  where
    n = V.length inputs

    -- Loop 2: Populate Results
    solution :: ([Int], [Int], [Int]) -> V.Vector Int
    solution ([], [], acc) = V.fromList acc
    solution (p : ps, s : ss, acc) = solution (ps, ss, p * s : acc)
    solution _ = error “Prefixes and suffixes must be the same size!”

    prefixes :: [Int]

    suffixes :: [Int]

So now we’ve done “Loop 2” already, and we just have to implement “Loop 1” so that it produces the right results. Again, we’ll make a tail recursive helper, and this will produce both prefixes and suffixes at once. It will take the index, as well as the “total” prefix and suffix so far, and then two accumulator lists. At the end of this, we want both lists in reverse index order.

productOfArrayExceptSelf :: V.Vector Int -> V.Vector Int
productOfArrayExceptSelf inputs = solution (prefixes, suffixes, [])
  where
    n = V.length inputs

    -- Loop 2: Populate Results
    solution :: ([Int], [Int], [Int]) -> V.Vector Int

    prefixes :: [Int]
    suffixes :: [Int]
    (prefixes, suffixes) = mkPrefixSuffix (0, 1, [], 1, [])

    -- Loop 1: Populate prefixes & suffixes
    mkPrefixSuffix :: (Int, Int, [Int], Int, [Int]) -> ([Int], [Int])
    mkPrefixSuffix (i, totalPre, pres, totalSuff, suffs) = undefined

Now we fill in mkPrefixSuffix as we would any tail recursive helper. First we satisfy the base case. This occurs once i is at least n. We’ll return the accumulated lists.

mkPrefixSuffix :: (Int, Int, [Int], Int, [Int]) -> ([Int], [Int])
mkPrefixSuffix (i, totalPre, pres, totalSuff, suffs) = if i >= n then (pres, reverse suffs)
  else ...

But observe we’ll need to reverse suffixes! This becomes clear when we map out what each iteration of the loop looks like for a simple input. Doing this kind of “loop tracking” is a very helpful problem solving skill for walking through your code!

input = [3, 4, 5]
i = 0: (0, 1, [], 1, [])
i = 1: (1, 3, [1], 5, [1])
i = 2: (2, 12, [3, 1], 20, [5, 1])
i = 3: (3, 60, [12, 3, 1], 60, [20, 5, 1])

Our prefixes are [12, 3, 1], which is properly reversed, but the suffixes are [20, 5, 1]. We don’t want both lists ending in 1! So we reverse the suffixes.

Now that we’ve figured this out, it’s simple enough to fill in the recursive case using what we already know from “Loop 1” in the Rust solution. We get the “front” index of input with i, and the “back” index with n - i - 1, use these to get the new products, and then save the old products in our list.

mkPrefixSuffix :: (Int, Int, [Int], Int, [Int]) -> ([Int], [Int])
mkPrefixSuffix (i, totalPre, pres, totalSuff, suffs) = if i >= n then (pres, reverse suffs)
  else
    let nextPre = nums V.! i
        nextSuff = nums V.! (n - i - 1)
    in mkPrefixSuffix (i + 1, totalPre * nextPre, totalPre : pres, totalSuff * nextSuff, totalSuff : suffs)

Here’s our complete Haskell solution!

productOfArrayExceptSelf :: V.Vector Int -> V.Vector Int
productOfArrayExceptSelf inputs = solution (prefixes, suffixes, [])
  where
    n = V.length inputs

    solution :: ([Int], [Int], [Int]) -> V.Vector Int
    solution ([], [], acc) = V.fromList acc
    solution (p : ps, s : ss, acc) = solution (ps, ss, p * s : acc)
    solution _ = error "Invalid solution!"

    prefixes :: [Int]
    suffixes :: [Int]
    (prefixes, suffixes) = mkPrefixSuffix (0, 1, [], 1, [])


    mkPrefixSuffix:: (Int, Int, [Int], Int, [Int]) -> ([Int], [Int])
    mkPrefixSuffix (i, totalPre, pres, totalSuff, suffs) = if i >= n then (pres, reverse suffs)
      else
        let nextPre = inputs V.! i
            nextSuff = inputs V.! (n - i - 1)
        in  mkPrefixSuffix (i + 1, totalPre * nextPre, totalPre : pres, totalSuff * nextSuff, totalSuff : suffs)

Conclusion

In this comparison, we saw a couple important differences in problem solving with a loop-based language like Rust compared to Haskell.

For-loops have to become recursion in Haskell
We want to use lists in Haskell, not mutable vectors
It takes a bit of planning to figure out when to reverse lists!

This led us to a couple important insights when solving problems in Haskell.

“Starting from the end” can be very helpful in plotting out our solution
“Loop tracking” is a very helpful skill to guide our solutions

For an in-depth look at these sorts of comparisons, check out our Solve.hs course. You’ll learn all the most important tips and tricks for solving coding problems in Haskell! In particular you’ll get an in-depth look at tail recursion, a vital concept for solving problems in Haskell.

James Bowen