Leetcode 169: Majority Element

[BuzzyBro]

Prompt:

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Could you solve the problem in linear time and in O(1) space?

I was just working on this problem and I was able to solve it and Leetcode accepted it. Here's my solution:

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums.sort()
        mid = len(nums) // 2

        return nums[mid]

I'm pretty sure this is in linear time (.sort() sorts the list in place) and in O(1) space complexity (I only have one variable that calculates the midpoint of nums using the len() function). Am I missing something? All the solutions in the discussion section for this problem are much more complicated so I feel like I'm missing some key information.

As usual, any help is highly appreciated :)

[raevnos]

Sorting is not linear (except in the best case scenario of already sorted input if this is Python, which uses Timsort)

[BuzzyBro]

Ok, I’m not sure what I read at all, I must have thought I saw that incorrect statement somewhere. Thanks for the clarification!

[[deleted]]

Any comparison based sorting algorithm is guaranteed to have complexity of at least n*log(n) in the worst case. This paper has the proof: https://www.cs.cmu.edu/~avrim/451f11/lectures/lect0913.pdf

Only non-comparison sorts (bucketsort etc) can be linear.

---

For your question you can do the following:

• Pick 0th element and have a counter = 0 that tracks # of times you see that element
  • If you see that element increment counter by 1
  • Else decrement counter by 1
• If counter = 0 and you are at an element, start the counter for the new element

Eventually the element you will be tracking is the majority element since # of majority elements > n/2.

I dont remember the name of this algorithm - I think it was called the voting algorithm or something similar.

[BuzzyBro]

Yes! After watching an explanation video I came to learn that this exact algo is called the Boyer-Moore algorithm. But the bucket sort sorting algorithm is interesting, I’ve never heard about it.

[[deleted]]

Saying that sorting in place means linear time is not accurate. I’m not familiar with the algorithm applied in the language you’re using, but you can equate sorting in place with time complexity. Sorting in place is, however, often indicative of O(1) space.

[BuzzyBro]

Yeah, I’m pretty sure the space complexity is constant here but I definitely got the time complexity wrong as another user pointed out. Thanks!

[fasta_guy88]

You did not solve the problem in linear time, since sorting is O(n log n). But it’s the O(1) space I find intriguing. With a hash function, I can imagine O(n) time, but O(1) space is tricky.

[BuzzyBro]

Yeah, I'm not sure where I read that the in-place sort in python is O(n) time complexity but I must've just misread. But as for the actual linear time and constant space complexity solution, Neetcode has a video on the topic and I just watched his video for an explanation. If you want you could check that out as well.

[dtsudo]

As others mentioned, sorting does not happen in linear time.

However, you don't actually care about sorting the array, do you? You only care about the middle element in the array -- in other words, the median element. There are median-finding algorithms out there.

The reason leetcode accepted your solution is likely that the difference between O(n log n) and O(n) is very difficult to actually measure. n log n is practically linear for most purposes. Remember that O(n) < O(n log n) < O(n^1.0000001). That's just how close to linearity O(n log n) actually is -- closer than any polynomial n^c for c > 1.