{"id":3523,"date":"2021-11-11T18:26:50","date_gmt":"2021-11-11T12:56:50","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=3523"},"modified":"2021-11-11T18:26:51","modified_gmt":"2021-11-11T12:56:51","slug":"largest-subarray-of-0s-and-1s","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/largest-subarray-of-0s-and-1s\/","title":{"rendered":"Largest Subarray of 0&#8217;s and 1&#8217;s"},"content":{"rendered":"\n<div class=\"gutentoc tocactive ullist\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"text_open\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#approach-1-brute-force\">Approach 1: Brute Force<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#approach-2-using-hashmap\">Approach 2: Using HashMap<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#faq\">FAQ<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<p>Given a binary array <strong>A[]<\/strong> consisting of 0\u2019s and 1\u2019s. The task is to return the length of the largest subarray which contains an equal number of 0\u2019s and 1\u2019s.<\/p>\n\n\n\n<p><strong>Examples:<\/strong><\/p>\n\n\n\n<p><strong>Input: <\/strong>A[]<strong> <\/strong>=[0, 1]<br><strong>Output: <\/strong>2<br><strong>Explanation: <\/strong>[0, 1] is the longest subarray with equal number of 0 and 1.<\/p>\n\n\n\n<p><strong>Input: <\/strong>&nbsp;A[] = [1, 0, 1, 1, 1, 0, 0]\n\n\n\n<p><strong>Output:<\/strong> 6<\/p>\n\n\n\n<p><strong>Explanation: <\/strong>[0, 1, 1, 1, 0, 0] is the longest subarray with equal number of 0s and 1s.<\/p>\n\n\n\n<h2 id=\"approach-1-brute-force\">Approach 1: Brute Force<\/h2>\n\n\n\n<p>The most naive approach is to simply generate all possible subarrays of the given array. Now, for each subarray, check whether the count of 0\u2019s and 1\u2019s are the same. If true, maximize the length.<\/p>\n\n\n\n<h3 id=\"c-code\"><span id=\"c-code-2\">C++ Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\"> int findMaxLength(int nums[], int n) {\n  int maxlen = 0;\n  for (int start = 0; start &lt; n; start++) {\n    int zeroes = 0, ones = 0;\n    for (int end = start; end &lt; n; end++) {\n      if (nums[end] == 0) {\n        zeroes++;\n      } else {\n        ones++;\n      }\n      if (zeroes == ones) {\n        maxlen = max(maxlen, end - start + 1);\n      }\n    }\n  }\n  return maxlen;\n}<\/pre>\n\n\n\n<h3 id=\"java-code\"><span id=\"java-code-2\">Java Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public int findMaxLength(int[] nums) {\n  int maxlen = 0;\n  for (int start = 0; start &lt; nums.length; start++) {\n    int zeroes = 0, ones = 0;\n    for (int end = start; end &lt; nums.length; end++) {\n      if (nums[end] == 0) {\n        zeroes++;\n      } else {\n        ones++;\n      }\n      if (zeroes == ones) {\n        maxlen = Math.max(maxlen, end - start + 1);\n      }\n    }\n  }\n  return maxlen;\n}<\/pre>\n\n\n\n<h3 id=\"python-code\"><span id=\"python-code-2\">Python Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def findMaxLength(nums):\n    maxlen = 0\n    for start in range(0, len(nums)):\n        zeroes = 0\n        ones = 0\n        for end in range(start, len(nums)):\n            if nums[end] == 0:\n                zeroes += 1\n            else:\n                ones += 1\n \n            if zeroes == ones:\n                maxlen = max(maxlen, end - start + 1)\n \n    return maxlen<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(N^2), where N is the size of the array A[]&nbsp;<\/p>\n\n\n\n<p><strong>Space Complexity:<\/strong> O(1), as no extra space is used.<\/p>\n\n\n\n<h2 id=\"approach-2-using-hashmap\">Approach 2: Using HashMap<\/h2>\n\n\n\n<p>The idea is to use a hashmap to store the count of 0\u2019s and 1\u2019s. At any moment, when the count of <strong>0<\/strong>s and <strong>1s<\/strong> are the same, maximize the length of the subarray.<br><br>Let us understand this approach with an example:<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"621\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Using HashMap\"  class=\"wp-image-3621 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Using-HashMap-1024x621.gif\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Using-HashMap-1024x621.gif 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Using-HashMap-300x182.gif 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Using-HashMap-768x466.gif 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Using-HashMap-380x231.gif 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Using-HashMap-550x334.gif 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Using-HashMap-800x485.gif 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Using-HashMap-1160x704.gif 1160w\" ><\/figure>\n\n\n\n<p><strong>Algorithm:<\/strong><\/p>\n\n\n\n<ul><li>Initialise a hashmap.<\/li><li>Initialise two variables <strong>maxLen = 0 <\/strong>and <strong>count = 0<\/strong>.<\/li><li>Traverse through the array and if the current element <strong>A[i]<\/strong> is <strong>1<\/strong>, increment the <strong>count<\/strong>, else decrement the value of <strong>count<\/strong>.<\/li><li>Now, check if the value of count is already present in the hashmap:<ul><li>If <strong>True<\/strong>, maximize the length of the subarray obtained so far.<\/li><\/ul><\/li><li>Else, insert <strong>(count, i)<\/strong> in the map.<\/li><li>Return the value of <strong>maximum length<\/strong> obtained.<br><\/li><\/ul>\n\n\n\n<p><strong>Implementation of the Approach:<\/strong><\/p>\n\n\n\n<h3 id=\"c-code\">C++ Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int findMaxLength(int nums[], int n) {\n  map &lt; int, int > map;\n  map.insert({0, -1});\n  int maxlen = 0, count = 0;\n  for (int i = 0; i &lt; n; i++) {\n    count = count + (nums[i] == 1 ? 1 : -1);\n    if (map.find(count) != map.end()) {\n      maxlen = max(maxlen, i - map.get(count));\n    } else {\n      map.insert({count, i});\n    }\n  }\n  return maxlen;\n}<\/pre>\n\n\n\n<h3 id=\"java-code\">Java Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public int findMaxLength(int[] nums) {\n  Map &lt; Integer, Integer > map = new HashMap &lt; > ();\n  map.put(0, -1);\n  int maxlen = 0, count = 0;\n  for (int i = 0; i &lt; nums.length; i++) {\n    count = count + (nums[i] == 1 ? 1 : -1);\n    if (map.containsKey(count)) {\n      maxlen = Math.max(maxlen, i - map.get(count));\n    } else {\n      map.put(count, i);\n    }\n  }\n  return maxlen;\n}<\/pre>\n\n\n\n<h3 id=\"python-code\">Python Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def findMaxLength(self, nums: List[int]) -> int:\n \n        count = 0\n        \n        map = { 0: -1}\n        \n        max_length = 0\n        \n        for i, number in enumerate( nums ):\n            if number:\n                count += 1\n            else:\n                count -= 1\n                \n            \n            if count in map:\n                max_length = max( max_length, ( i - map[count] ) )\n                \n            else:\n                map[ count ] = i\n                \n        return max_length<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(N), where N is the size of the array A[]&nbsp;<\/p>\n\n\n\n<p><strong>Space Complexity:<\/strong> O(N), as a map is used<\/p>\n\n\n\n<p><strong>Practice Questions:<\/strong><\/p>\n\n\n\n<p><a href=\"https:\/\/www.interviewbit.com\/problems\/max-sum-contiguous-subarray\/\" target=\"_blank\" rel=\"noreferrer noopener\">Max Sum Contiguous Subarray<\/a><\/p>\n\n\n\n<h2 id=\"faq\">FAQ<\/h2>\n\n\n\n<ul><li><strong>How to find the smallest subarray having equal number of 0s and 1s?<\/strong><br>Following the similar to finding the maximum length having equal zeroes and ones, we need to minimise the length.<\/li><\/ul>\n\n\n\n<ul><li><strong>What is the time and space complexity of the hashing approach?<\/strong><br>The time and space complexity of the hashmap approach is O(N).<\/li><\/ul>\n","protected":false},"excerpt":{"rendered":"Given a binary array A[] consisting of 0\u2019s and 1\u2019s. The task is to return the length of&hellip;\n","protected":false},"author":5,"featured_media":3619,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[549],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3523"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=3523"}],"version-history":[{"count":6,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3523\/revisions"}],"predecessor-version":[{"id":3686,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3523\/revisions\/3686"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/3619"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=3523"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=3523"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=3523"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}