{"id":15,"date":"2019-02-05T15:33:36","date_gmt":"2019-02-05T15:33:36","guid":{"rendered":"https:\/\/www.kindsonthegenius.com\/coding\/?p=15"},"modified":"2019-02-05T17:19:41","modified_gmt":"2019-02-05T17:19:41","slug":"question-3-sort-a-binary-array-in-linear-time","status":"publish","type":"post","link":"https:\/\/www.kindsonthegenius.com\/coding\/question-3-sort-a-binary-array-in-linear-time\/","title":{"rendered":"Question 3 &#8211; Sort a Binary Array in Linear Time"},"content":{"rendered":"<h4><strong>Question 3<\/strong><\/h4>\n<p>Given an unsorted binary array, you need to sort it in linear time &#8211; O(n) and constant space O(1).<\/p>\n<p><b>Input: <\/b>[0, 1, 1, 0, 1, 0, 0]<\/p>\n<p><b>Output<\/b>:[0, 0, 0, 0, 1, 1, 1]<\/p>\n<p>&nbsp;<\/p>\n<h4><strong>Best Solution<\/strong><\/h4>\n<p>Since the question clearly specifies that we sort in linear time and constant space, we simply would go directly to the solution.<\/p>\n<p>The approach is this: Iterate through the array and each time you encounter a zero, move it to the beginning. At the same time, keep count of the number of zeroes seen so far. At the end of the iteration, then fill the remaining part of the array with ones.<\/p>\n<p>This means that\u00a0 the total time taken is linear.<\/p>\n<p>The Python code is given below:<\/p>\n<p><!-- HTML generated using hilite.me --><\/p>\n<pre style=\"margin: 0; line-height: 125%;\"><span style=\"color: #888888;\"># **** SORT A BINARY ARRAY IN LINEAR TIME AND CONSTANT SPACE ****<\/span>\r\n\r\n<span style=\"color: #008800; font-weight: bold;\">def<\/span> <span style=\"color: #0066bb; font-weight: bold;\">sortBinaryArray<\/span>(a):\r\n    j <span style=\"color: #333333;\">=<\/span> <span style=\"color: #0000dd; font-weight: bold;\">0<\/span> <span style=\"color: #888888;\"># number of zeroes so far<\/span>\r\n    i <span style=\"color: #333333;\">=<\/span> <span style=\"color: #0000dd; font-weight: bold;\">0<\/span> <span style=\"color: #888888;\"># loop variable<\/span>\r\n    <span style=\"color: #008800; font-weight: bold;\">while<\/span>(i <span style=\"color: #333333;\">!=<\/span> <span style=\"color: #007020;\">len<\/span>(a)):\r\n        <span style=\"color: #008800; font-weight: bold;\">if<\/span>(a[i] <span style=\"color: #333333;\">==<\/span> <span style=\"color: #0000dd; font-weight: bold;\">0<\/span>):\r\n            a[j] <span style=\"color: #333333;\">=<\/span> <span style=\"color: #0000dd; font-weight: bold;\">0<\/span>\r\n            j <span style=\"color: #333333;\">=<\/span> j <span style=\"color: #333333;\">+<\/span> <span style=\"color: #0000dd; font-weight: bold;\">1<\/span>\r\n        i <span style=\"color: #333333;\">=<\/span> i <span style=\"color: #333333;\">+<\/span> <span style=\"color: #0000dd; font-weight: bold;\">1<\/span>\r\n\r\n    <span style=\"color: #008800; font-weight: bold;\">for<\/span> i <span style=\"color: #000000; font-weight: bold;\">in<\/span> <span style=\"color: #007020;\">range<\/span>(j<span style=\"color: #333333;\">+<\/span><span style=\"color: #0000dd; font-weight: bold;\">1<\/span>, <span style=\"color: #007020;\">len<\/span>(a)):\r\n        a[i] <span style=\"color: #333333;\">=<\/span> <span style=\"color: #0000dd; font-weight: bold;\">1<\/span>\r\n\r\nar <span style=\"color: #333333;\">=<\/span> [<span style=\"color: #0000dd; font-weight: bold;\">0<\/span>, <span style=\"color: #0000dd; font-weight: bold;\">1<\/span>, <span style=\"color: #0000dd; font-weight: bold;\">1<\/span>, <span style=\"color: #0000dd; font-weight: bold;\">0<\/span>, <span style=\"color: #0000dd; font-weight: bold;\">1<\/span>, <span style=\"color: #0000dd; font-weight: bold;\">0<\/span>, <span style=\"color: #0000dd; font-weight: bold;\">0<\/span>]\r\n<span style=\"color: #007020;\">print<\/span>(ar)\r\nsortBinaryArray(ar)\r\n<span style=\"color: #007020;\">print<\/span>(ar)\r\n<\/pre>\n<p>&nbsp;<\/p>\n<h4><strong>Video Explanation<\/strong><\/h4>\n<p><iframe loading=\"lazy\" width=\"100%\" height=\"315\" src=\"https:\/\/www.youtube.com\/embed\/v2uFtXMk7VY\" frameborder=\"0\" allow=\"accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen><\/iframe>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Question 3 Given an unsorted binary array, you need to sort it in linear time &#8211; O(n) and constant space O(1). Input: [0, 1, 1, &hellip; <\/p>\n","protected":false},"author":395,"featured_media":19,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8,2,6,14],"tags":[],"class_list":["post-15","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-array","category-coding-challenge","category-python","category-sorting"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v27.6 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>Question 3 - Sort a Binary Array in Linear Time - Coding Challenge<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/www.kindsonthegenius.com\/coding\/question-3-sort-a-binary-array-in-linear-time\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Question 3 - Sort a Binary Array in Linear Time - Coding Challenge\" \/>\n<meta property=\"og:description\" content=\"Question 3 Given an unsorted binary array, you need to sort it in linear time &#8211; O(n) and constant space O(1). Input: [0, 1, 1, &hellip;\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.kindsonthegenius.com\/coding\/question-3-sort-a-binary-array-in-linear-time\/\" \/>\n<meta property=\"og:site_name\" content=\"Coding Challenge\" \/>\n<meta property=\"article:published_time\" content=\"2019-02-05T15:33:36+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2019-02-05T17:19:41+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/www.kindsonthegenius.com\/coding\/wp-content\/uploads\/sites\/4\/2019\/02\/Sort-a-Binary-Array-Python.jpg\" \/>\n\t<meta property=\"og:image:width\" content=\"1005\" \/>\n\t<meta property=\"og:image:height\" content=\"544\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/jpeg\" \/>\n<meta name=\"author\" content=\"kindsonthegenius\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"kindsonthegenius\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"1 minute\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/www.kindsonthegenius.com\\\/coding\\\/question-3-sort-a-binary-array-in-linear-time\\\/#article\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/www.kindsonthegenius.com\\\/coding\\\/question-3-sort-a-binary-array-in-linear-time\\\/\"},\"author\":{\"name\":\"kindsonthegenius\",\"@id\":\"https:\\\/\\\/www.kindsonthegenius.com\\\/coding\\\/#\\\/schema\\\/person\\\/63a68934672db675ff0cd80d066510c2\"},\"headline\":\"Question 3 &#8211; Sort a Binary Array in Linear Time\",\"datePublished\":\"2019-02-05T15:33:36+00:00\",\"dateModified\":\"2019-02-05T17:19:41+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/www.kindsonthegenius.com\\\/coding\\\/question-3-sort-a-binary-array-in-linear-time\\\/\"},\"wordCount\":126,\"commentCount\":0,\"image\":{\"@id\":\"https:\\\/\\\/www.kindsonthegenius.com\\\/coding\\\/question-3-sort-a-binary-array-in-linear-time\\\/#primaryimage\"},\"thumbnailUrl\":\"https:\\\/\\\/www.kindsonthegenius.com\\\/coding\\\/wp-content\\\/uploads\\\/sites\\\/4\\\/2019\\\/02\\\/Sort-a-Binary-Array-Python.jpg\",\"articleSection\":[\"Array\",\"Coding Challenge\",\"Python\",\"Sorting\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\\\/\\\/www.kindsonthegenius.com\\\/coding\\\/question-3-sort-a-binary-array-in-linear-time\\\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/www.kindsonthegenius.com\\\/coding\\\/question-3-sort-a-binary-array-in-linear-time\\\/\",\"url\":\"https:\\\/\\\/www.kindsonthegenius.com\\\/coding\\\/question-3-sort-a-binary-array-in-linear-time\\\/\",\"name\":\"Question 3 - Sort a Binary Array in Linear Time - Coding Challenge\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/www.kindsonthegenius.com\\\/coding\\\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\\\/\\\/www.kindsonthegenius.com\\\/coding\\\/question-3-sort-a-binary-array-in-linear-time\\\/#primaryimage\"},\"image\":{\"@id\":\"https:\\\/\\\/www.kindsonthegenius.com\\\/coding\\\/question-3-sort-a-binary-array-in-linear-time\\\/#primaryimage\"},\"thumbnailUrl\":\"https:\\\/\\\/www.kindsonthegenius.com\\\/coding\\\/wp-content\\\/uploads\\\/sites\\\/4\\\/2019\\\/02\\\/Sort-a-Binary-Array-Python.jpg\",\"datePublished\":\"2019-02-05T15:33:36+00:00\",\"dateModified\":\"2019-02-05T17:19:41+00:00\",\"author\":{\"@id\":\"https:\\\/\\\/www.kindsonthegenius.com\\\/coding\\\/#\\\/schema\\\/person\\\/63a68934672db675ff0cd80d066510c2\"},\"breadcrumb\":{\"@id\":\"https:\\\/\\\/www.kindsonthegenius.com\\\/coding\\\/question-3-sort-a-binary-array-in-linear-time\\\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/www.kindsonthegenius.com\\\/coding\\\/question-3-sort-a-binary-array-in-linear-time\\\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/www.kindsonthegenius.com\\\/coding\\\/question-3-sort-a-binary-array-in-linear-time\\\/#primaryimage\",\"url\":\"https:\\\/\\\/www.kindsonthegenius.com\\\/coding\\\/wp-content\\\/uploads\\\/sites\\\/4\\\/2019\\\/02\\\/Sort-a-Binary-Array-Python.jpg\",\"contentUrl\":\"https:\\\/\\\/www.kindsonthegenius.com\\\/coding\\\/wp-content\\\/uploads\\\/sites\\\/4\\\/2019\\\/02\\\/Sort-a-Binary-Array-Python.jpg\",\"width\":1005,\"height\":544,\"caption\":\"Sort a Binary array\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/www.kindsonthegenius.com\\\/coding\\\/question-3-sort-a-binary-array-in-linear-time\\\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\\\/\\\/www.kindsonthegenius.com\\\/coding\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Question 3 &#8211; Sort a Binary Array in Linear Time\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/www.kindsonthegenius.com\\\/coding\\\/#website\",\"url\":\"https:\\\/\\\/www.kindsonthegenius.com\\\/coding\\\/\",\"name\":\"Coding Challenge\",\"description\":\"\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/www.kindsonthegenius.com\\\/coding\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Person\",\"@id\":\"https:\\\/\\\/www.kindsonthegenius.com\\\/coding\\\/#\\\/schema\\\/person\\\/63a68934672db675ff0cd80d066510c2\",\"name\":\"kindsonthegenius\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/3079a7f663b02e801d03cd075852a037af36bd179b5fbcd0603bae3dd7833a9b?s=96&d=mm&r=g\",\"url\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/3079a7f663b02e801d03cd075852a037af36bd179b5fbcd0603bae3dd7833a9b?s=96&d=mm&r=g\",\"contentUrl\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/3079a7f663b02e801d03cd075852a037af36bd179b5fbcd0603bae3dd7833a9b?s=96&d=mm&r=g\",\"caption\":\"kindsonthegenius\"},\"url\":\"https:\\\/\\\/www.kindsonthegenius.com\\\/coding\\\/author\\\/kindsonthegenius-2\\\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Question 3 - Sort a Binary Array in Linear Time - Coding Challenge","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/www.kindsonthegenius.com\/coding\/question-3-sort-a-binary-array-in-linear-time\/","og_locale":"en_US","og_type":"article","og_title":"Question 3 - Sort a Binary Array in Linear Time - Coding Challenge","og_description":"Question 3 Given an unsorted binary array, you need to sort it in linear time &#8211; O(n) and constant space O(1). Input: [0, 1, 1, &hellip;","og_url":"https:\/\/www.kindsonthegenius.com\/coding\/question-3-sort-a-binary-array-in-linear-time\/","og_site_name":"Coding Challenge","article_published_time":"2019-02-05T15:33:36+00:00","article_modified_time":"2019-02-05T17:19:41+00:00","og_image":[{"width":1005,"height":544,"url":"https:\/\/www.kindsonthegenius.com\/coding\/wp-content\/uploads\/sites\/4\/2019\/02\/Sort-a-Binary-Array-Python.jpg","type":"image\/jpeg"}],"author":"kindsonthegenius","twitter_card":"summary_large_image","twitter_misc":{"Written by":"kindsonthegenius","Est. reading time":"1 minute"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/www.kindsonthegenius.com\/coding\/question-3-sort-a-binary-array-in-linear-time\/#article","isPartOf":{"@id":"https:\/\/www.kindsonthegenius.com\/coding\/question-3-sort-a-binary-array-in-linear-time\/"},"author":{"name":"kindsonthegenius","@id":"https:\/\/www.kindsonthegenius.com\/coding\/#\/schema\/person\/63a68934672db675ff0cd80d066510c2"},"headline":"Question 3 &#8211; Sort a Binary Array in Linear Time","datePublished":"2019-02-05T15:33:36+00:00","dateModified":"2019-02-05T17:19:41+00:00","mainEntityOfPage":{"@id":"https:\/\/www.kindsonthegenius.com\/coding\/question-3-sort-a-binary-array-in-linear-time\/"},"wordCount":126,"commentCount":0,"image":{"@id":"https:\/\/www.kindsonthegenius.com\/coding\/question-3-sort-a-binary-array-in-linear-time\/#primaryimage"},"thumbnailUrl":"https:\/\/www.kindsonthegenius.com\/coding\/wp-content\/uploads\/sites\/4\/2019\/02\/Sort-a-Binary-Array-Python.jpg","articleSection":["Array","Coding Challenge","Python","Sorting"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/www.kindsonthegenius.com\/coding\/question-3-sort-a-binary-array-in-linear-time\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/www.kindsonthegenius.com\/coding\/question-3-sort-a-binary-array-in-linear-time\/","url":"https:\/\/www.kindsonthegenius.com\/coding\/question-3-sort-a-binary-array-in-linear-time\/","name":"Question 3 - Sort a Binary Array in Linear Time - Coding Challenge","isPartOf":{"@id":"https:\/\/www.kindsonthegenius.com\/coding\/#website"},"primaryImageOfPage":{"@id":"https:\/\/www.kindsonthegenius.com\/coding\/question-3-sort-a-binary-array-in-linear-time\/#primaryimage"},"image":{"@id":"https:\/\/www.kindsonthegenius.com\/coding\/question-3-sort-a-binary-array-in-linear-time\/#primaryimage"},"thumbnailUrl":"https:\/\/www.kindsonthegenius.com\/coding\/wp-content\/uploads\/sites\/4\/2019\/02\/Sort-a-Binary-Array-Python.jpg","datePublished":"2019-02-05T15:33:36+00:00","dateModified":"2019-02-05T17:19:41+00:00","author":{"@id":"https:\/\/www.kindsonthegenius.com\/coding\/#\/schema\/person\/63a68934672db675ff0cd80d066510c2"},"breadcrumb":{"@id":"https:\/\/www.kindsonthegenius.com\/coding\/question-3-sort-a-binary-array-in-linear-time\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.kindsonthegenius.com\/coding\/question-3-sort-a-binary-array-in-linear-time\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/www.kindsonthegenius.com\/coding\/question-3-sort-a-binary-array-in-linear-time\/#primaryimage","url":"https:\/\/www.kindsonthegenius.com\/coding\/wp-content\/uploads\/sites\/4\/2019\/02\/Sort-a-Binary-Array-Python.jpg","contentUrl":"https:\/\/www.kindsonthegenius.com\/coding\/wp-content\/uploads\/sites\/4\/2019\/02\/Sort-a-Binary-Array-Python.jpg","width":1005,"height":544,"caption":"Sort a Binary array"},{"@type":"BreadcrumbList","@id":"https:\/\/www.kindsonthegenius.com\/coding\/question-3-sort-a-binary-array-in-linear-time\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/www.kindsonthegenius.com\/coding\/"},{"@type":"ListItem","position":2,"name":"Question 3 &#8211; Sort a Binary Array in Linear Time"}]},{"@type":"WebSite","@id":"https:\/\/www.kindsonthegenius.com\/coding\/#website","url":"https:\/\/www.kindsonthegenius.com\/coding\/","name":"Coding Challenge","description":"","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/www.kindsonthegenius.com\/coding\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Person","@id":"https:\/\/www.kindsonthegenius.com\/coding\/#\/schema\/person\/63a68934672db675ff0cd80d066510c2","name":"kindsonthegenius","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/secure.gravatar.com\/avatar\/3079a7f663b02e801d03cd075852a037af36bd179b5fbcd0603bae3dd7833a9b?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/3079a7f663b02e801d03cd075852a037af36bd179b5fbcd0603bae3dd7833a9b?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/3079a7f663b02e801d03cd075852a037af36bd179b5fbcd0603bae3dd7833a9b?s=96&d=mm&r=g","caption":"kindsonthegenius"},"url":"https:\/\/www.kindsonthegenius.com\/coding\/author\/kindsonthegenius-2\/"}]}},"_links":{"self":[{"href":"https:\/\/www.kindsonthegenius.com\/coding\/wp-json\/wp\/v2\/posts\/15","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.kindsonthegenius.com\/coding\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.kindsonthegenius.com\/coding\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.kindsonthegenius.com\/coding\/wp-json\/wp\/v2\/users\/395"}],"replies":[{"embeddable":true,"href":"https:\/\/www.kindsonthegenius.com\/coding\/wp-json\/wp\/v2\/comments?post=15"}],"version-history":[{"count":4,"href":"https:\/\/www.kindsonthegenius.com\/coding\/wp-json\/wp\/v2\/posts\/15\/revisions"}],"predecessor-version":[{"id":21,"href":"https:\/\/www.kindsonthegenius.com\/coding\/wp-json\/wp\/v2\/posts\/15\/revisions\/21"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.kindsonthegenius.com\/coding\/wp-json\/wp\/v2\/media\/19"}],"wp:attachment":[{"href":"https:\/\/www.kindsonthegenius.com\/coding\/wp-json\/wp\/v2\/media?parent=15"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.kindsonthegenius.com\/coding\/wp-json\/wp\/v2\/categories?post=15"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.kindsonthegenius.com\/coding\/wp-json\/wp\/v2\/tags?post=15"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}