How do you solve Design an ATM Machine on LeetCode?

Design an ATM Machine (LeetCode #2241) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Greedy algorithms are often optimal for problems involving making change or selecting items based on value.

What is the brute force solution for Design an ATM Machine?

The brute force approach for Design an ATM Machine is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves trying to withdraw the requested amount by checking each denomination one by one, starting from the largest. This method is straightforward but inefficient as it may require multiple iterations to find a valid combination. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Design an ATM Machine?

Design an ATM Machine uses the following concepts: Array, Greedy, Design. The recommended patterns to study are: Greedy, Array.

What are the interview tips for Design an ATM Machine?

Explain your thought process clearly as you work through the problem. Consider edge cases, such as withdrawing an amount greater than the total available. Practice similar problems to become familiar with greedy strategies.

What are common mistakes when solving Design an ATM Machine?

Not checking if the amount is a multiple of 10, leading to invalid withdrawal requests. Failing to account for the total available amount before attempting to withdraw.

#2241

Design an ATM Machine

Medium

ArrayGreedyDesignGreedyArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution leverages a greedy approach, where we prioritize using the largest denominations first. This minimizes the number of banknotes used and ensures that we can meet the withdrawal request efficiently.

⚙️

Algorithm

3 steps

1Step 1: Check if the requested amount can be withdrawn based on the total available banknotes.
2Step 2: For each denomination from largest to smallest, calculate how many banknotes can be used without exceeding the amount.
3Step 3: Deduct the used banknotes from the ATM's count and return the result.

solution.py21 lines

1# Full working Python code
2class ATM:
3    def __init__(self):
4        self.banknotes = [0] * 5
5
6    def deposit(self, banknotesCount):
7        for i in range(5):
8            self.banknotes[i] += banknotesCount[i]
9
10    def withdraw(self, amount):
11        if amount % 10 != 0 or sum(b * c for b, c in zip([20, 50, 100, 200, 500], self.banknotes)) < amount:
12            return [-1]
13        result = [0] * 5
14        denominations = [500, 200, 100, 50, 20]
15        for i in range(5):
16            if amount >= denominations[i]:
17                count = min(amount // denominations[i], self.banknotes[i])
18                amount -= count * denominations[i]
19                self.banknotes[i] -= count
20                result[i] += count
21        return result if amount == 0 else [-1]

ℹ

Complexity note: The time complexity is O(n) because we only iterate through the banknotes once to calculate the withdrawal. The space complexity is O(1) as we use a fixed amount of space for the banknotes and results.

1Greedy algorithms are often optimal for problems involving making change or selecting items based on value.
2Always check if the total amount available can satisfy the withdrawal request before processing.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.