1
\$\begingroup\$

Input consists of 2 lists

Products: [[20, 'discount1', 'discount2']], [15, 'discount2'], [10, 'NONE', 'discount1']]

Discounts: [['discount1', 1, 30], ['discount2', 2, 5.5]]

= = =

Each product list consist of [product-price, discount-name, discount-name, ....]

Each discount list consist of [discount-name, discount-type, discount-amount]

= = = =

Discount-type 1: Take the discount amount as percentage and subtract it from product price

Discount-type 2: Take the discount amount as discount price and subtract it from product price

= = =

The goal is to determine optimal price for each product and sum it to total price. As each optimal price is calculated, I round it to the nearest integer.

Ex: (using the above 2 lists)

Take product 1, which is $20. Apply 'discount1'. 'discount1' is type 1 so do the following 20 - 20(.30) = 14 -> Math.round(14) = 14

Now apply 'discount2'. 'discount2' is type 2 so do the following 20 - 5.5 = 14.5 -> Math.round(14.5) = 15

Since 14 < 15, I take 14 as the optimal price for product 1 and add it to a finalPrice variable. I do this for the rest of the products

public class Solution {
        static class DisHelper {
        int type;
        double d;
        DisHelper(int type, double d) {
            this.type=type;
            this.d=d;
        }
    }
    public static int Price(List<List<String>> products, List<List<String>> discounts) {
        int finalPrice=0;
        
        HashMap<String, DisHelper> map = new HashMap<>();
        for(List<String> list: discounts) {
            map.put(list.get(0), new DisHelper(Integer.parseInt(list.get(1)), Double.parseDouble(list.get(2))));
        }
        
        for(List<String> list: products) {
            double originalPrice = Double.parseDouble(list.get(0));
            double optimalPrice = originalPrice;
            for(int i=1;i<list.size();i++) {
                if(list.get(i).equals("NONE")) {
                    continue;
                }
                double price1=originalPrice;
                DisHelper subDisObj = map.get(list.get(i));
                if(subDisObj.type==1) {
                    price1=Math.round(price1-(price1*(subDisObj.d/(double)100)));
                } else if(subDisObj.type==2) {
                    price1=Math.round(price1-subDisObj.d);
                }
                optimalPrice=Math.min(optimalPrice, price1);

            }

            finalPrice+=(int)optimalPrice;
        }
        return finalPrice;
    }

    public static void main(String[] args) {

        List<List<String>> products = new ArrayList<>();
        List<List<String>> discounts = new ArrayList<>();
        products.add(new ArrayList<>(List.of("20", "discount1", "discount2")));
        products.add(new ArrayList<>(List.of("15", "discount2")));
        products.add(new ArrayList<>(List.of("10", "NONE", "discount1")));
        discounts.add(new ArrayList<>(List.of("discount1", "1", "30")));
        discounts.add(new ArrayList<>(List.of("discount2", "2", "5.5")));
        System.out.println(Price(products, discounts));

    }
}

Analysis Say we have M products, N discounts, and k discount names for each product.

Populating HashMap: O(N)

Going through each product: O(M)

Going through each discount (for each product) O(M * k)

Time complexity: O(max(N, M * k))

Space Complexity: O(N) for Hashmap.

Are the time and space complexities correct?

Can I optimize this code?

\$\endgroup\$

2 Answers 2

1
\$\begingroup\$

The mess you are in

Below are the initial comments. Mostly naming, but I also added code explanation comments for the purpose of the next part of refactoring. You seem to mix different levels of abstraction in a single line. For example when you iterate over the list of products, each item in the list is a product, not a "list" just because a product is represented as a list.

Also notice, that your method has multiple levels of indentation. This is a sign, that the method does more than it says it does. Each explanation comment is basically saying what the method does.

...
    // Minor naming: Seems like Discount would be more appropriate
    static class DisHelper {
        int type;
        // Major naming: why not amount?
        double d;
        DisHelper(int type, double d) {
            this.type=type;
            this.d=d;
        }
    }

    // Minor naming: method names should be in camel case
    // Minor naming: method does not really say what it does (there is no verb in the name and it isn't a getter either)
    public static int Price(List<List<String>> products, List<List<String>> discounts) {
        int finalPrice=0;

        // Major naming: discountMap instead of map
        // Explanation: this block builds the map out of discount list
        HashMap<String, DisHelper> map = new HashMap<>();
        // Major naming: why list? discount would be a better name
        for(List<String> list: discounts) {
            map.put(list.get(0), new DisHelper(Integer.parseInt(list.get(1)), Double.parseDouble(list.get(2))));
        }

        // Explanation: this block sums the total price
        // Major naming: same as above: list is not a good name
        for(List<String> list: products) {
            double originalPrice = Double.parseDouble(list.get(0));
            double optimalPrice = originalPrice;

            // Explanation: this block calculates the optimal price
            for(int i=1;i<list.size();i++) {
                if(list.get(i).equals("NONE")) {
                    continue;
                }

                // Explanation: this block calculates the price with discount
                // Minor naming: priceWithDiscount
                double price1=originalPrice;
                // Minor naming: discount
                DisHelper subDisObj = map.get(list.get(i));
                if(subDisObj.type==1) {
                    price1=Math.round(price1-(price1*(subDisObj.d/(double)100)));
                } else if(subDisObj.type==2) {
                    price1=Math.round(price1-subDisObj.d);
                }

                optimalPrice=Math.min(optimalPrice, price1);
            }

            finalPrice+=(int)optimalPrice;
        }
        return finalPrice;
    }
...

Fix the names

Next step is removing the naming comments. And also, we'll make the code breathe (notice the code has more space and is easier to read - full credit to IDE formatting tool, I didn't do this by hand).

    static class Discount {
        int type;
        double amount;

        Discount(int type, double amount) {
            this.type = type;
            this.amount = amount;
        }
    }

    public static int calculateOptimalPrice(List<List<String>> products, List<List<String>> discounts) {
        int finalPrice = 0;

        // Explanation: this block builds the map out of discount list
        HashMap<String, Discount> discountMap = new HashMap<>();
        for (List<String> list : discounts) {
            discountMap.put(list.get(0), new Discount(Integer.parseInt(list.get(1)), Double.parseDouble(list.get(2))));
        }

        // Explanation: this block sums the total price
        for (List<String> product : products) {
            double originalPrice = Double.parseDouble(product.get(0));
            double optimalPrice = originalPrice;

            // Explanation: this block calculates the optimal price
            for (int i = 1; i < product.size(); i++) {
                if (product.get(i).equals("NONE")) {
                    continue;
                }

                // Explanation: this block calculates the price with discount
                double priceWithDiscount = originalPrice;
                Discount discount = discountMap.get(product.get(i));
                if (discount.type == 1) {
                    priceWithDiscount = Math.round(priceWithDiscount - (priceWithDiscount * (discount.amount / (double) 100)));
                } else if (discount.type == 2) {
                    priceWithDiscount = Math.round(priceWithDiscount - discount.amount);
                }

                optimalPrice = Math.min(optimalPrice, priceWithDiscount);
            }

            finalPrice += (int) optimalPrice;
        }
        return finalPrice;
    }

Break things up

Next is converting explanation comments into methods. Make sure that the names are meaningful and explain what the method does.

    public static int calculateOptimalPrice(List<List<String>> products, List<List<String>> discounts) {
        HashMap<String, Discount> discountMap = buildDiscountMap(discounts);
        /*
        If you want to impress friends
        return products.stream()
               .mapToInt(product -> calculateOptimalProductPrice(discountMap, product))
               .sum();
        */
        int finalPrice = 0;

        for (List<String> product : products) {
            finalPrice += calculateOptimalProductPrice(discountMap, product);
        }

        return finalPrice;
    }

    private static int calculateOptimalProductPrice(HashMap<String, Discount> discountMap, List<String> product) {
        double originalPrice = Double.parseDouble(product.get(0));
        double optimalPrice = originalPrice;

        for (int i = 1; i < product.size(); i++) {
            if (product.get(i).equals("NONE")) {
                continue;
            }

            Discount discount = discountMap.get(product.get(i));
            double discountedPrice = calculateDiscountedProductPrice(discount, originalPrice);

            optimalPrice = Math.min(optimalPrice, discountedPrice);
        }

        return (int) optimalPrice;
    }

    // Major OO: you need to pass discount and original price in just to calculate based on type
    // It would be better to move this method into Discount class
    private static double calculateDiscountedProductPrice(Discount discount, double originalPrice) {
        if (discount.type == 1) {
            return Math.round(originalPrice - (originalPrice * (discount.amount / (double) 100)));
        } else if (discount.type == 2) {
            return Math.round(originalPrice - discount.amount);
        } else {
            throw new IllegalArgumentException("Unknown discount type");
        }
    }

    private static HashMap<String, Discount> buildDiscountMap(List<List<String>> discounts) {
        HashMap<String, Discount> discountMap = new HashMap<>();
        for (List<String> discount : discounts) {
            discountMap.put(discount.get(0), new Discount(Integer.parseInt(discount.get(1)), Double.parseDouble(discount.get(2))));
        }
        return discountMap;
    }

Small details make the difference

This is already enough for what this code does, but just for the sake of it, let's refactor to remove the new OO comment.

    private static class Discount {
        private final int type;
        private final double amount;

        Discount(int type, double amount) {
            this.type = type;
            this.amount = amount;
        }

        public double apply(double originalPrice) {
            if (this.type == 1) {
                return Math.round(originalPrice - (originalPrice * (this.amount / (double) 100)));
            } else if (this.type == 2) {
                return Math.round(originalPrice - this.amount);
            } else {
                throw new IllegalArgumentException("Unknown discount type");
            }
        }
    }

    ...
            Discount discount = discountMap.get(product.get(i));
            double discountedPrice = discount.apply(originalPrice);

            optimalPrice = Math.min(optimalPrice, discountedPrice);
    ...

You can never over engineer

Now that the comment is removed, I wonder what would happen if we applied the same concept to the product. Let's make product a class the same way you did with discount.

private static class Product {
        private final int price;
        private final List<Discount> discounts;

        public Product(int price, List<Discount> discounts) {
            this.price = price;
            this.discounts = discounts;
        }

        public int optimalPrice() {
            /*
            To show off
            discounts.stream()
                    .mapToInt(discount -> (int) discount.apply(this.price))
                    .min();
             */

            int price = this.price;

            for (Discount discount : discounts) {
                price = Math.min(price, (int) discount.apply(this.price));
            }

            return price;
        }
    }

    private static List<Product> buildProducts(List<List<String>> productsInput, HashMap<String, Discount> discountMap) {
        return productsInput.stream()
                .map(productInput -> mapInputToProduct(productInput, discountMap))
                .toList();
    }

    private static Product mapInputToProduct(List<String> product, Map<String, Discount> discountMap) {
        int price = Integer.parseInt(product.get(0));
        List<Discount> discounts = new ArrayList<>();

        for (int i = 1; i < product.size(); i++) {
            if (product.get(i).equals("NONE")) {
                continue;
            }

            Discount discount = discountMap.get(product.get(i));
            discounts.add(discount);
        }

        return new Product(price, discounts);
    }

...
        for (Product product : products) {
            finalPrice += product.optimalPrice();
        }
...

As I said, never!

As you can see, building the product (essentialy parsing the input) is the only messy part. It could probably be refactored further, but it is good enough. The important part is that Product is clean.

Looking at what we have now you might say: But what if I add different types of discounts in the future, that will use different criteria to apply the discount. Coding this way you will need to expand the apply method with additional if statements. Let's fix this by making Discount an interface and change how discount input is being parsed.

    interface Discount {
        double apply(double amount);
    }

    private static class PercentageDiscount implements Discount {
        private final double amount;

        public PercentageDiscount(double amount) {
            this.amount = amount;
        }

        @Override
        public double apply(double originalPrice) {
            return Math.round(originalPrice - (originalPrice * (this.amount / (double) 100)));
        }
    }

    private static class PriceDiscount implements Discount {
        private final double amount;

        public PriceDiscount(double amount) {
            this.amount = amount;
        }

        @Override
        public double apply(double originalPrice) {
            return Math.round(originalPrice - this.amount);
        }
    }

...

    private static HashMap<String, Discount> buildDiscountMap(List<List<String>> discounts) {
        HashMap<String, Discount> discountMap = new HashMap<>();
        for (List<String> discount : discounts) {
            discountMap.put(discount.get(0), mapInputToDiscount(discount));
        }
        return discountMap;
    }

    private static Discount mapInputToDiscount(List<String> discount) {
        int type = Integer.parseInt(discount.get(1));
        double amount = Double.parseDouble(discount.get(2));

        if(type == 1) {
            return new PercentageDiscount(amount);
        } else if(type == 2) {
            return new PriceDiscount(amount);
        } else {
            throw new IllegalArgumentException("Unknown discount type");
        }
    }
...

But maybe I can...

This is as far as you can go refactoring your code I think. You can notice that most of the work is actually parsing the input into something "readable", after that it is pretty much self explainatory.

I have applied a few cleanups to parsing and this is what the final result looks like:

    public static int calculateOptimalPrice(List<Product> products) {
        return products.stream()
               .mapToInt(Product::optimalPrice)
               .sum();
    }

...But there is a lot of stuff going on in the background. When lookig at it, focus on the main method and explore what each that is invoked looks like. Don't start reading from top to bottom as your head will start spinning.

This is actually what the final result is:

public class Solution {

    interface Discount {
        double apply(double amount);
    }

    private static class PercentageDiscount implements Discount {
        private final double amount;

        public PercentageDiscount(double amount) {
            this.amount = amount;
        }

        @Override
        public double apply(double originalPrice) {
            return Math.round(originalPrice - (originalPrice * (this.amount / (double) 100)));
        }
    }

    private static class PriceDiscount implements Discount {
        private final double amount;

        public PriceDiscount(double amount) {
            this.amount = amount;
        }

        @Override
        public double apply(double originalPrice) {
            return Math.round(originalPrice - this.amount);
        }
    }

    private static class Product {
        private final int price;
        private final List<Discount> discounts;

        public Product(int price, List<Discount> discounts) {
            this.price = price;
            this.discounts = discounts;
        }

        public int optimalPrice() {
            return discounts.stream()
                    .mapToInt(discount -> (int) discount.apply(this.price))
                    .min()
                    .orElse(this.price);
        }
    }

    private static class ProductMapper {
        private final Map<String, Discount> discountMap;

        public ProductMapper(Map<String, Discount> discountMap) {
            this.discountMap = discountMap;
        }

        public Product toProduct(List<String> input) {
            int price = Integer.parseInt(input.get(0));
            input.remove(0);

            List<Discount> discounts = findAssociatedDiscounts(input);

            return new Product(price, discounts);
        }

        public List<Product> toProductList(List<List<String>> productsInput) {
            return productsInput.stream()
                    .map(this::toProduct)
                    .toList();
        }

        private List<Discount> findAssociatedDiscounts(List<String> discounts) {
            return discounts.stream()
                    .map(discountMap::get)
                    .filter(Objects::nonNull)
                    .toList();
        }
    }

    private static class DiscountMapper {
        public Discount toDiscount(List<String> input) {
            int type = Integer.parseInt(input.get(1));
            double amount = Double.parseDouble(input.get(2));

            if(type == 1) {
                return new PercentageDiscount(amount);
            } else if(type == 2) {
                return new PriceDiscount(amount);
            } else {
                throw new IllegalArgumentException("Unknown discount type");
            }
        }

        public Map<String, Discount> toDiscountMap(List<List<String>> discounts) {
            HashMap<String, Discount> discountMap = new HashMap<>();
            for (List<String> discount : discounts) {
                discountMap.put(discount.get(0), this.toDiscount(discount));
            }
            return discountMap;
        }
    }

    public static int calculateOptimalPrice(List<Product> products) {
        return products.stream()
               .mapToInt(Product::optimalPrice)
               .sum();
    }

    public static void main(String[] args) {

        List<List<String>> productsInput = new ArrayList<>();
        List<List<String>> discountsInput = new ArrayList<>();
        productsInput.add(new ArrayList<>(List.of("20", "discount1", "discount2")));
        productsInput.add(new ArrayList<>(List.of("15", "discount2")));
        productsInput.add(new ArrayList<>(List.of("10", "NONE", "discount1")));
        discountsInput.add(new ArrayList<>(List.of("discount1", "1", "30")));
        discountsInput.add(new ArrayList<>(List.of("discount2", "2", "5.5")));

        // Moved input parsing out of the total price calculation
        Map<String, Discount> discountMap = new DiscountMapper().toDiscountMap(discountsInput);
        List<Product> products = new ProductMapper(discountMap).toProductList(productsInput);

        System.out.println(calculateOptimalPrice(products));

    }
}

The code is longer, it is probably slower, is more complex architecturaly and still only prints 31. But each part only does one job and is easy to change and to understand what the change will affect. The biggest change from the original is probably that Discount and Product are classes now, which makes it way easier to manage.

Another benefit from this approach is that you can represent the input differently, but you will only need to change the parsing - the "business rules" are isolated and don't know about how original input looked like.

Hopefully this wasn't too much at once :) I tried to split everything in small steps to be easier to understand how your code trippled in size. If you take anything away from this, let it be naming and asking yourself what a block of code does so you can extract it into a new method (the first two improvements).

\$\endgroup\$
1
\$\begingroup\$

Your time and space complexities are correct. You could also write your time complexity as O(N+M*k), which is equivalent.

There are a few things that could be improved in your code but it shouldn't change its runtime perfs much.

Naming conventions

Most of your variable are slightly misnamed or have not-quite-helpful names, and so does DisHelper. I assume that you're doing an online challenge where the Price method is an imposed signature so I'll ignore it.

Calling DisHelper that way instead of DiscountHelper, you spare 4 characters in exchange for code clarity.

Your finalPrice really is more a totalPrice, since it is the sum of all your optimal prices. At first glance, with this name, I expected it to contain the final price of the current product.

Those are two examples but price1, subDisObj and list share similar issues.

Coding against the interface

You should (almost) never explicitly declare a variable as a HashMap. Since you only use the Map interface, you should instead do Map<String, DisHelper> map = new HashMap<>();. That way, changing from a HashMap to any other type of Map will have less impact on your code.

Number handling

It seems that your originalPrice will always be an int but you parse it as a double. Then, you cast it back to an int at the last moment, when adding it to finalPrice.

Instead, you could only keep it as an int, and cast the result of the discount as as an int. You could save an infinitesimal amount of time comparing two int (32 bits) instead of two double (64 bits). With a very large number of test cases on an online challenge, that could potentially save you some milliseconds, but probably not much more.

One way to do that would be to replace

                double price1=originalPrice;
                DisHelper subDisObj = map.get(list.get(i));
                if(subDisObj.type==1) {
                    price1=Math.round(price1-(price1*(subDisObj.d/(double)100)));
                } else if(subDisObj.type==2) {
                    price1=Math.round(price1-subDisObj.d);
                }
                optimalPrice=Math.min(optimalPrice, price1);

by

                int currentPrice;
                DisHelper subDisObj = map.get(list.get(i));
                if (subDisObj.type==1) {
                    currentPrice = (int) Math.round(originalPrice*(1-subDisObj.d/100.0));
                } else if (subDisObj.type==2) {
                    currentPrice = (int) Math.round(originalPrice-subDisObj.d);
                }
                optimalPrice=Math.min(optimalPrice, currentPrice);
\$\endgroup\$
2
  • \$\begingroup\$ There is excellent feedback. Would you say I have the optimal solution? For each product, I'm traversing through each discount name. This part takes O(M*k). I'm wondering if I can do something here to reduce the time complexity. It seems like I can't do much for space complexity as I have to use a HashMap to retrieve discount type and value in O(1) instead of O(n) \$\endgroup\$
    – user-116
    Commented Sep 1, 2021 at 20:45
  • \$\begingroup\$ I can't prove that it is optimal, so I won't say it but it does look like it. If your input was built differently (for each product, two different lists, one with type 1 discounts and one with type 2 discounts, both of them sorted by amount of reduction), then you could reduce it down to O(M) instead of O(M*k), but that would be cheating. :) \$\endgroup\$
    – Anab
    Commented Sep 2, 2021 at 17:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.