{"id":3114,"date":"2024-03-03T07:00:00","date_gmt":"2024-03-03T07:00:00","guid":{"rendered":"https:\/\/favtutor.com\/articles\/?p=3114"},"modified":"2024-04-04T04:36:54","modified_gmt":"2024-04-04T04:36:54","slug":"maximum-consecutive-ones","status":"publish","type":"post","link":"https:\/\/favtutor.com\/articles\/maximum-consecutive-ones\/","title":{"rendered":"Maximum Consecutive Ones ( C++, Java, Python)"},"content":{"rendered":"\n<p>Arrays are the most basic data structures that must be mastered before any coding interview. There are a lot of leetcode questions about it, but here we will discuss how to Find the Maximum Consecutive Ones in a binary array based on binary numbers.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Maximum Consecutive Ones problem<\/strong><\/h2>\n\n\n\n<p><strong>In the Maximum Consecutive Ones problem, we are given a binary array (consisting of 1s and 0s) and we have to find the maximum consecutive 1s in the array. <\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/JEwltOdg4SAiREONEERHxQx-rm9zDZ_3GVuIz91HqvKKpZVuF3Xup2ub4TrcQUJKSzey-IF3sxMz-00FEUXRkjDLtM73yO5ZavoHbDUWYcJzgRggaH3NEqL0emCJIRGgD3z8QId3DO-UgQd2PiaOEx0\" alt=\"Maximum Consecutive Ones problem visualization\"\/><\/figure>\n\n\n\n<p>For example, the given array above is [ 1, 0, 0, 1, 1, 1, 0, 1]. Then, the maximum number of consecutive ones is 3 as shown below:<\/p>\n\n\n\n<p>This problem is very important when we need to manipulate arrays or real-world applications where binary sequences are involved.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution<\/strong><\/h2>\n\n\n\n<p>It is quite an easy problem at first glance! We just need to iterate over the array and keep adding consecutive ones. <\/p>\n\n\n\n<p>If we find 0 at any index compare the previous sum with the maximum consecutive 1s. If the previous sum exceeds the maximum consecutive 1s then update the maximum with the previous sum. Make the previous sum = 0 and repeat the same process.<\/p>\n\n\n\n<p>Let\u2019s take another example of understand this solution:<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/GbD3vR5nnldzX13ukZiKwXnoJ2zhJUe5Z75sQ-3ZW9IoIS6Sl5I7Y76vDkrMjighmSa8aVhOs8a3lTTqLV5fZCbr4fU4ihZ2omVVBAO1P5x38Lrr3izo-ZuVqYFdBXDAU7CRh9S75hoXyqzQ42dwtxs\" alt=\"Array\"\/><\/figure>\n\n\n\n<ul class=\"wp-block-list\">\n<li>First create two variables, the previous sum, and the maximum consecutive ones.&nbsp; Initialize both with 0.<\/li>\n\n\n\n<li>Now iterate over the array and if you find 1 then update our previous sum to previous sum + 1.<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/VDOXyvnTc5MW6LoLfuyR1ItPsz74eaoapj71x1abvn2AXK8oeguqc-cD5sh4cRhKjnkvUyCATn0HIJEBqwt9xeYT1_aJtmR6c4I_8MYsVIOaDtoDvKfeNfyJHsHcOdbzGe3ur2rWHPDHXYW9wKfw7W4\" alt=\"Previous Sum Array\"\/><\/figure>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Otherwise, update the previous sum = 0.<\/li>\n\n\n\n<li>At last, check if the maximum consecutive ones is less than the previous sum or not. If it is less update the maximum consecutive ones to the previous sum.<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/3k-a7t0ffSd-v97AO1IWm47I7Urt9-WX38AoLJROuuTqdlfE4G7WsHKGolI98atd2DjDXeybXFwyDaZuGislzG8pU8H0a-X8TxwdZWAFBATVpQ7oyyHydsrgcDO4WUZ5WEXfw_lzs6n_UqUqsfGjxCM\" alt=\"Maximum Consecutive Ones Array\"\/><\/figure>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Return the maximum consecutive ones at last.<\/li>\n<\/ul>\n\n\n\n<p>Finally, it&#8217;s time to implement it.<\/p>\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 maximum consecutive 1s in a binary 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;\n\nusing namespace std;\n\n\u00a0\u00a0\u00a0\u00a0int max_ones(vector&lt;int&gt;&amp; nums){\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int max_consecutive_ones=0, previous_sum=0;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0for(int i=0;i&lt;nums.size();i++){\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if(nums[i]==0) previous_sum=0;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0else {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0previous_sum++;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0max_consecutive_ones = max(max_consecutive_ones, previous_sum);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0return max_consecutive_ones;\n\n\u00a0\u00a0\u00a0\u00a0}\u00a0\n\nint main(){\n\n\u00a0\u00a0\u00a0\u00a0vector&lt;int&gt; nums = {1, 0, 0, 1, 1, 1, 0, 1};\n\n\u00a0\u00a0\u00a0\u00a0int result = max_ones(nums);\n\n\u00a0\u00a0\u00a0\u00a0cout&lt;&lt;&quot;Maximum Consecutive Ones in the array: &quot;&lt;&lt;result;\n\n\u00a0\u00a0\u00a0\u00a0return 0;\n\n}<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Java Code<\/strong><\/h3>\n\n\n\n<p>We can implement the solution in Java also:<\/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.*;\n\nclass Main {\n\n\u00a0\u00a0\u00a0\u00a0public static int maxOnes(List&lt;Integer&gt; nums) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int maxConsecutiveOnes = 0;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int previousSum = 0;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0for (int i = 0; i &lt; nums.size(); i++) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if (nums.get(i) == 0)\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0previousSum = 0;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0else {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0previousSum++;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0maxConsecutiveOnes = Math.max(maxConsecutiveOnes, previousSum);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0return maxConsecutiveOnes;\n\n\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0public static void main(String[] args) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0List&lt;Integer&gt; nums = new ArrayList&lt;&gt;(Arrays.asList(1, 0, 0, 1, 1, 1, 0, 1));\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int result = maxOnes(nums);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0System.out.println(&quot;Maximum Consecutive Ones in the array: &quot; + result);\n\n\u00a0\u00a0\u00a0\u00a0}\n\n}<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Python Code<\/strong><\/h3>\n\n\n\n<p>Below is the Python program for the solution:<\/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 max_ones(nums):\n\n\u00a0\u00a0\u00a0\u00a0max_consecutive_ones = 0\n\n\u00a0\u00a0\u00a0\u00a0previous_sum = 0\n\n\u00a0\u00a0\u00a0\u00a0for num in nums:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if num == 0:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0previous_sum = 0\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0else:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0previous_sum += 1\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0max_consecutive_ones = max(max_consecutive_ones, previous_sum)\n\n\u00a0\u00a0\u00a0\u00a0return max_consecutive_ones\n\ndef main():\n\n\u00a0\u00a0\u00a0\u00a0nums = [1, 0, 0, 1, 1, 1, 0, 1]\n\n\u00a0\u00a0\u00a0\u00a0result = max_ones(nums)\n\n\u00a0\u00a0\u00a0\u00a0print(&quot;Maximum Consecutive Ones in the array:&quot;, result)\n\nif __name__ == &quot;__main__&quot;:\n\n\u00a0\u00a0\u00a0\u00a0main()<\/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 has-link-color wp-elements-ac7e3ae75b59da2492b7a3dfb261f84e\" style=\"background-color:#fedcba\"><code>Maximum Consecutive Ones in the array: 3<\/code><\/pre>\n\n\n\n<p><strong>The time complexity to find the maximum consecutive ones in a binary array is O(n) where n is the size of the array.<\/strong> We are iterating the array once which took O(n) time complexity. The space complexity will be O(1) as we are not using any extra space.<\/p>\n\n\n\n<p>In programming competitions, such easy problems become tricky at first but if the participant can solve it efficiently, it demonstrates proficiency in algorithmic problem-solving skills. Here is a <a href=\"https:\/\/favtutor.com\/articles\/how-to-solve-1000-leetcode-problems\/\">guide to practising leetcode problems<\/a> to master the skills.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Conclusion<\/strong><\/h2>\n\n\n\n<p>In this article, we solved the <a href=\"https:\/\/leetcode.com\/problems\/max-consecutive-ones\/description\/\" target=\"_blank\" rel=\"noreferrer noopener nofollow\">leetcode problem<\/a> titled Maximum Consecutive Ones. Some similar array problems to try are <a href=\"https:\/\/favtutor.com\/articles\/find-minimum-in-rotated-sorted-array\/\">finding the minimum in a rotated sorted array<\/a>, <a href=\"https:\/\/favtutor.com\/articles\/maximum-product-subarray-problem\/\">finding the maximum product subarray<\/a>, and <a href=\"https:\/\/favtutor.com\/articles\/kth-largest-element\/\">finding kth largest element in an array<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>We will solve the leetcode problem to find the Maximum Consecutive Ones in a binary array, by implementing the solution in C++, Java, and Python.<\/p>\n","protected":false},"author":14,"featured_media":3117,"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":[145,14,15],"class_list":["post-3114","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structures-algorithms","tag-array","tag-dsa","tag-leetcode"],"_links":{"self":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/3114","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\/14"}],"replies":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/comments?post=3114"}],"version-history":[{"count":2,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/3114\/revisions"}],"predecessor-version":[{"id":3219,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/3114\/revisions\/3219"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media\/3117"}],"wp:attachment":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media?parent=3114"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/categories?post=3114"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/tags?post=3114"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}