Lemonade Change Leetcode Solution  


Difficulty Level Easy
Frequently asked in Amazon Atlassian
algorithms coding Greedy Interview interviewprep LeetCode LeetCodeSolutions

This post is on Lemonade Change Leetcode Solution

Problem statement  

In the problem ” Lemonade Change” there is a queue of customers. They want to buy lemonade from us which costs 5 rupees. The customers can give us 5 rupees, 10 rupees, or 20 rupees. We want to return the correct amount of change to the customers. Initially, we don’t have any change. We need to answer if we can successfully return the correct amount of change to each customer or not.

Example  

 bills = [5,5,5,10,20]
true

Explanation:

Lemonade Change Leetcode SolutionPin

In the starting three transactions, we need not give any change. After three transactions we have three coins of 5 rupees. During the fourth transaction, we need to return 5 rupees. So after the fourth transaction, we have 2 coins of 5 rupees and one coin of 10 rupees. In the fifth transaction, we need to return 15 rupees. We can return one ten rupees coin and one five rupees coin. As all the transactions are completed so answer is true.

Approach  

This is an implementation problem using a greedy algorithm. As the values given in the array represent a queue of customers so when we will traverse the array at the same time we will be also doing transactions. Initially, we don’t have any change so the number of five, ten, and twenty rupees coins are zero.

See also
Unique Paths II

Let’s look for each of the scenarios one by one:

  1. If the customer pays five rupees then we need not provide any change to him and the number of five rupees coins with us will increase by one.
  2. Let’s say the customer pays ten rupees, then we must have at least one five rupees coin to give him the change. If we fail to do that we will return false as it is not possible to give the correct amount of change to everyone.
  3. If the customer pays twenty rupees then we can give him change in two different ways:
    1. In case we have a ten rupees coin and a five rupees coin then we can return him a total of fifteen rupees. If we fail then we will look for the second method.
    2. As we have to return a total of fifteen rupees so, we can give him three coins of five rupees each. For this, we must have at least 3 coins of fives rupees. If we fail to do that we will return false as it is not possible to give the correct amount of change to everyone.

If we provided the correct amount of change to all the customers then we will simply return true.

Code  

C++ code for Lemonade Change Leetcode Solution

#include <bits/stdc++.h> 
using namespace std; 
       bool lemonadeChange(vector<int>& bills) {
        int n=bills.size();
        int five=0,ten=0,twenty=0;
        for(int i=0;i<n;i++)
        {
            if(bills[i]==5)five++;
            else if(bills[i]==10)
            {
                ten++;
                if(five>0)five--;
                else return false;
            }   
            else 
            {
               twenty++;
                if(ten>0&&five>0){ten--;five--;}
                else if(five>2)five=five-3;
                else return false;
            }
                
        }
            return true;
    }

int main() 
{ 
 vector<int> arr = {5,5,5,10,20}; 
 cout <<boolalpha;
 cout<<lemonadeChange(arr)<<endl; 
 return 0;
}

 

true

Java code for Lemonade Change Leetcode Solution

import java.util.Arrays; 
public class Tutorialcup {
    public static boolean lemonadeChange(int[] bills) {
                int n=bills.length;
        int five=0,ten=0,twenty=0;
        for(int i=0;i<n;i++)
        {
            if(bills[i]==5)five++;
            else if(bills[i]==10)
            {
                ten++;
                if(five>0)five--;
                else return false;
            }   
            else 
            {
               twenty++;
                if(ten>0&&five>0){ten--;five--;}
                else if(five>2)five=five-3;
                else return false;
            }
                
        }
            return true;
    }
  public static void main(String[] args) {
    int [] arr = {5,5,5,10,20}; 
    boolean ans= lemonadeChange(arr);
    System.out.println(ans);
  }
true

Complexity Analysis of Lemonade Change Leetcode Solution  

Time complexity

The time complexity of the above code is O(n) because we are traversing the bills array only once. Here n is the length of the bills array.

See also
Leetcode Permutations

Space complexity

The space complexity of the above code is O(1) because we are using only a variable to store answers.

References