# dense graph solution

• trivial solution need to sort. O(mnlogmn).
however, we can model this problem to a graph. G is mxn matrix to represent all pairs of nums1x nums2
trivial complex become O(kmn). just iterate the G to find minimal edge.

further optimization:
becomes each row and column are sorted. just skip unnecessary comparisons.

``````    vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
vector<pair<int, int>> ans;
int m = nums1.size(); int n = nums2.size();
if (m == 0 || n == 0) return ans;

vector<vector<int>> G(m, vector<int>(n, INT_MAX));
for (int i=0; i<m; ++i) for (int j=0; j<n; ++j) {
G[i][j] = nums1[i] + nums2[j];
}

while (k--) {
int edge = INT_MAX;
int x = m, y;
y = n;

for (int i=0; i<m; ++i) {
for (int j=0; j < y; ++j)
if(G[i][j] < edge) {
edge = G[i][j];
x = i;
y = j;
break;
}
else if (G[i][j] != INT_MAX && G[i][j] > edge) break;
}
if (edge == INT_MAX) break;

ans.push_back(make_pair(nums1[x], nums2[y]));
G[x][y] = INT_MAX;
}
return ans;
}
``````

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