Coding

Now you should be ready to write the code for the coin change problem. To represent infinity/inf, you can use a very large number for which you are sure that it is larger than any possible result. For example, I suggest taking inf as the highest denomination/Txhighest. If no combination is possible, then the coinChange function should return -1. You may assume that the input array is sorted, but I would encourage you to sort the array, if necessary.

The code should have a complexity of O(NT * T/coin[0]) as there are N(amount+1) cells in the matrix. For each cell, a minimum is computed from a list of at the most amount/coin[0] items. As the number of comparisons to compute the minimum won't change, even if we increase the number of unique coins, hence we can take amount/coin[0] as a constant, resulting in a time complexity of O(NT).