Recently I came across a . I found it interesting enough to post here. Codility demo task At first, I wanted to use a , tracking the minimum positive integer . Take the following array: [1, 3, 6, 4, 1, 2]. Let’s iterate it. The first number is 1. So the minimum integer that is not in this array so far is 2. Then there is 3. So the minimum integer that is not in this array so far is still 2. Everything’s great until I finally encounter 2 in the end of this array. So how am I supposed to come up with an answer — 5 — with this approach? Well, I’m afraid it simply doesn’t work here. So it became obvious that I need to remember somehow all the encountered numbers. greedy algorithm so far What is the best way to spot them? The approach that comes to mind first is to have some pattern array, kinda sieve, the one that contains all the positive integers within a given interval. And it would be very handy if its keys would coincide with values. So with every integer I encounter in input array I find a corresponding key in a pattern array, and mark its value as, say, null: $pattern = (0, 100000); range ($a $value) {$pattern[$value] = ;} foreach as null After that all I need is to iterate it and find the first key with a non-null value. But before that I want to make sure that I won’t get 0 as an answer since it’s not a positive integer. So I unset the first element in my pattern array. And there is an edge case. What happens if I get all the integers within a given interval, [1, 100000]? The answer should be 100001. So I create a pattern array with the equals to 100001: supremum solution( $a) {$pattern = (0, 100001); function array range **foreach** ($a **as** $value) { $pattern\[$value\] = **null**; } **unset**($pattern\[0\]); **for** ($i = 1; $i <= _count_($pattern); $i++) { **if** (!_is\_null_($pattern\[$i\])) { **return** $i; } } } Voilà!
