{"id":755,"date":"2023-12-06T16:00:00","date_gmt":"2023-12-06T16:00:00","guid":{"rendered":"https:\/\/favtutor.com\/articles\/?p=755"},"modified":"2023-12-08T13:07:27","modified_gmt":"2023-12-08T13:07:27","slug":"majority-element","status":"publish","type":"post","link":"https:\/\/favtutor.com\/articles\/majority-element\/","title":{"rendered":"Majority Element Problem (C++, Java, Python)"},"content":{"rendered":"\n<p>In programming interviews, there are many leetcode problems related to arrays and one of them is the majority element. In this article, we will explore different approaches to find the optimal solution for this problem and discuss their time complexities.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>What is the Majority Element?<\/strong><\/h2>\n\n\n\n<p><strong>In this problem, we are given an array and our main goal is to find the majority element in an array.<\/strong> The majority element is defined as an element that occurs more than N\/2 times in the given array, where N represents the size of the array. <\/p>\n\n\n\n<p>Let us understand it better with an example:<\/p>\n\n\n\n<p class=\"has-black-color has-text-color has-background\" style=\"background-color:#fedcba\"><strong>Array<\/strong> = [3, 3, 4, 2, 4, 4, 2, 4, 4]<br><strong>Output <\/strong>= 4<\/p>\n\n\n\n<p>Output is 4 as 4 appears 5 times and the total length of the array is 9:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" width=\"1024\" height=\"155\" src=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-2-1024x155.png\" alt=\"Example of Majority Element\" class=\"wp-image-759\" srcset=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-2-1024x155.png 1024w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-2-300x46.png 300w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-2-768x116.png 768w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-2-750x114.png 750w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-2-1140x173.png 1140w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-2.png 1279w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<\/div>\n\n\n<h2 class=\"wp-block-heading\"><strong>Brute Force Approach: Using Hashmap<\/strong><\/h2>\n\n\n\n<p>In this approach, we will use <a href=\"https:\/\/favtutor.com\/blogs\/hashing-in-data-structure\">hashmap <\/a>to count the number of occurrences of each element and check which element is occurring more than n\/2 times where n is the size of our array.<\/p>\n\n\n\n<p>Here are the steps to solve this problem:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Firstly we will declare a hashmap to store the count of each element and then we will run a loop to store the element with their occurrence in the hashmap.<\/li>\n<\/ul>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" width=\"1024\" height=\"405\" src=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-2-1024x405.png\" alt=\"declare a hashmap\" class=\"wp-image-761\" srcset=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-2-1024x405.png 1024w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-2-300x119.png 300w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-2-768x304.png 768w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-2-750x297.png 750w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-2-1140x451.png 1140w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-2.png 1276w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<\/div>\n\n\n<ul class=\"wp-block-list\">\n<li>Now we will run a loop to search for the majority element in the map and if there is no such element in the map then we will return -1.<\/li>\n<\/ul>\n\n\n\n<p>The time complexity for this approach is O(n*logn) + O(n) where n is the size of the array as the map data structure takes logN time for insertion as we are doing it for n elements in the array and O(n) for searching it.<\/p>\n\n\n\n<p>The space complexity of this approach is O(m) as we are using map data structure and m is the number of unique elements present in the map<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Optimal Approach: Moore\u2019s Voting Algorithm<\/strong><\/h2>\n\n\n\n<p><strong>The Boyer-Moore Majority Vote Algorithm is an optimal algorithm for finding the majority element in a sequence of elements.<\/strong> The algorithm was proposed by Robert S. Boyer and J Strother Moore in 1980 and is particularly efficient for our purpose.<\/p>\n\n\n\n<p>Here are the steps to implement this algorithm:&nbsp;<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Firstly we will declare a count variable to keep track of the count and an element variable to store the potential majority element.<\/li>\n\n\n\n<li>We will start iterating through the array and if the count is 0 set the value of the element equal to the current element and increment count.<\/li>\n<\/ul>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" width=\"1024\" height=\"211\" src=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/3-2-1024x211.png\" alt=\"Index: 0\" class=\"wp-image-762\" srcset=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/3-2-1024x211.png 1024w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/3-2-300x62.png 300w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/3-2-768x159.png 768w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/3-2-750x155.png 750w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/3-2-1140x235.png 1140w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/3-2.png 1279w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<\/div>\n\n\n<ul class=\"wp-block-list\">\n<li>If the current element is equal to the element, increment count; otherwise, decrement count. And if the count goes less than 0 set it to 0<\/li>\n<\/ul>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img decoding=\"async\" width=\"1024\" height=\"238\" src=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/4-1-1024x238.png\" alt=\"Index: 1\" class=\"wp-image-763\" style=\"aspect-ratio:4.302521008403361;width:1024px;height:auto\" srcset=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/4-1-1024x238.png 1024w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/4-1-300x70.png 300w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/4-1-768x178.png 768w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/4-1-750x174.png 750w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/4-1-1140x265.png 1140w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/4-1.png 1280w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<\/div>\n\n\n<ul class=\"wp-block-list\">\n<li>Here 4 is not equal to 3 so we will decrease the count and as the count is not 0 our element will remain the same.<\/li>\n<\/ul>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" width=\"1024\" height=\"229\" src=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/5-1024x229.png\" alt=\"Index: 2\" class=\"wp-image-764\" srcset=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/5-1024x229.png 1024w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/5-300x67.png 300w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/5-768x172.png 768w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/5-750x168.png 750w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/5-1140x255.png 1140w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/5.png 1279w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<\/div>\n\n\n<ul class=\"wp-block-list\">\n<li>Now when our pointer comes on 2 again count will decrement and becomes 0.<\/li>\n<\/ul>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" width=\"1024\" height=\"242\" src=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/6-1024x242.png\" alt=\"Index: 3\" class=\"wp-image-766\" srcset=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/6-1024x242.png 1024w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/6-300x71.png 300w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/6-768x181.png 768w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/6-750x177.png 750w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/6-1140x269.png 1140w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/6.png 1280w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<\/div>\n\n\n<ul class=\"wp-block-list\">\n<li>The count is 0 and the current element is not equal to the element so our element will update and the count will increment.<\/li>\n<\/ul>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" width=\"1024\" height=\"218\" src=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/7-1024x218.png\" alt=\"Index: 4\" class=\"wp-image-767\" srcset=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/7-1024x218.png 1024w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/7-300x64.png 300w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/7-768x163.png 768w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/7-750x159.png 750w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/7-1140x242.png 1140w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/7.png 1280w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<\/div>\n\n\n<ul class=\"wp-block-list\">\n<li>The current element is equal to the element so the count will increment and the element will remain the same.<\/li>\n<\/ul>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" width=\"1024\" height=\"243\" src=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/8-1024x243.png\" alt=\"Index: 5\" class=\"wp-image-768\" srcset=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/8-1024x243.png 1024w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/8-300x71.png 300w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/8-768x183.png 768w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/8-750x178.png 750w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/8-1140x271.png 1140w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/8.png 1279w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<\/div>\n\n\n<ul class=\"wp-block-list\">\n<li>The count will decrease as the current element is not the same as the element but the element will not change as the count is not 0.<\/li>\n<\/ul>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" width=\"1024\" height=\"237\" src=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/9-1024x237.png\" alt=\"Index: 6\" class=\"wp-image-769\" srcset=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/9-1024x237.png 1024w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/9-300x69.png 300w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/9-768x178.png 768w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/9-750x174.png 750w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/9-1140x264.png 1140w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/9.png 1279w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<\/div>\n\n\n<ul class=\"wp-block-list\">\n<li>For the next two steps count will increment as the current element is equal to the element.<\/li>\n<\/ul>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" width=\"1024\" height=\"227\" src=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/10-1024x227.png\" alt=\"Index: 7\" class=\"wp-image-771\" srcset=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/10-1024x227.png 1024w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/10-300x66.png 300w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/10-768x170.png 768w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/10-750x166.png 750w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/10-1140x252.png 1140w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/10.png 1279w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<\/div>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" width=\"1024\" height=\"225\" src=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/11-1024x225.png\" alt=\"Index: 8\" class=\"wp-image-772\" srcset=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/11-1024x225.png 1024w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/11-300x66.png 300w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/11-768x169.png 768w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/11-750x165.png 750w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/11-1140x250.png 1140w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/11.png 1279w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<\/div>\n\n\n<ul class=\"wp-block-list\">\n<li>After the iteration element is the potential element to verify it we will run a loop to check whether the potential element is the actual majority element or not.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>C++ Code<\/strong><\/h3>\n\n\n\n<p>Here is the C++ program to find the majority element in an array:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;clike&quot;,&quot;mime&quot;:&quot;text\/x-c++src&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;C++&quot;,&quot;modeName&quot;:&quot;cpp&quot;}\">#include&lt;bits\/stdc++.h&gt;\nusing namespace std;\nint majorityElement(vector&lt;int&gt;&amp; nums) {\n    \/\/ Initialize variables to track the current candidate element and its count\n    int element = 0;\n    int count = 0;\n\n    \/\/ Traverse the array\n    for (int i = 0; i &lt; nums.size(); i++) {\n        \/\/ If the count is 0, update the current element\n        if (count == 0) {\n            element = nums[i];\n        }\n\n        \/\/ Update count based on whether the current element is equal to the candidate element\n        if (nums[i] == element) {\n            count++;\n        } else {\n            count--;\n        }\n    }\n\n    \/\/ Check if the candidate element is the majority element\n    int countCheck = 0;\n    for (int i = 0; i &lt; nums.size(); i++) {\n        if (nums[i] == element) {\n            countCheck++;\n        }\n    }\n\n    \/\/ If the count of the candidate element is greater than half the array size, it is the majority element\n    if (countCheck &gt; nums.size() \/ 2) {\n        return element;\n    }\n\n    \/\/ If there is no major element, return -1\n    return -1;\n}\n\nint main() {\n    \/\/ Example array\n    vector&lt;int&gt; nums = {3, 3, 4, 2, 4, 4, 2, 4, 4};\n\n    \/\/ Find the majority element using the function\n    int result = majorityElement(nums);\n\n    \/\/ Print the result\n    if (result != -1) {\n        cout &lt;&lt; &quot;The majority element is: &quot; &lt;&lt; result &lt;&lt; endl;\n    } \n  \telse {\n        cout &lt;&lt; &quot;There is no majority element.&quot; &lt;&lt; endl;\n    }\n\n    \/\/ Return 0 to indicate successful completion\n    return 0;\n}<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Java Code<\/strong><\/h3>\n\n\n\n<p>Below is the Java code to solve this problem:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;clike&quot;,&quot;mime&quot;:&quot;text\/x-java&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;Java&quot;,&quot;modeName&quot;:&quot;java&quot;}\">import java.util.HashMap;\nimport java.util.Map;\n\npublic class MajorityElement {\n\n    public static int majorityElement(int[] nums) {\n        \/\/ Initialize variables to track the current candidate element and its count\n        int element = 0;\n        int count = 0;\n\n        \/\/ Traverse the array\n        for (int num : nums) {\n            \/\/ If the count is 0, update the current element\n            if (count == 0) {\n                element = num;\n            }\n\n            \/\/ Update count based on whether the current element is equal to the candidate element\n            if (num == element) {\n                count++;\n            } \n          \telse {\n                count--;\n            }\n        }\n\n        \/\/ Check if the candidate element is the majority element\n        int countCheck = 0;\n        for (int num : nums) {\n            if (num == element) {\n                countCheck++;\n            }\n        }\n\n        \/\/ If the count of the candidate element is greater than half the array size, it is the majority element\n        if (countCheck &gt; nums.length \/ 2) {\n            return element;\n        }\n\n        \/\/ If there is no major element, return -1\n        return -1;\n    }\n\n    public static void main(String[] args) {\n        \/\/ Example array\n        int[] nums = {3, 3, 4, 2, 4, 4, 2, 4, 4};\n\n        \/\/ Find the majority element using the function\n        int result = majorityElement(nums);\n\n        \/\/ Print the result\n        if (result != -1) {\n            System.out.println(&quot;The majority element is: &quot; + result);\n        } \n      \telse {\n            System.out.println(&quot;There is no majority element.&quot;);\n        }\n    }\n}<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Python Code<\/strong><\/h3>\n\n\n\n<p>You can implement the algorithm in Python too:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;python&quot;,&quot;mime&quot;:&quot;text\/x-python&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;Python&quot;,&quot;modeName&quot;:&quot;python&quot;}\">def majority_element(nums):\n    # Initialize variables to track the current candidate element and its count\n    element = 0\n    count = 0\n\n    # Traverse the array\n    for num in nums:\n        # If the count is 0, update the current element\n        if count == 0:\n            element = num\n\n        # Update count based on whether the current element is equal to the candidate element\n        if num == element:\n            count += 1\n        else:\n            count -= 1\n\n    # Check if the candidate element is the majority element\n    count_check = 0\n    for num in nums:\n        if num == element:\n            count_check += 1\n\n    # If the count of the candidate element is greater than half the array size, it is the majority element\n    if count_check &gt; len(nums) \/\/ 2:\n        return element\n\n    # If there is no major element, return -1\n    return -1\n\n# Example array\nnums = [3, 3, 4, 2, 4, 4, 2, 4, 4]\n\n# Find the majority element using the function\nresult = majority_element(nums)\n\n# Print the result\nif result != -1:\n    print(&quot;The majority element is:&quot;, result)\nelse:\n    print(&quot;There is no majority element.&quot;)<\/pre><\/div>\n\n\n\n<p><strong>Output:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code has-black-color has-text-color has-background\" style=\"background-color:#fedcba\"><code>The majority element is: 4<\/code><\/pre>\n\n\n\n<p>The time complexity for this approach is O(n) + O(n): O(n) for finding the potential majority element and another O(n) for checking whether it is the actual majority element or not.<\/p>\n\n\n\n<p>The space complexity for this approach is O(1) as we are not using any extra space.<\/p>\n\n\n\n<p>Below is a comparison of both methods:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td>&nbsp; Approach<\/td><td class=\"has-text-align-center\" data-align=\"center\">Time complexity<\/td><td class=\"has-text-align-center\" data-align=\"center\">&nbsp; &nbsp; Space&nbsp; complexity&nbsp;<\/td><td>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Detail<\/td><\/tr><tr><td>Hashmap approach<\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>O(n*logn) + O(n)<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>O(m)<\/strong><\/td><td>It takes logN time for insertion and we are doing it for n element in the array and O(n) for searching it.<br><\/td><\/tr><tr><td>Moore voting algorithm<\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>O(n) + O(n)<\/strong><\/td><td class=\"has-text-align-center\" data-align=\"center\"><strong>O(1)&nbsp;<\/strong><\/td><td>O(n) for finding the potential element and another O(n) for checking whether the it is the actual majority element or not.<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Conclusion<\/strong><\/h2>\n\n\n\n<p>In conclusion, the majority element <a href=\"https:\/\/leetcode.com\/problems\/majority-element\/\" target=\"_blank\" rel=\"noreferrer noopener nofollow\">leetcode problem<\/a> involves finding an element that occurs more than n\/2 times in an array. In this article, we have discussed two approaches with their time complexities and came to know that the Moore voting algorithm helps us to solve this problem in linear time complexity.\u00a0<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Understand the Majority Element leetcode problem, using Boyer-Moore majority vote algorithm with implementation in C++, Java, and Python.<\/p>\n","protected":false},"author":12,"featured_media":757,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jnews-multi-image_gallery":[],"jnews_single_post":null,"jnews_primary_category":{"id":"","hide":""},"footnotes":""},"categories":[7],"tags":[14,15],"class_list":["post-755","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structures-algorithms","tag-dsa","tag-leetcode"],"_links":{"self":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/755","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/users\/12"}],"replies":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/comments?post=755"}],"version-history":[{"count":8,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/755\/revisions"}],"predecessor-version":[{"id":872,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/755\/revisions\/872"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media\/757"}],"wp:attachment":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media?parent=755"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/categories?post=755"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/tags?post=755"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}