C++ Coding Test Course, Finding Minimum Value 2

One of the most common problems encountered in coding tests is finding the minimum or maximum value in an array that meets given conditions. In this tutorial, we will introduce a problem titled ‘Finding the Second Minimum’ which is frequently tested in actual coding tests, and we will explain in detail how to solve it using C++.

Problem Description

This is a problem of finding and printing the minimum value that satisfies specific conditions from a given array.

Problem Definition

An integer N is given, along with an array A that contains N integers. Write a program that outputs the second smallest value among all elements of the array.

Input Format

The first line contains an integer N (2 ≤ N ≤ 100,000). The second line contains N integers separated by spaces. Each integer is between -1,000,000,000 and 1,000,000,000.

Output Format

Output the second smallest integer. If there is no second smallest integer, output “No Second Minimum”.

Example Input and Output

Approach to Problem Solving

To solve this problem, it is essential to understand how to sort the elements of the array and how to handle duplicates well. Since we want to find the second smallest value, we can simply sort the array and then extract the second value from the unique values.

Algorithm Steps

1. Receive the array as input and sort it.
2. Remove duplicates from the sorted array to create a list of unique values.
3. Check if the second minimum value exists in the list of unique values and print it.

C++ Implementation

Now, let’s implement the above algorithm in C++. Below is the C++ code:

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

int main() {
    int N;
    cin >> N;

    vector<int> A(N);
    
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    // Sort the array
    sort(A.begin(), A.end());

    // Set to store unique values
    set<int> uniqueValues(A.begin(), A.end());

    // Find the second smallest value
    if (uniqueValues.size() < 2) {
        cout << "No Second Minimum" << endl;
    } else {
        auto it = uniqueValues.begin();
        it++;
        cout << *it << endl;
    }

    return 0;
}
    

Code Explanation

• #include <iostream>: Library for input and output.
• #include <vector>: Enables the use of dynamic arrays.
• #include <algorithm>: Allows the use of sorting functions and other algorithm-related functions.
• #include <set>: Library for using sets (a data structure that does not allow duplicates).
• The code takes user input for the size of the array N, followed by N integers.
• sort(A.begin(), A.end());: Sorts the array.
• set<int> uniqueValues(A.begin(), A.end());: Converts the sorted array into a set to remove duplicate values.
• Checks the size of the set to determine if the second smallest value exists, then outputs the result.

Time Complexity

The time complexity of the above algorithm is as follows:

• Time taken for sorting: O(N log N)
• Removing duplicates and finding the second value: O(N) (checking the size of the set can be done in constant time)
• Total time complexity: O(N log N), mainly due to the cost of sorting.

Conclusion

In this tutorial, we learned how to find the second smallest value in an array using C++. If you have understood the structure of sorting the given array and removing duplicate values to find the second minimum value, it will greatly help you solve similar problems. Practice solving various array manipulation problems. Good job!