# 15 ms C++ without priority queue, explained with comments

• ``````#include <algorithm>
#include <functional>

class Solution {
typedef std::vector<std::pair<int, int>> pIIV;
public:
pIIV kSmallestPairs(std::vector<int>& nums1, std::vector<int>& nums2, int k) {
pIIV resV;
if(nums1.empty() || nums2.empty() || k==0) return resV;
auto num1A = nums1.data(), num2A = nums2.data();
int nrow = nums1.size(), ncol = nums2.size();
// could swap num1A and num2A here when nrow<ncol for a lower bound of the time complexity
// use a vector of size ncol to store the possible row number of minimum pairs
// in each column (each column can have no more than one min pair)
std::vector<int> irows(ncol, 0); auto irowA = irows.data();
// for each step, find the min pair among the ncol potential min pairs
int colmin = 0; // colmin increments when the bottom element of the current first column is output
for(int i=0; i<std::min(k, nrow*ncol); ++i) {
int icolmin = colmin, min = num1A[irows[colmin]] + num2A[colmin];
for(int icol=colmin+1; icol<ncol; ++icol) {
if(irowA[icol] == irowA[icol-1]) continue;  // element in the same row cannot be smaller than the first
int val = num1A[irowA[icol]] + num2A[icol]; // compute sum of current pair
if( val < min ) { min = val; icolmin = icol; }  // update min
}
resV.push_back({num1A[irowA[icolmin]], num2A[icolmin]});
if( (++irowA[icolmin]) == nrow ) ++colmin;  // increment colmin if the current column is done
}
return resV;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.