Finding max/min values for distinct elements of an unsorted collection

Question

I have a list of Country code values (which can be duplicated) and corresponding prices as shown in the Class Main, i want to find max/min in this way:

if Country Code = 0.1 , i should get it max price= 0.92 from 0.90, 0.91, 0.92. and so on for all other country codes i.e. i want to Find max price for each distinct Country codes

i have done it successfully in the code shown below. But it is very slow and not good approach.

My Method: As the data in "Class Main" is related (country code, with price), i first sort the data by country code using Class "Telephone" with Comparator, and then i scan all the elements of the " Telephone-ArrayList" and then i find the max value for each "Distinct" Country Code with comparison of ArrayList elements.

class Telephone implements Comparator<Telephone>{
    private int countryCode; 
    private double price;

    Telephone(){
    }

    Telephone( int c, double p){
        countryCode= c;
        price= p;

    }

    public int getCountryCode(){
        return countryCode;
    }

    public double getPrice(){
        return price;
    }


    // Overriding the compare method to sort
    public int compare(Telephone d, Telephone d1){

        return d.getCountryCode() - d1.getCountryCode();    
    }

}


public class Main {                          
    /**                                     
    * @param args
    */
    public static void main(String[] args) {
        // Takes a list o Telephone objects
        ArrayList <Telephone> list = new ArrayList<Telephone>(); 
        ArrayList <Double> arr = new ArrayList<Double>(); 
        list.add(new Telephone(1, 0.9));
        list.add(new Telephone(268, 5.1 ));
        list.add(new Telephone(46, 0.17 ));
        list.add(new Telephone(46, 0.01));
        list.add(new Telephone(4631, 0.15 ));
        list.add(new Telephone(4620, 0.0 ));
        list.add(new Telephone(468, 0.15 ));
        list.add(new Telephone(46, 0.02));
        list.add(new Telephone(4673, 0.9));
        list.add(new Telephone(46732,1.1));



        list.add(new Telephone(1, 0.91 ));
        list.add(new Telephone(44, 0.4 ));
        list.add(new Telephone(92, 0.4 ));
        list.add(new Telephone(467, 0.2 ));
        list.add(new Telephone(4, 0.0001 ));

        list.add(new Telephone(1, 0.92 ));
        list.add(new Telephone(44, 0.5 ));

        list.add(new Telephone(467, 1.0 ));
        list.add(new Telephone(48, 1.2 ));
        list.add(new Telephone(4, 0.1));

        Collections.sort(list, new Telephone());

        for ( int i=0; i < list.size()-1; i++)
        {

            arr.clear();

            while ( list.get(i).getCountryCode()== list.get(i+1).getCountryCode())
            {

              arr.add(list.get(i).getPrice()) ;
              i=i+1;

            }
            arr.add(list.get(i).getPrice());

            arr.trimToSize();

            System.out.println( " Max value is " + Collections.max(arr).toString() + " for " +list.get(i).getCountryCode());
        }
    }   
}

Answer 1

I think the best implementation depends on what you are after.

a)If you have a more or less static set of phones which is called often, you should try to set the min,max when adding a new telefone.

b) If you are adding telefons frequently you should get the min max only if you require it.

for a) You could use HashMap where key is country code.

 HashMap<Integer,ArrayList<float>> telefonMap = new HashMap<Integer,ArrayList<float>();
 addtelephone(int coutrycode, float price ){
  if (telefonMap.contains(countrycode){
     telefonMap.get(contrycode).add(price);
     // if you have frequent min max requests add, else skip the next line
     Collections.sort(telefonMap.get(countrycode));
  }
  else {
     ArrayList<Float> tempList = new ArrayList<Float>();
     priceList.add(price);
     telefonMap.put(contrycode,tempList);
 }
}

now you can get the min max element by calling

telephoneMap.get(countrycode).get(0 or telephoneMap.get(countrycode).size()-1)

If you haven't sorted the array while adding the phone than you just call the array here and sort it

Answer 2

If I were you I would do with maps as below.

// Mapping of counties and lis of prices
Map<String, List<Double>> telephones = new HashMap<String, List<Double>>();

//Searching for country code 0.1
List<Double> prices = telephones.get("0.1");

//Finding Max and Min
Double maximum = Collections.max(prices);
Double minimum = Collections.min(prices);

Answer 3

You could let Telephone implement Comparable and if the counrycodes are equal you could calculate your price into the comparison. If you sort your list then, you will have it sorted by contrycode first and then by price.

You can then iterate over your Telephone colection and keep the contrycode for each interation. The last element of a countrycode you iterated over will be the one with the highest price. This way you can do the country code comparison and price comparison in one step.

 public int compareTo(Telephone d){
    int cc1 = this.getCountryCode();
    int cc2 = d.getCountryCode();

    if(cc1 == cc2){
      double price1 = this.getPrice();
      double price2 = d.getPrice();          
      if(price1 < price2)
         return -1;
      if(price1 > price2)
         return 1;
      return 0;
    }

    return cc1 - cc2;    
 }

Answer 4

You can do this without doing any sorting up-front, so your only costs will be one iteration through the collection and the insertion time for a hash map.

Collection<Telephone> list = ...;

Map<Integer, Double> maximumPrices = new HashMap<Integer, Double>();

for(Telephone telephone : list) {
    Double checkPrice = maximumPrices.get(telephone.getCountryCode());
    if(checkPrice == null || checkPrice < telephone.getPrice()) {
        maximumPrices.put(telephone.getCountryCode(), telephone.getPrice());
    }
}

I'll leave adding support for recording minimum prices as an exercise for you.