Coin Change Problem with Memoization

Question

Purpose

Another take on the classic Change-making Problem:

Given some set of coins and a value, find the minimum number of coins necessary to add up to this value

In my implementation, instead of returning the number of coins, I'm returning a Map of the coin values and their counts.

For example, given the coin values [1, 5], we'd expect my implementation to return {1: 2, 5: 1} for an input of 7.

Implementation Details

I decided to memoize results from previous calculations so as to not redo the same work over and over again. The idea here is that if an input value is greater than the size of the cache, we can use the cache to identify all values between the current size of the cache and the input value itself.

For example, the initial cache size is 1 (index 0 is mapped to an empty HashMap). Let's say, I call calculateMinimumCoinChange with 7. Since the input value (7) is greater than the size of the cache (1), empty HashMaps are mapped to index values 1 to 7, inclusive.

Then, starting from the previous size index (1), I use the cache values to calculate the coin change counts for index values 1 through 7. Thus, the cache should now contain coin change counts from 0 through 7.

So if I look up the coin change counts for 5, I can just lookup the value in the cache. If I look up the coin change counts for 10, I would expand my cache and use the coin change counts from 0 through 7 to inform my counts for 8 through 10.

There are a few things about my implementation that give me pause.

1. I think it makes sense for the CoinChangeCalculator to take a Set of Integer coin values as an instance variable. But does it make sense to check this Set for nulls or negative values in the constructor? Again, I think it does (obviously) but I'm open to alternative suggestions.
2. Is there a better way to implement my memoization?
3. I had a really tough time with naming, especially when talking about counts, so open to alternative naming suggestions.

Implementation

package problems.impl;

import java.util.*;

public class CoinChangeCalculator {
    private final Set<Integer> coinValues;
    private final List<Map<Integer, Integer>> coinChangeCounts;

    public CoinChangeCalculator(Set<Integer> coinValues) {
        for (Integer coinValue : coinValues) {
            if (coinValue == null || coinValue < 0) {
                throw new IllegalArgumentException(String.format("Invalid coin value: {} ", coinValue));
            }
        }

        this.coinValues = coinValues;
        this.coinChangeCounts = new ArrayList<>();
        this.coinChangeCounts.add(0, new HashMap<>());
    }

    public Map<Integer, Integer> calculateMinimumCoinChange(int value) {
        if (value > this.coinChangeCounts.size()) {
            int previousSize = this.coinChangeCounts.size();

            for (int index = previousSize; index <= value; index++) {
                this.coinChangeCounts.add(index, new HashMap<>());
            }

            for (int subValue = previousSize; subValue <= value; subValue++) {
                for (Integer coinValue : this.coinValues) {
                    int previousValue = subValue - coinValue;
                    if (previousValue >= 0) {
                        Map<Integer, Integer> previousValueChangeChange = coinChangeCounts.get(previousValue);
                        Map<Integer, Integer> subValueChangeCounts = coinChangeCounts.get(subValue);

                        int previousCoinCounts = previousValueChangeChange.values().stream()
                                .filter((counts) -> counts != null)
                                .mapToInt(Number::intValue)
                                .sum();
                        int subValueCoinCounts = subValueChangeCounts.values().stream()
                                .filter((counts) -> counts != null)
                                .mapToInt(Number::intValue)
                                .sum();

                        if (subValueChangeCounts.isEmpty() || previousCoinCounts + 1 < subValueCoinCounts) {
                            Map<Integer, Integer> updatedChangeCounts = new HashMap<>(previousValueChangeChange);

                            Integer coinValueCount = updatedChangeCounts.get(coinValue);
                            if (coinValueCount == null) {
                                updatedChangeCounts.put(coinValue, 1);
                            } else {
                                updatedChangeCounts.put(coinValue, coinValueCount + 1);
                            }

                            coinChangeCounts.set(subValue, updatedChangeCounts);
                        }
                    }
                }
            }
        }

        return coinChangeCounts.get(value);
    }
}

Answer 1

Overall, I think your code is clear, well structured and easy to follow, and the variable names are informative. However, I found some flaws with it, which I will address first.

Correcting (potential) bugs

• If an instance of CoinChangeCalculator is created with the constructor CoinChangeCalculator(Set<Integer>), the created object will not have exclusive control over the field coinValues, because coinValues references the same object that was passed to the constructor, and since a Set is not immutable, something outside the object could modify the Set<Integer> referenced by coinValues, thereby corrupting your object. It would be safer to do this instead:

  public CoinChangeCalculator(Set<Integer> coinValues) {
      // ...
      this.coinValues = new HashSet<>(coinValues);
      // ...
  }
  

  This will copy the Integers from the passed Set into a new HashSet, and since an Integer is immutable, your object is now independent.

• There is a mistake in the first line inside the method calculateMinimumCoinChange(int). The comparison should be:

  if (value >= this.coinChangeCounts.size())
  

  Notice the >= operator instead of >. I assume this was a mistake, because the rest of your code looks like you're aware that the indexes in a List are zero-based.

• One can trick your algorithm into producing an erroneous result by including a coin with a value of 0 in the set of possible coins. If your inner for loop is on this 0-value-coin, then previousValue will equal subValue. However, your code seems to assume that previousValue is always less than subValue and that every element in coinChangeCounts with an index below subValue has a valid coin combination associated with it, so it will rely on coinChangeCounts.get(previousValue) to represent a correct coin combination. But if coinValue == 0, then previousValue == subValue, and coinChangeCounts.get(previousValue) will only contain the empty map you put there in the first for loop of the method, causing your code to fail. To prevent this, you can either disallow 0-value-coins in the first place, or you have to do an additional check when you enter the inner for loop. I would suggest prohibiting them in the first place, because if you do allow them and check if coinValue > 0 when entering the inner for loop, the 0-value-coin will either never appear in a result, not even if you invoke calculateMinimumCoinChange(0), or, if you set coinChangeCounts.get(0) to contain a mapping from 0 to 1 (i.e. one 0-value-coin) in the constructor, then the 0-value-coin will uselessly (and wrongly) appear in every other result as well. So it's probably easier just not to deal with this useless coin and let the constructor handle any attempt to confuse your code into malfunctioning.
• There is another bug in your code: The for loop that introduces int subValue will only update coinChangeCounts for that subValue index if there is at least one coin with a value that is smaller than or equal to subValue. However, if there is no coin with a value of 1, then not all coin combinations contained in coinChangeCounts will be valid for their respective indices. To rectify this problem, it is probably inevitable to use Optionals, or alternatively null values (although I would personally prefer the first, because it is explicit in its intention), to signify that a value has been positively determined to be impossible to construct using the available coins, as opposed to simply not being cached yet. Note that I've caught this bug after I had written most of the "Suggestions" section, so the examples there might not take this bug into account.

Following are some suggestions that are not corrections of mistakes, but possible ways to improve the code or its readability.

Suggestions

• Populating coinChangeCounts with empty HashMaps for all indexes that do not yet contain a valid coin combination up to the queried value creates ambiguity about the contents of coinChangeCounts – it might not only contain a valid coin combination, but also empty HashMaps that don't represent a valid coin combination. This doesn't really help. True, it ensures that coinChangeCounts.get(subValue) returns a value, but what is this guarantee of being returned a value worth if you can't be sure that the returned value is of any use? coinChangeCounts.get(int) might as well not return any value at all if there is no associated coin combination for this index yet. That way, a 0-value-coin would have resulted in an IndexOutOfBoundsException being thrown, which to me seems preferable to a wrong result being presented as an unexceptional outcome. So instead of filling up coinChangeCounts with empty HashMaps, you could do this inside the inner for loop:

  // ...
  if (previousValue >= 0) {
      Map<Integer, Integer> previousValueChangeChange = coinChangeCounts.get(previousValue);
      int previousCoinCounts = previousValueChangeChange.values().stream()
              .filter((counts) -> counts != null)
              .mapToInt(Number::intValue)
              .sum();
  
      OptionalInt subValueCoinCounts;
      if (subValue < coinChangeCounts.size()) {
          subValueCoinCounts = OptionalInt.of(
                  coinChangeCounts
                          .get(subValue)
                          .values()
                          .stream()
                          .filter((counts) -> counts != null)
                          .mapToInt(Number::intValue)
                          .sum());
      } else {
          subValueCoinCounts = OptionalInt.empty();
      }
  
      if (!subValueCoinCounts.isPresent() || previousCoinCounts + 1 < subValueCoinCounts.getAsInt()) {
          // ...
          if (subValue < coinChangeCounts.size()) {
              coinChangeCounts.set(subValue, updatedChangeCounts);
          } else {
              coinChangeCounts.add(subValue, updatedChangeCounts);
              /* if I had used this instead of the one argument version
                 add(int) in the first place, I probably would have caught
                 the no-1-value-coin-bug sooner */
          }
      }
  }
  

  Thus, the contract of coinChangeCounts can be that, for every index at which it contains an element, this element must be a valid coin combination for that index, which to me seems more practical than if an element could also be an empty map, because, as you have seen with the 0-value-coin, a bug can cause an empty map to be falsely interpreted as a valid coin combination.

• About the null checks in your code. You ask whether it makes sense to inspect the passed Set<Integer> for potential nulls. In my opinion, it definitely does make sense. Catching unwanted null values trying to intrude into your methods/objects as early as possible can only be a good thing, because they can, at best, only cause just as much damage later on, if not more. I don't think it's different from checking if all integers are greater than (or equal to) zero. If the type of the parameter doesn't imply all the necessary conditions for it, then you have to check manually. The only alternative would be to create a custom implementation of Set that only accepts non-null and non-negative Integers, and I doubt the benefits of such an approach would outweigh its impracticality.

  On the other hand, I think that null-checking when streaming over the values of coinChangeCounts.get(previousValue) and coinChangeCounts.get(subValue) is unnecessary, because coinChangeCounts is a private field and only you have control over its contents. And if you don't trust yourself and want to protect yourself from inadvertently putting a null value into one of the Maps in coinChangeCounts, you can always use assertions:

  assert coinChangeCounts
          .get(previousValue)
          .values()
          .stream()
          .noneMatch(integer -> integer == null);
  

  In your case, mapToInt(Number::intValue) would throw a NullPointerException anyway if it encountered a null element, but this doesn't mean you can't explicitly check for nulls if that is your intention (by the way, why don't you use Integer::intValue instead of Number::intValue? It doesn't make a difference in the end, but I find it a bit odd). Also, filtering out null elements would imply that a coin combination with a null value instead of a coin count is valid, so you're effectively passing up an opportunity to detect a bug in your program.