{"id":3411,"date":"2017-12-16T13:08:16","date_gmt":"2017-12-16T07:38:16","guid":{"rendered":"http:\/\/theoryofprogramming.azurewebsites.net\/?p=3411"},"modified":"2017-12-16T13:08:16","modified_gmt":"2017-12-16T07:38:16","slug":"find-majority-element-array","status":"publish","type":"post","link":"https:\/\/theoryofcoding.com\/index.php\/2017\/12\/16\/find-majority-element-array\/","title":{"rendered":"Find the majority element in an array"},"content":{"rendered":"<p><b>Problem statement<\/b> &#8211; Given an unsorted array, find the majority element (element which occurs for more than N\/2 times).<br \/>\n<b>Clues<\/b> &#8211;<\/p>\n<ul>\n<li>Solution must be O(N) in time and O(1) in space.<\/li>\n<li>If the majority element exists, there will only be one such element. How can we find it?<\/li>\n<\/ul>\n<p><b>Solution<\/b> &#8211; We can do this in O(N) time by the Boyer\u2013Moore majority voting algorithm. It is a simple 3-step algorithm \u2013<\/p>\n<div class=\"su-list su-list-style-\">\n<ul>\n<li><b>Initialization<\/b> \u2013 We will take 2 variables, \u2018<em>candidate<\/em>\u2019 and \u2018<em>votes<\/em>\u2019 and set them to 0.<\/li>\n<li><b>Voting<\/b> \u2013 Traverse through the array once. If votes is 0, then we set <em>candidate<\/em> to the current element. We will also check, if the current element (<em>arr[i]<\/em>) is equal to the candidate, if yes, increment <em>votes<\/em>, else decrement.<\/li>\n<li><b>Checking the winning candidate<\/b> \u2013 After Step 2, we will compute the frequency of the value in candidate. If this is more than N\/2, then the candidate is the majority element, otherwise, the majority element does not exist.<\/li>\n<\/ul>\n<p>So this is kind of like picking a candidate and computing how many votes he has. You may not understand it in the first glance, but try reading the logic two more times and try to write the pseudo-code for this. Believe me, this is a ridiculously simple algorithm!<\/p>\n<\/div>\n<p><b>Code<\/b> &#8211;<\/p>\n<pre class=\"brush: cpp; title: ; notranslate\" title=\"\">\n\/\/ Moore's Majority Voting Algorithm procedure\n\/\/ Computes the majority element in O(N) time\n\/\/ Returns the majority element\n\/\/ If no majority element, returns INT_MIN\nint majorityElement(int arr&#x5B;], int length)\n{\n    int votes = 0, candidate = -1, i;\n     \n        \/\/ Voting\n    for (i = 0; i &lt; length; ++i) {\n        if (votes == 0) {\n            candidate = arr&#x5B;i];\n        }\n         \n        if (candidate == arr&#x5B;i]) {\n            ++votes;\n        } else {\n            --votes;\n        }\n    }\n     \n    votes = 0;\n     \n    \/\/ Get freq. of candidate\n    for (i = 0; i &lt; length; ++i) { if (arr&#x5B;i] == candidate) { ++votes; } } \/\/ Verify if the candidate \/\/ is the majority element if (votes &gt; length \/ 2) {\n        return candidate;\n    } else {\n        return INT_MIN;\n    }\n}\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Given an unsorted array, find the majority element. Majority element is defined as that element which occurs for more than N\/2 times. If the majority element exists, there will only be one such element. We can do this in O(N) time by the Boyer\u2013Moore majority voting algorithm.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[16],"tags":[20,22,61],"class_list":["post-3411","post","type-post","status-publish","format-standard","hentry","category-array-interview-questions","tag-arrays","tag-arrays-interview-questions","tag-interview-questions"],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/posts\/3411","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/comments?post=3411"}],"version-history":[{"count":0,"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/posts\/3411\/revisions"}],"wp:attachment":[{"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/media?parent=3411"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/categories?post=3411"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/tags?post=3411"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}