#include <iostream>
#include <vector>
#include <algorithm>
/*
Find the N smallest values in a 2D vector.
The program uses a two‑step approach:
1. Flatten the 2D vector into a single vector.
2. Use std::nth_element to partition the vector so that the first N
elements are the smallest (in any order).
3. Sort only those N elements for clean output.
This avoids sorting the entire dataset and is efficient even for large inputs.
*/
// Flatten a 2D vector into a 1D vector
std::vector<int> flatten(const std::vector<std::vector<int>>& matrix) {
std::vector<int> result;
for (const auto& row : matrix) {
result.insert(result.end(), row.begin(), row.end());
}
return result;
}
// Extract the N smallest values
std::vector<int> smallestN(const std::vector<std::vector<int>>& matrix, std::size_t N) {
auto flat = flatten(matrix);
if (N >= flat.size()) {
std::sort(flat.begin(), flat.end());
return flat;
}
// Partition so that the first N elements are the smallest
std::nth_element(flat.begin(), flat.begin() + N, flat.end());
// Sort only the smallest N elements
std::vector<int> result(flat.begin(), flat.begin() + N);
std::sort(result.begin(), result.end());
return result;
}
int main() {
std::vector<std::vector<int>> matrix = {
{12, 5, 7},
{3, 19, 1},
{8, 4, 6}
};
std::size_t N = 5;
auto values = smallestN(matrix, N);
std::cout << "The " << N << " smallest values:\n";
for (int v : values) {
std::cout << v << " ";
}
}
/*
run:
The 5 smallest values:
1 3 4 5 6
*/
