Finding the smallest missing positive number in an array

Question

Any suggestions to improve?

public class FindSmallestMissingPositive {
 public static void main(String args[]){
 int a[] = {3,5,4,-1,1,-1,0};
 System.out.println("Smallest Missing positive : "+ findSmPositive(a));
 }
 public static int findSmPositive(int input[]){
 int min = input[0];
 int max= input[0];
 HashSet<Integer> set = new HashSet<Integer>();
 for(int i=0;i<input.length;i++){
 set.add(input[i]);
 if(input[i]<min){
 min = input[i];
 }
 if(input[i]>max){
 max = input[i];
 }
 }
 for(int i=min;i<=max;i++){
 if(i>0 && !set.contains(i)){
 return i;
 }
 else continue;
 }
 return -1;
 }
}

• Naktibalda: if min is more than 1, or max is less than 1, then result should be 1, right?

Answer 1

Bugs

The implementation incorrectly gives -1 for all these input:

• [0] should return 1
• [1] should return 2
• [2] should return 1
• [0,2,2,1,1] should return 3
• [1,2,2,1,3,1,0,4,0] should return 5

Improving the algorithm

The algorithm you used is \$O(n)\$ time and \$O(n)\$ space. If you don't mind modifying the input array, then you could reuse it as the storage, making the algorithm \$O(1)\$ space.

Consider this alternative algorithm:

• If the array is empty, return 1
• Loop over the array indexes
  • While input[i] - 1 is a valid array index and not in the correct position, and input[input[i] - 1] is not in the correct position, then swap the elements i and input[i] - 1.
• Loop over the array indexes again, and when you find a value not in the correct position, then return i + 1.
• Return the last value + 1.

The logic behind this algorithm:

• Swap elements into the correct position to get a sequence of positive integers 1, 2, 3, ...
• Ignore values that cannot be in this array (<= 0 or too high index)
• The beginning of the array will be filled with correct sequence values, gaps will be filled with junk, and the second looping pass will short-circuit on the first incorrect value

Strange coding style

Although these type declarations compile, they are not recommended:

public static void main(String args[]) {
public static int findSmPositive(int input[]) {

The recommended writing style:

public static void main(String[] args) {
public static int findSmPositive(int[] input) {

Also, the code formatting style is not great, at many places it's too compact. I suggest to copy paste into an IDE like IntelliJ or Eclipse and use the auto-formatting function to reformat nicely.

Testing your improvements

The problem description seems to match this one on leetcode. After you implement your improvements, I suggest posting there to verify the correctness of your implementation.

https://leetcode.com/problems/first-missing-positive/

Answer 2

Possible bug

int min = input[0];
int max= input[0];

is going to explode if you pass an empty array. This is not what I would expect from the method. The smallest missing positive number in an empty array is 0, because 0 is not the array and it is the smallest positive number.

Then, you actually do not need to store the minimum and the maximum: since we want the smallest positive numbers, we can start searching from 0, and increment while the array contains it.

Use enhanced for loop

for(int i=0;i<input.length;i++){
 set.add(input[i]);
 // ...
}

When you're iterating over an array, or an Iterable, and you don't need the index, it is simpler to use an enhanced for loop:

for (int element : input) {
 set.add(element);
 // ...
}

Don't bother with negative elements

We're searching for the smallest positive numbers, so we can ignore negative ones. So inside:

for(int i=min;i<=max;i++){
 if(i>0 && !set.contains(i)){
 return i;
 }
 else continue;
}

There is no need to start at the minimum: we can start at 0. Furthermore, instead of using a for loop, it would be cleaner to use a while loop:

int smallestPositive = 0;
while (set.contains(smallestPositive)) {
 smallestPositive++;
}
return smallestPositive;

This is a lot shorter and also clearer: while the set of all the numbers in the array contains our attempt, increment it. This will terminate when we find the smallest one.

A small memory improvement, if there are a lot of negative numbers, would be to not store negative numbers in the set in the first place. It doesn't hurt performance since contains will still be constant-time, but there will be less elements in it.

• BenC: +1, although I believe the smallest positive (not non-negative) integer is usually 1. OP uses this definition as well.

Answer 3

Favor interfaces over implementations

 HashSet<Integer> set = new HashSet<Integer>();

Consider

 Set<Integer> set = new HashSet<>();

Everything else stays the same. Now if you want to change from a HashSet to another Set type, you can just change it one place. Not so big a deal here, but when you start passing them, using the interface can simplify later changes greatly.

Toss bad data early

At the end, you check that the number is positive. Why wait?

 for(int i=0;i<input.length;i++){
 set.add(input[i]);
 if(input[i]<min){
 min = input[i];
 }
 if(input[i]>max){
 max = input[i];
 }
 }

If you check here, you have fewer elements to check later, and you don't have to worry about a negative min.

 for (int element : input) {
 if (element < 0) {
 min = 0;
 continue;
 }
 set.add(element);
 if (element < min) {
 min = element;
 }
 if (element > max) {
 max = element;
 }
 }

Note that the

 min = 0;

is just there to cover sets like {-5, 5}. Your code will return 1 in that case. This preserves that.

Know your boundaries

 for(int i=min;i<=max;i++){
 if(i>0 && !set.contains(i)){
 return i;
 }
 else continue;
 }

You don't have to check min and max. The set will always contain max. And min can only be out of the set if it is 0, which doesn't need to be checked. So

 for (int i = min + 1; i < max; i++) {
 if (!set.contains(i)) {
 return i;
 }
 }

Now every value it checks has a chance to be the answer.

I removed the continue, as it didn't do anything in this loop.

As I said earlier, the i > 0 check is unnecessary here, as min + 1 will always be positive. The smallest value for min is 0, and we add one to start.