{"id":32973,"date":"2023-02-03T10:25:49","date_gmt":"2023-02-03T04:55:49","guid":{"rendered":"https:\/\/jassweb.com\/solved\/solved-how-to-find-the-minimal-missing-integer-in-a-list-in-an-stl-way\/"},"modified":"2023-02-03T10:25:49","modified_gmt":"2023-02-03T04:55:49","slug":"solved-how-to-find-the-minimal-missing-integer-in-a-list-in-an-stl-way","status":"publish","type":"post","link":"https:\/\/jassweb.com\/solved\/solved-how-to-find-the-minimal-missing-integer-in-a-list-in-an-stl-way\/","title":{"rendered":"[Solved] How to find the minimal missing integer in a list in an STL way"},"content":{"rendered":"

[ad_1]
\n<\/p>\n

\n
\n
<\/div>\n
\n
\n

You can do this by building a set of integers and adding larger seen in the set, and holding the minimum not seen in as a counter. Once there is a number that is equal to the latter, go through the set removing elements until there is a missing integer.<\/p>\n

Please see below for implementation.<\/p>\n

template<typename I> typename I::value_type solver(I b, I e)\n{\n    constexpr typename I::value_type maxseen=\n      std::numeric_limits<typename I::value_type>::max();\n    std::set<typename I::value_type> seen{maxseen};\n\n    typename I::value_type minnotseen(1);\n\n    for(I p=b; p!=e;++p)\n    {\n        if(*p == minnotseen)\n        {\n            while(++minnotseen == *seen.begin())\n            {\n                seen.erase(seen.begin());\n            }\n\n        } else if( *p > minnotseen)\n        {\n            seen.insert(*p);\n        }\n    }\n\n    return minnotseen;\n}\n<\/code><\/pre>\n
In case you sequence is in a vector you should use this with:<\/p>\n
solver(sequence.begin(),sequence.end());\n<\/code><\/pre>\n
The algorithm is O(N) in time and O(1) in space since it uses only a counter, constant size additional space, and a few iterators to keep track of the least value.<\/p>\n
Complexity ( order of growth rate ) The algorithm keeps a subset only of the input which is expected to be of constant order of growth with respect the growth rate of the input, thus O(1) in space. The growth rate of the iterations is O(N+NlogK) where K is  the growth rate of the larger subsequence of seen larger numbers. The latter is the aforementioned subsequence of constant growth rate i.e. K=1 , which results in the algorithm having O(N) complexity.<\/em> (see comments)<\/p>\n<\/p><\/div>\n
<\/div>\n<\/div>\n
            17<\/span> <\/p><\/div>\n<\/div>\n
[ad_2]<\/p>\n
solved How to find the minimal missing integer in a list in an STL way <\/p>\n","protected":false},"excerpt":{"rendered":"
[ad_1] You can do this by building a set of integers and adding larger seen in the set, and holding the minimum not seen in as a counter. Once there is a number that is equal to the latter, go through the set removing elements until there is a missing integer. Please see below for … Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[320],"tags":[457,324,761],"class_list":["post-32973","post","type-post","status-publish","format-standard","hentry","category-solved","tag-algorithm","tag-c","tag-stl"],"yoast_head":"\n[Solved] How to find the minimal missing integer in a list in an STL way - JassWeb<\/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:\/\/jassweb.com\/solved\/solved-how-to-find-the-minimal-missing-integer-in-a-list-in-an-stl-way\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"[Solved] How to find the minimal missing integer in a list in an STL way - JassWeb\" \/>\n<meta property=\"og:description\" content=\"[ad_1] You can do this by building a set of integers and adding larger seen in the set, and holding the minimum not seen in as a counter. Once there is a number that is equal to the latter, go through the set removing elements until there is a missing integer. Please see below for ... Read more\" \/>\n<meta property=\"og:url\" content=\"https:\/\/jassweb.com\/solved\/solved-how-to-find-the-minimal-missing-integer-in-a-list-in-an-stl-way\/\" \/>\n<meta property=\"og:site_name\" content=\"JassWeb\" \/>\n<meta property=\"article:published_time\" content=\"2023-02-03T04:55:49+00:00\" \/>\n<meta name=\"author\" content=\"Kirat\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Kirat\" \/>\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:\/\/jassweb.com\/solved\/solved-how-to-find-the-minimal-missing-integer-in-a-list-in-an-stl-way\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-how-to-find-the-minimal-missing-integer-in-a-list-in-an-stl-way\/\"},\"author\":{\"name\":\"Kirat\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31\"},\"headline\":\"[Solved] How to find the minimal missing integer in a list in an STL way\",\"datePublished\":\"2023-02-03T04:55:49+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-how-to-find-the-minimal-missing-integer-in-a-list-in-an-stl-way\/\"},\"wordCount\":216,\"publisher\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\"},\"keywords\":[\"algorithm\",\"c++\",\"stl\"],\"articleSection\":[\"Solved\"],\"inLanguage\":\"en-US\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-how-to-find-the-minimal-missing-integer-in-a-list-in-an-stl-way\/\",\"url\":\"https:\/\/jassweb.com\/solved\/solved-how-to-find-the-minimal-missing-integer-in-a-list-in-an-stl-way\/\",\"name\":\"[Solved] How to find the minimal missing integer in a list in an STL way - JassWeb\",\"isPartOf\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#website\"},\"datePublished\":\"2023-02-03T04:55:49+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-how-to-find-the-minimal-missing-integer-in-a-list-in-an-stl-way\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/jassweb.com\/solved\/solved-how-to-find-the-minimal-missing-integer-in-a-list-in-an-stl-way\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-how-to-find-the-minimal-missing-integer-in-a-list-in-an-stl-way\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/jassweb.com\/solved\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"[Solved] How to find the minimal missing integer in a list in an STL way\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/jassweb.com\/solved\/#website\",\"url\":\"https:\/\/jassweb.com\/solved\/\",\"name\":\"JassWeb\",\"description\":\"Build High-quality Websites\",\"publisher\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/jassweb.com\/solved\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\",\"name\":\"Jass Web\",\"url\":\"https:\/\/jassweb.com\/solved\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png\",\"contentUrl\":\"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png\",\"width\":693,\"height\":132,\"caption\":\"Jass Web\"},\"image\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/\"}},{\"@type\":\"Person\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31\",\"name\":\"Kirat\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1775798750\",\"contentUrl\":\"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1775798750\",\"caption\":\"Kirat\"},\"sameAs\":[\"http:\/\/jassweb.com\"],\"url\":\"https:\/\/jassweb.com\/solved\/author\/jaspritsinghghumangmail-com\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"[Solved] How to find the minimal missing integer in a list in an STL way - JassWeb","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:\/\/jassweb.com\/solved\/solved-how-to-find-the-minimal-missing-integer-in-a-list-in-an-stl-way\/","og_locale":"en_US","og_type":"article","og_title":"[Solved] How to find the minimal missing integer in a list in an STL way - JassWeb","og_description":"[ad_1] You can do this by building a set of integers and adding larger seen in the set, and holding the minimum not seen in as a counter. Once there is a number that is equal to the latter, go through the set removing elements until there is a missing integer. Please see below for ... Read more","og_url":"https:\/\/jassweb.com\/solved\/solved-how-to-find-the-minimal-missing-integer-in-a-list-in-an-stl-way\/","og_site_name":"JassWeb","article_published_time":"2023-02-03T04:55:49+00:00","author":"Kirat","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Kirat","Est. reading time":"1 minute"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/jassweb.com\/solved\/solved-how-to-find-the-minimal-missing-integer-in-a-list-in-an-stl-way\/#article","isPartOf":{"@id":"https:\/\/jassweb.com\/solved\/solved-how-to-find-the-minimal-missing-integer-in-a-list-in-an-stl-way\/"},"author":{"name":"Kirat","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31"},"headline":"[Solved] How to find the minimal missing integer in a list in an STL way","datePublished":"2023-02-03T04:55:49+00:00","mainEntityOfPage":{"@id":"https:\/\/jassweb.com\/solved\/solved-how-to-find-the-minimal-missing-integer-in-a-list-in-an-stl-way\/"},"wordCount":216,"publisher":{"@id":"https:\/\/jassweb.com\/solved\/#organization"},"keywords":["algorithm","c++","stl"],"articleSection":["Solved"],"inLanguage":"en-US"},{"@type":"WebPage","@id":"https:\/\/jassweb.com\/solved\/solved-how-to-find-the-minimal-missing-integer-in-a-list-in-an-stl-way\/","url":"https:\/\/jassweb.com\/solved\/solved-how-to-find-the-minimal-missing-integer-in-a-list-in-an-stl-way\/","name":"[Solved] How to find the minimal missing integer in a list in an STL way - JassWeb","isPartOf":{"@id":"https:\/\/jassweb.com\/solved\/#website"},"datePublished":"2023-02-03T04:55:49+00:00","breadcrumb":{"@id":"https:\/\/jassweb.com\/solved\/solved-how-to-find-the-minimal-missing-integer-in-a-list-in-an-stl-way\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/jassweb.com\/solved\/solved-how-to-find-the-minimal-missing-integer-in-a-list-in-an-stl-way\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/jassweb.com\/solved\/solved-how-to-find-the-minimal-missing-integer-in-a-list-in-an-stl-way\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/jassweb.com\/solved\/"},{"@type":"ListItem","position":2,"name":"[Solved] How to find the minimal missing integer in a list in an STL way"}]},{"@type":"WebSite","@id":"https:\/\/jassweb.com\/solved\/#website","url":"https:\/\/jassweb.com\/solved\/","name":"JassWeb","description":"Build High-quality Websites","publisher":{"@id":"https:\/\/jassweb.com\/solved\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/jassweb.com\/solved\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/jassweb.com\/solved\/#organization","name":"Jass Web","url":"https:\/\/jassweb.com\/solved\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/","url":"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png","contentUrl":"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png","width":693,"height":132,"caption":"Jass Web"},"image":{"@id":"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/"}},{"@type":"Person","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31","name":"Kirat","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/image\/","url":"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1775798750","contentUrl":"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1775798750","caption":"Kirat"},"sameAs":["http:\/\/jassweb.com"],"url":"https:\/\/jassweb.com\/solved\/author\/jaspritsinghghumangmail-com\/"}]}},"_links":{"self":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts\/32973","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/comments?post=32973"}],"version-history":[{"count":0,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts\/32973\/revisions"}],"wp:attachment":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/media?parent=32973"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/categories?post=32973"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/tags?post=32973"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}