CODEWITHSUNDEEP
pythonalgorithm
user514310
user514310

Reputation:

Find most-frequently-occurring element with O(n) time and O(1) space

I want to find the most-frequently-occurring element in a list, in O(n) time and O(1) space.

First Solution

from collections import Counter
def max_repetitions(elements):
    return max([v for k, v in Counter(elements).items() if v > 1])

Space complexity is O(n). I'm not sure about time complexity. Is it O(nlogn) or O(n)?

Second solution

def max_repetitions(elements):
counter = 0
for k, v in Counter(elements).items():
    if v > 1 and counter < v:
        counter = k
return counter

What is the time-complexity of this solution? Is it O(nlogn) or O(n)?

Is there any other way?

Upvotes: 2

Views: 812

Answers (3)

user1952500
user1952500

Reputation: 6771

If you want a majority element, which is an element that appears more than n/2 times in the array, you can use the (very simple) MJRTY algorithm due to Boyer-Moore: http://www.cs.utexas.edu/~moore/best-ideas/mjrty/ This runs in O(n) time with O(1) space.

Upvotes: 1

Louis Ricci
Louis Ricci

Reputation: 21106

If your list is already sorted

function maxItem(list) {
var maxCount = 0;
var maxElement = null;
for(var i = 0, count = 1, elm = null; i < list.length; i++) {
  if(elm != list[i]) {
    count = 1;
    elm = list[i];
  } else { 
    count++;
  }
  if(count > maxCount) {
    maxCount = count;
    maxElement = elm;
  }
}
return maxElement;
}

console.log(maxItem([1,1,1, 2,2,2,2, 4,4, 8,8,8,8,8])); // 8
console.log(maxItem([1,1,1, 2,2,2,2, 4,4, 8,8,8,8,8, 9])); // 8
console.log(maxItem([8])); // 8

edit sorry it's JavaScript not python

Upvotes: 0

MatsLindh
MatsLindh

Reputation: 52872

In simple cases like these: To get the time complexity try to answer how many times you iterate over the elements in a sequence.

Since you're using the Counter class in the collections module that will also affect the complexity, but let's assume that it's O(n).

The only other work you do is to iterate over the list again, with also is O(n). That gives O(n) as the time complexity, as it grows linearly with the number of elements n.

Upvotes: 1

Related Questions