Small Steps III — Thinking with Programs

Finding the second-largest value

Find the second-largest value.

What you will learn

Before solving a new problem, define what counts as the answer and what assumptions hold about the input. Here we remember two candidates.

Try it

void small_main()
{
    Array<int> numbers = {8, 3, 12, 5, 10};

    int largest = numbers[0];
    int second = numbers[1];

    if (second > largest)
    {
        int temp = largest;
        largest = second;
        second = temp;
    }

    for (int i = 2; i < numbers.length(); i = i + 1)
    {
        if (numbers[i] > largest)
        {
            second = largest;
            largest = numbers[i];
        }
        else if (numbers[i] > second)
        {
            second = numbers[i];
        }
    }

    print("Second largest: ", second);
}

The example assumes at least two elements and includes duplicates in the ranking. For {9, 9, 3}, the answer is 9. It does not mean the second distinct value.

When a new maximum appears, move the previous maximum into second. For 8, 3, 12, 5, 10, the answer is 10.

Exercise

Assume there are at least two distinct values and find the second-smallest value.

void small_main()
{
    Array<int> numbers = {8, 3, 12, 5, 10};

    // find the second smallest value.
}

Hint

Remember smallest and second. When a value is smaller than smallest, update both values together.

void small_main()
{
    Array<int> numbers = {8, 3, 12, 5, 10};

    int smallest = numbers[0];
    int second = numbers[1];

    if (second < smallest)
    {
        int temp = smallest;
        smallest = second;
        second = temp;
    }

    for (int i = 2; i < numbers.length(); i = i + 1)
    {
        if (numbers[i] < smallest)
        {
            second = smallest;
            smallest = numbers[i];
        }
        else if (numbers[i] < second)
        {
            second = numbers[i];
        }
    }

    print(second);
}