-2
\$\begingroup\$

This is for leetcode problem: https://leetcode.com/problems/majority-element

There is something wrong with the way I create solutions, and not sure how to stop doing it. Basically the problem is I always create a count variable. Here is it called greatest_count. For the if statement, I create a conditional, which I think is fine, but I feel like I don't need the additional greatest_count variable here but not sure a better way to write it. I always seem to think I need to count it and check it against the previous counts. Do I need this? How can I write this without needing the count variable? or without using the greatest unique? Any ways to optimize this would be great to know.

Problem area:

if unique_count > greatest_count:
   greatest_count = unique_count
   greatest_unique = i

Here is the full code:

class Solution:
    def majorityElement(self, nums):
        unique_nums = set(nums)
        greatest_unique = 0
        greatest_count = 0
        
        for i in unique_nums:
            unique_count = nums.count(i)
            if unique_count > greatest_count:
                greatest_count = unique_count
                greatest_unique = i
        return greatest_unique
\$\endgroup\$
4
  • 4
    \$\begingroup\$ Thank you for providing the link, however, links can break. Please include the text of the programming challenge in the question. \$\endgroup\$
    – pacmaninbw
    Oct 19 '21 at 19:36
  • 2
    \$\begingroup\$ It's not clear from question, but I'm assuming the code is passing all tests? \$\endgroup\$
    – joseville
    Oct 19 '21 at 19:42
  • \$\begingroup\$ Check out Moore's algorithm \$\endgroup\$
    – vnp
    Oct 20 '21 at 6:08
  • 1
    \$\begingroup\$ The current question title, which states your concerns about the code, is too general to be useful here. Please edit to the site standard, which is for the title to simply state the task accomplished by the code. Please see How to get the best value out of Code Review: Asking Questions for guidance on writing good question titles. \$\endgroup\$ Oct 28 '21 at 9:57
0
\$\begingroup\$

Your code, simplified:

Here's an alternative that uses fewer variables. It involves tuple comparisons in max(num_cnt_max, num_cnt):

CNT, NUM = 0, 1
class Solution:
    def majorityElement(self, nums):
        unique_nums = set(nums)
        num_cnt_max = (0, 0)
        
        for num in unique_nums:
            num_cnt = (nums.count(num), num)
            num_cnt_max = max(num_cnt_max, num_cnt)
        return num_cnt_max[CNT]

Use Counter instead of set and list.count:

Another suggestion is to use collections.Counter instead of the combination of set and list.count your solution uses. In case you're not familiar with Counter, here's an example of its usage:

from collections import Counter

nums = [1, 6, 3, 9, 3, 4, 3, 1]
nums_counter = Counter(nums)
print(nums) # Counter({3: 3, 1: 2, 6: 1, 9: 1, 4: 1})

The relationship between nums and nums_counter is that nums_counter[num] == nums.count(num). Creating a Counter (Counter(nums)) and then accessing it (nums_counter[num]) repeatedly is probably faster than repeatedly calling nums.count(num).

Use information given in the problem statement:

Another suggestion is to use the information that the majority element appears more than N / 2 times. In a list of N elements how many different elements can have a count of more than N / 2? Using that information would let you break out of the foo loop earlier and you'd know which element is the majority just by looking at its count, so you would not have to maintain the intermediate num_cnt_max variable.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ You should make note of the Counter.most_common([n]) method, which reduces the code to one statement return Counter(nums).most_common(1)[0]. But what you really should do is provide a review of the OP's code, since alternate-solution-only answers are not valid answers on this site. \$\endgroup\$
    – AJNeufeld
    Oct 19 '21 at 22:13

Not the answer you're looking for? Browse other questions tagged or ask your own question.