The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. ― Donald E. Knuth

# Algorithms

## Arrays & Strings

Problem :-
Find the smallest positive element missing in the given array of size 'n' consisting of both positive & negative integers.
Consider the array { -8, 3, 2, -4, 6, 1, 5 } .
Smallest positive element missing in the array is 4.

Solution :-
We might think of an approach in which we start searching the array for positive integers starting from 1 and look for the first missing element. This is a very inefficient approach.
We can also use hash table where positive integers are the keys and values denote their presence in the array. If a value 'x' is present, hash_map[x] is set to 1, else 0. Then we traverse the hash_map to look for first key with value set to 0.
This is efficient in terms of time complexity but not so efficient if we consider the space complexity.
We will go for an approach best in terms of both time and space complexity.
First let's divide the array in two halves. First half consisting of negative elements only & 2nd half consisting of positive elements. This can be done with the same logic discussed in sorting an array of 0s & 1s.
Then we consider the positive half of the array and find the smallest missing element extending the logic discussed in find duplicate elements in the array.
If we see element 'x', we make the element at pos_half(x) negative.
Then we traverse the positive half again to look for 1st negative value. The index of that value is the smallest positive element missing in the array. See the implementation below.