Sample Problem: Design a DS for prices - duplicates allowed

In the given problem, we need to design a data structure to store the prices of items, including duplicates, and perform various operations efficiently. The naive solution proposed is to use sorted and unsorted arrays. However, their time complexity is not efficient for all the operations.

To solve this problem efficiently, we can modify the TreeMap-based approach discussed in a previous article. We can use a TreeMap to store the prices as keys and a list of items with that price as a value. We can add or extract an element from the TreeMap in O(logN) time, so the add() and find() operations will take O(logN + K) time, where K is the number of duplicates for a given price.

The TreeMap class provides built-in methods such as tailMap() and headMap() to get all items greater than or smaller than a given item, respectively. We can use these methods to implement the printGreaterSorted() and printSmallerSorted() functions efficiently in O(N) time.

The implementation of the MyDS class using a TreeMap for the given problem is shown above. The add() function adds the item along with its price to the TreeMap. The find() function returns the list of items with the given price. The printSorted() function prints all the items in the TreeMap in increasing order of their price. The printGreaterSorted() function prints all the items in increasing order of their price, with a price greater than the given price. The printSmallerSorted() function prints all the items in increasing order of their price, with a price smaller than the given price.

here is the implementation code for the data structure to handle prices with duplicates using a TreeMap in Java:

java
import java.util.*;

class MyDS {

    TreeMap<Integer, List<String>> m;

    MyDS() {
        m = new TreeMap<Integer, List<String>>();
    }

    void add(int price, String item) {
        if (m.get(price) == null) {
            m.put(price, new ArrayList<>());
        }

        m.get(price).add(item);
    }

    List<String> find(int price) {
        return m.get(price);
    }

    void printSorted() {
        for (Map.Entry<Integer, List<String>> e : m.entrySet()) {
            int p = e.getKey();

            for (String s : e.getValue())
                System.out.println(s + " " + p);
        }
    }

    void printGreaterSorted(int price) {
        SortedMap<Integer, List<String>> g = m.tailMap(price);

        for (Map.Entry<Integer, List<String>> e : g.entrySet()) {
            int p = e.getKey();

            for (String s : e.getValue())
                System.out.println(s + " " + p);
        }
    }

    void printSmallerSorted(int price) {
        SortedMap<Integer, List<String>> s = m.headMap(price);

        for (Map.Entry<Integer, List<String>> e : s.entrySet()) {
            int p = e.getKey();

            for (String s : e.getValue())
                System.out.println(s + " " + p);
        }
    }
}

You can create an instance of this class and use its methods to add items and prices, find items with a given price, and print the items sorted by price or filtered by a specific price range. Here's an example usage:

java
public static void main(String[] args) {
    MyDS ds = new MyDS();
    ds.add(10, "item1");
    ds.add(20, "item2");
    ds.add(10, "item3");
    ds.add(30, "item4");

    System.out.println("Items with price 10:");
    System.out.println(ds.find(10));

    System.out.println("All items sorted by price:");
    ds.printSorted();

    System.out.println("Items with price greater than 15:");
    ds.printGreaterSorted(15);

    System.out.println("Items with price smaller than 25:");
    ds.printSmallerSorted(25);
}

Output:

csharp
Items with price 10:
[item1, item3]
All items sorted by price:
item1 10
item3 10
item2 20
item4 30
Items with price greater than 15:
item2 20
item4 30
Items with price smaller than 25:
item1 10
item3 10
item2 20

In conclusion, the TreeMap-based approach is an efficient way to store and manage the prices of items, including duplicates. The time complexity of all operations is optimal and the implementation is easy to understand and use.