How to speed up this piece of java code?

Question

This method returns the number from the array of positive integers if it occurs more than half times of the array size, -1 otherwise. I need to improve its running time for larger arrays (10^5<size<10^8). Any suggestions?

public static int findResult(int arr[],int len){

    int val=0;
    HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
    for(int i=0;i<len;i++){
        if(map.containsKey(arr[i])){
            val = (Integer)map.get(arr[i]);
            map.put(arr[i], val+1);
        }else{
            val=1; 
            map.put(arr[i], val);
        }
    }
    Iterator<Integer> it=map.keySet().iterator();
    while(it.hasNext()){
        int next=it.next();
        if((Integer)map.get(next)>(len/2)){
            return next;
        }
    }
    return -1;
}

This probably should be posted to [codereview](http://codereview.stackexchange.com/), not SO. — Denys Séguret, May 05 '13 at 12:20
(i) instead of containsKey + get, just use one `get` and compare with `null` (ii) keep track of the highest number in the first loop and get rid of the second loop (iii) size your map to start with and avoid many rehashing operations — assylias, May 05 '13 at 12:23
@assylias yes, I got the point using `if(val+1>len/2) return arr[i];` eliminates the use of iterator for the purpose. Thanks — Nishant, May 05 '13 at 12:36
You can also abort the loop early, if you have traversed half and count is still 0 "more than half" will not hold. — arynaq, May 05 '13 at 13:48

score 6 · Accepted Answer · answered May 05 '13 at 12:44

6

You can do this without a Map, removing the need for boxing/unboxing:

public static int findResult(int[] arr, int len) {
    if(len == 0) return -1;
    if(len == 1) return arr[0];

    int element = arr[0];
    int count = 1;
    for(int i = 1; i < len; i++) {
        if(arr[i] == element) {
            count++;
        } else if(count > 0) {
            count--;
        } else {
            element = arr[i];
            count = 1;
        }
    }

    count = 0;
    for(int a:arr) {
        if(a == element) {
            count++;
        }
    }

    return (count > len / 2) ? element : -1;
}

answered May 05 '13 at 12:44

fgb

18,439
2
38
52

Doesn't this algo work ONLY IF one item is the majority? – assylias May 05 '13 at 13:09
@assylias If no item is a majority then the final count will be <= len/2 and -1 should be returned. – fgb May 05 '13 at 13:18
I had missed the second loop. Here is a nice explanation of the algo: http://stackoverflow.com/a/3740548/829571 – assylias May 05 '13 at 13:38

score 1 · Answer 2 · answered May 05 '13 at 12:25

1

Why don't you compare against the length (the second iterator loop you are running) after every iteration of inputting in the hashmap? This was by the time the hashmap is done, you know the result, and you only have to do this once.

answered May 05 '13 at 12:25

William Falcon

9,813
14
67
110

score 0 · Answer 3 · answered May 05 '13 at 12:28

This IMO is shorter and more efficient

public static int findResult(int arr[], int len) {
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    for (int i = 0; i < len; i++) {
        Integer val = map.get(arr[i]);
        if (val != null) {
            map.put(arr[i], val + 1);
        } else {
            map.put(arr[i], 1);
        }
    }
    for (Entry<Integer, Integer> e : map.entrySet()) {
        if (e.getKey() > (len / 2)) {
            return e.getValue();
        }
    }
    return -1;
}

1) original version uses 2 method calls on map

if(map.containsKey(arr[i])){
        val = (Integer)map.get(arr[i]);

mine uses one map.get

2) this

 while(it.hasNext()){
        int next=it.next();
        if((Integer)map.get(next)>(len/2)){

is so bad performance-wise that even Sonar or FindBugs will detect it iimediately and suggest to replace with what I offer

Although this is still O(n), the size of this input can make a difference between iterating once vs twice. Also changing the map.contains to your get is still the same O(1). — William Falcon, May 05 '13 at 12:33

score 0 · Answer 4 · answered May 05 '13 at 12:53

you can use a temp variable to store always the biggest amount, every time you are increasing the counter of some variable, check if its bigger than your temp, if it is, replace it, otherwise continue, this way you can do it without the second loop and you just know your answer is in the temp variable

How to speed up this piece of java code?

4 Answers4