find smallest positive number in an array

Question

So ... I have : int array[] = {-8,2,0,5,-3,6,0,9};

I want to find the smallest positive number ( which in the list above is 2 )

This is what i am doing :

---

int array[] = {-8,2,0,5,-3,6,0,9};

int smallest=0;


        for(int i=0;i<array.length;i++) // Find the first number in array>0 (as initial           
                                         // value for int smallest)
        {
            if(array[i]>0)
            {
                smallest=array[i]; 
                break;// Break out of loop, when you find the first number >0
            }   
        }


        for(int i=0;i<array.length;i++) // Loop to find the smallest number in array[]
        {

            if(smallest>array[i]&&array[i]>0)
            {
                smallest=array[i];

            }

        }

        System.out.println(smallest);

        }

---

My question is :

Can we reduce the number of steps ? Is there any smarter/shorter way of doing it, with no other data structure.

Thanks.

Answer 1

is there any smarter/shorter way of doing it?

If you want shorter, with Java 8, you can use a stream of ints:

int min = Arrays.stream(array).filter(i -> i >= 0).min().orElse(0);

(assuming you are happy with a min of 0 when the array is empty).

Answer 2

You do not need to have smallest=array[i], just initialize a variable with INTEGER.MAX_VALUE or array[0] and iterate over the array comparing the value with this variable.

This is achieved in O(n) time and O(1) space and thats the best you can get! :)

a simpler way would be

 int[] array ={-1, 2, 1};
 boolean max_val_present = false;  

 int min = Integer.MAX_VALUE;

 for(int i=0;i<array.length;i++) // Loop to find the smallest number in array[]
 {
      if(min > array[i] && array[i] > 0)
         min=array[i];
      //Edge Case, if all numbers are negative and a MAX value is present
      if(array[i] == Integer.MAX_VALUE)
        max_val_present = true;
 }

 if(min == Integer.MAX_VALUE && !max_val_present) 
 //no positive value found and Integer.MAX_VALUE 
 //is also not present, return -1 as indicator
    return -1; 

 return min; //return min positive if -1 is not returned

Answer 3

Without any prioe knowledge there is no way to avoid iterating the entire array.

You can however make sure you iterate it only once by removing the first loop, and instead just assign smallest = Integer.MAX_VALUE. You can also add a boolean that indicates the array was changed to distinguish between cases where there is no positive integer, and cases where the only positive integer is Integer.MAX_VALUE