<jupyter_start><jupyter_text>Leetcode link: https://leetcode.com/problems/majority-element/ Problem Statement:Given an array of size n, find the majority element. The majority element is the element that appears more than `⌊ n/2 ⌋` times.You may assume that the array is non-empty and the majority element always exist in the array. --- **Example 1:**`Input: [4,4,4,2,1]Output: 4`**Example 2:**`Input: [1,1,1,1,1,1,1,2]Output: 1`---  Three Solutions: 1. Hashmap 2. Sorting 3. Moore’s Voting Algorithm---  Solution 1: Hashmap* Store the count of each of element in the array in a hashmap, as a hashmap has O(1) access.* Select the max of the hashmap by the key values (counts of nums) to find the single majority element. Speed: O(n)* Iterate through the array once takes O(n). Finding the max of the hashmap takes O(n/2), which rounds up to O(n). Space: O(n)* There are guaranteed to be a majority element, so there will be at most `⌈ n / 2 ⌉` elements in the array. This rounds up to O(n).<jupyter_code>def majorityElement(nums: list) -> int:
    d = {}

    for num in nums:
        d[num] = d.get(num, 0) + 1
        
#         print(d)

    return max(d, key=lambda x: d[x])
nums = [1,1,1,2,1,4,2]
majorityElement(nums)<jupyter_output><empty_output><jupyter_text>---  Solution 2: Sorting* Sort the elements and access the middle element of the array.* Middle element guaranteed to be the result as the result appears n / 2 times, so starting from end, beginning, or somewhere in the middle, it is guaranteed to be at the middle of the sorted array. Speed: O(nlogn)* Sorting takes O(nlogn). Space: O(1)* No **extra** storage needed as original input array is modified.<jupyter_code>def majorityElement(nums: list) -> int:
    nums.sort()
#     print(nums)
    return nums[len(nums) // 2]
nums = [1,4,4,4,1,4,2]
majorityElement(nums)<jupyter_output><empty_output><jupyter_text>---  Solution 3: Moore’s Voting Algorithm* **This method only works when the majority element is guaranteed to be in the array.*** Each occurrence of the majority element, save for at least one, will be canceled by every other element in the array. The final result value will be the majority element. Speed: O(n)* Iterate through the array once. Space: O(1)* Constant space for two variables: `result` and `count`. O(2) rounds down to O(1).<jupyter_code>def majorityElement(nums: list) -> int:
    result = None
    count = 0

    for num in nums:
        if count == 0:
            result = num
            count = 1
        elif num == result:
            count += 1
        else:
            count -= 1
            
#         print(result, count)

    return result
nums = [2,2,1,3,1,1,1]
majorityElement(nums)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11053984575835475, 'fraction_numerical': 0.022401762761659935, 'mean_word_length': 3.502479338842975, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 16, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '115479', 'license': 'BSD-3-Clause', 'n_tokens_mistral': 893, 'n_tokens_neox': 854, 'n_words': 357, 'path': 'majority_element_1/Majority Element 1.ipynb', 'repo_name': 'programmingwithalex/Coding_Problems', 'size': '2723'}