322. Coin Change

Problem Statement

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Input: coins = [1,2,5], amount = 11 Output: 3 Explanation: 11 = 5 + 5 + 1
  • 1 <= coins[i] <= 231 - 1
  • 0 <= amount <= 104

Approach

Code

Python | Time: O(amount * len(coins)) | Space: O(amount) | In the worst case scenario, the DP array will store a potential value for every single amount.

Thank you for reading!

In case if you haven’t yet joined my Discord server where I host daily sessions on data structures & algorithms for free, please join via the link shared below.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
John Kim

John Kim

75 Followers

iOS Developer | Full Stack Developer | Software Engineer | LinkedIn: john-kim-developer | GitHub: cloudiosx | Portfolio: cloudiosx.com