Find sum of max repeating integer in array with least time complexity

Question

I am new to programming and trying to learn by exploring. I was looking for a solution to find sum of maximum time repeating integer in an array with best time complexity. Suppose we have [1, 2, 3, 3] the result should be 6 with least time complexity, say O(n).

I came up with a solution but not sure about the complexity. Need some help to understand if below mentioned code has least complexity or it could be better(definitely!). Sorry if I made any mistake and thanks in advance.

public static int mapBasedFinder(int[] arr){
    Map<Integer, Integer> values = new HashMap<Integer, Integer>();
    int result = 0;
    for(int i=0; i<arr.length; i++){
        int temp = arr[i];
        if(values.containsKey(temp))
            values.put(temp, values.get(temp)+1);
        else
            values.put(temp, 1);

        Map.Entry<Integer, Integer> maxEntry = null;
        for (Map.Entry<Integer, Integer> entry : values.entrySet())
        {
            int key = entry.getKey();
            if (maxEntry == null || entry.getValue().compareTo(maxEntry.getValue()) > 0)
            {
                maxEntry = entry;
                result = entry.getValue() * key;
            }
        }
    }
    return result;
}

It looks like an error to have the second for loop inside the first one. Your first loop (which fills the map) should finish before the second one scans the map. — aro_tech
– aro_tech, Commented Nov 8, 2015 at 6:01

Erwin Bolwidt · Accepted Answer · 2015-11-08 05:59:12Z

1

You have two loops, with the second loop inside the first loop. That's going to give you complexity worse than O(n) - probably O(n²) (worst case).

But it looks to be a mistake. You should move the second loop outside the first loop, because you only need to check the maximum once you have completely iterated over the array once to find out how many times each number repeats.

And then you're complexity is back to O(n) because there is no such thing as O(2n) - iterating over the values twice is still O(n).

answered Nov 8, 2015 at 5:59

Erwin Bolwidt

31.3k15 gold badges59 silver badges81 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

new guy Over a year ago

What if we want to minimize space complexity, no matter what time complexity would be(suppose time complexity is not a concern any more), what will be the best case for space complexity?

Uma Kanth · Accepted Answer · 2015-11-08 05:57:48Z

0

Maintain 2 variables maxRepCount and maxRepNum and keep track of these two. Instead of processing after reading all elements, use it in the loop.

int []a = {1,2,3,3};
int maxRepCount = -1;
int maxRepNum = a[0];
HashMap<Integer, Integer> hm = new HashMap();

for(int i = 0; i < a.length; ++i)
{
 int count;
 if(hm.containsKey(a[i]))
 {
  count = hm.get(a[i]) + 1;
  hm.put(a[i], count);
 }
 else
 {
  hm.put(a[i], 1);
  count = 1;
 }
 if(count > maxRepCount)
  { 
    maxRepCount = count;
    maxRepNum = a[i];
  }
}
System.out.println(maxRepNum * maxRepCount);

answered Nov 8, 2015 at 5:57

Uma Kanth

5,6292 gold badges22 silver badges43 bronze badges

2 Comments

Stephen C Over a year ago

Yup. Time compexity O(N), space complexity O(N).

new guy Over a year ago

Thanks, I can understand it better now. What if we want to minimize space complexity, no matter what time complexity would be(suppose time complexity is not a concern any more), what will be the best case for space complexity?

Collectives™ on Stack Overflow

Find sum of max repeating integer in array with least time complexity

2 Answers 2

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related