dense graph solution


  • 0
    N

    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;
        }
    

Log in to reply
 

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