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++.<\/p>\n
This is a problem of finding and printing the minimum value that satisfies specific conditions from a given array.<\/p>\n
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.<\/p>\n
The first line contains an integer N (2 \u2264 N \u2264 100,000). The second line contains N integers separated by spaces. Each integer is between -1,000,000,000 and 1,000,000,000.<\/p>\n
Output the second smallest integer. If there is no second smallest integer, output “No Second Minimum”.<\/p>\n
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.<\/p>\n
Now, let’s implement the above algorithm in C++. Below is the C++ code:<\/p>\n
#include <iostream>\n#include <vector>\n#include <algorithm>\n#include <set>\n\nusing namespace std;\n\nint main() {\n int N;\n cin >> N;\n\n vector<int> A(N);\n \n for (int i = 0; i < N; i++) {\n cin >> A[i];\n }\n\n \/\/ Sort the array\n sort(A.begin(), A.end());\n\n \/\/ Set to store unique values\n set<int> uniqueValues(A.begin(), A.end());\n\n \/\/ Find the second smallest value\n if (uniqueValues.size() < 2) {\n cout << \"No Second Minimum\" << endl;\n } else {\n auto it = uniqueValues.begin();\n it++;\n cout << *it << endl;\n }\n\n return 0;\n}\n <\/code><\/pre>\nCode Explanation<\/h2>\n\n#include <iostream><\/code>: Library for input and output.<\/li>\n#include <vector><\/code>: Enables the use of dynamic arrays.<\/li>\n#include <algorithm><\/code>: Allows the use of sorting functions and other algorithm-related functions.<\/li>\n#include <set><\/code>: Library for using sets (a data structure that does not allow duplicates).<\/li>\n- The code takes user input for the size of the array N, followed by N integers.<\/li>\n
sort(A.begin(), A.end());<\/code>: Sorts the array.<\/li>\nset<int> uniqueValues(A.begin(), A.end());<\/code>: Converts the sorted array into a set to remove duplicate values.<\/li>\n- Checks the size of the set to determine if the second smallest value exists, then outputs the result.<\/li>\n<\/ul>\n
Time Complexity<\/h2>\n
The time complexity of the above algorithm is as follows:<\/p>\n