Finding the second smallest integer in array

Question

We are required in our assignment to find the second smallest integer in one array recursively. However, for the sake of understanding the subject more, I want to do it iteratively first (with the help of this website) and recursively on my own.

Unfortunately, doing it iteratively is quite confusing. I understand that the solution is simple but i can't wrap my head around it.

Below is my code, so far:

public static void main(String[] args) 
{
    int[] elements  = {0 , 2 , 10 , 3, -3 }; 
    int smallest = 0; 
    int secondSmallest = 0; 

    for (int i = 0; i < elements.length; i++)
    {
        for (int j = 0; j < elements.length; j++)
        {
            if (elements[i] < smallest)
            {
                smallest = elements[i];

                if (elements[j] < secondSmallest)
                {
                    secondSmallest = elements[j];
                }
            }
        }

    }

    System.out.println("The smallest element is: " + smallest + "\n"+  "The second smallest element is: " + secondSmallest);
}

This works for a few numbers, but not all. The numbers change around because the inner if condition isn't as efficient as the outer if condition.

Array rearrangements are forbidden.

Answer 1

Try this one. Second condition is used to catch an event when the smallest number is the first

    int[] elements = {-5, -4, 0, 2, 10, 3, -3};
    int smallest = Integer.MAX_VALUE;
    int secondSmallest = Integer.MAX_VALUE;
    for (int i = 0; i < elements.length; i++) {
        if(elements[i]==smallest){
          secondSmallest=smallest;
        } else if (elements[i] < smallest) {
            secondSmallest = smallest;
            smallest = elements[i];
        } else if (elements[i] < secondSmallest) {
            secondSmallest = elements[i];
        }

    }

UPD by @Axel

int[] elements = {-5, -4, 0, 2, 10, 3, -3};
int smallest = Integer.MAX_VALUE;
int secondSmallest = Integer.MAX_VALUE;
for (int i = 0; i < elements.length; i++) {
    if (elements[i] < smallest) {
        secondSmallest = smallest;
        smallest = elements[i];
    } else if (elements[i] < secondSmallest) {
        secondSmallest = elements[i];
    }
}

Answer 2

Here is TimeComlexity Linear O(N):

  public static int secondSmallest(int[] arr) {
    if(arr==null || arr.length < 2) {
        throw new IllegalArgumentException("Input array too small");
    }

    //implement
    int firstSmall = -1;
    int secondSmall = -1;

    //traverse to find 1st small integer on array
    for (int i = 0; i<arr.length;i++)
        if (firstSmall == -1 || arr[firstSmall]>arr[i])
            firstSmall = i;

     //traverse to array find 2 integer, and skip first small
    for (int i = 0;i<arr.length;i++) {
        if (i != firstSmall && (secondSmall == -1 || arr[secondSmall] > arr[i]))
            secondSmall = i;
    }

    return arr[secondSmall];
}

Answer 3

    int[] arr = { 4, 1, 2, 0, 6, 1, 2, 0 };

    int smallest = Integer.MAX_VALUE;
    int smaller = Integer.MAX_VALUE;
    int i = 0;

    if (arr.length > 2) {
        for (i = 0; i < arr.length; i++) {

            if (arr[i] < smallest) {
                smaller = smallest;
                smallest = arr[i];
            } else if (arr[i] < smaller && arr[i] > smallest) {
                smaller = arr[i];
            }
        }

        System.out.println("Smallest number is " + smallest);
        System.out.println("Smaller number is " + smaller);

    } else {
        System.out.println("Invalid array !");
    }
}

Answer 4

You can do it in O(n) time. Below is the python code

def second_small(A):
    if len(A)<2:
        print 'Invalid Array...'
        return
    small = A[0]
    second_small = [1]
    if small >  A[1]:
        second_small,small = A[0],A[1]

    for i in range(2,len(A)):
        if A[i] < second_small and A[i]!=small:
            if A[i] < small:
                second_small = small
                small = A[i]
            else:
                second_small = A[i]
    print small, second_small
A = [12, 13, 1, 10, 34, 1]
second_small(A)