{"id":6709,"date":"2020-05-05T22:28:26","date_gmt":"2020-05-06T05:28:26","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6709"},"modified":"2020-05-05T22:31:19","modified_gmt":"2020-05-06T05:31:19","slug":"leetcode-1439-find-the-kth-smallest-sum-of-a-matrix-with-sorted-rows","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-1439-find-the-kth-smallest-sum-of-a-matrix-with-sorted-rows\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1439. Find the Kth Smallest Sum of a Matrix With Sorted Rows"},"content":{"rendered":"\n

You are given an m * n<\/code> matrix, mat<\/code>, and an integer k<\/code>, which has its rows sorted in non-decreasing order.<\/p>\n\n\n\n

You are allowed to choose exactly 1 element from each row to form an array. Return the Kth smallest<\/strong> array sum among all possible arrays.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> mat = [[1,3,11],[2,4,6]], k = 5\nOutput:<\/strong> 7\nExplanation: <\/strong>Choosing one element from each row, the first k smallest sum are:\n[1,2], [1,4], [3,2], [3,4], [1,6]. Where the 5th sum is 7.  <\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> mat = [[1,3,11],[2,4,6]], k = 9\nOutput:<\/strong> 17\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> mat = [[1,10,10],[1,4,5],[2,3,6]], k = 7\nOutput:<\/strong> 9\nExplanation:<\/strong> Choosing one element from each row, the first k smallest sum are:\n[1,1,2], [1,1,3], [1,4,2], [1,4,3], [1,1,6], [1,5,2], [1,5,3]. Where the 7th sum is 9.  \n<\/pre>\n\n\n\n
Example 4:<\/strong><\/p>\n\n\n\n
Input:<\/strong> mat = [[1,1,10],[2,2,9]], k = 7\nOutput:<\/strong> 12\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • m == mat.length<\/code><\/li>
  • n == mat.length[i]<\/code><\/li>
  • 1 <= m, n <= 40<\/code><\/li>
  • 1 <= k <= min(200, n ^ m)<\/code><\/li>
  • 1 <= mat[i][j] <= 5000<\/code><\/li>
  • mat[i]<\/code> is a non decreasing array.<\/li><\/ul>\n\n\n\n
    Solution 1: Priority Queue<\/strong><\/h2>\n\n\n\n
    Generate the arrays in order.<\/p>\n\n\n\n
    Each node is {sum, idx_0, idx_1, …, idx_m},<\/p>\n\n\n\n
    Start with {sum_0, 0, 0, …, 0}.<\/p>\n\n\n\n
    For expansion, pick one row and increase its index<\/p>\n\n\n\n
    Time complexity: O(k * m ^ 2* log k)
    Space complexity: O(k)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int kthSmallest(vector>& mat, int k) {\n    const int m = mat.size();\n    const int n = mat[0].size();\n    priority_queue> q;\n    vector node(m + 1); \/\/ {-sum, idx_0, idx_1, ..., idx_m}\n    for (int i = 0; i < m; ++i) node[0] -= mat[i][0];\n    q.push(node);\n    set> seen{{node}};\n    while (!q.empty()) {\n      const vector cur = q.top(); q.pop();\n      if (--k == 0) return -cur[0];  \n      for (int i = 1; i <= m; ++i) {\n        if (cur[i] == n - 1) continue;\n        vector nxt(cur);\n        ++nxt[i]; \/\/ increase i-th row's index.\n        \/\/ Update sum.\n        nxt[0] -= (mat[i - 1][nxt[i]] - mat[i - 1][nxt[i] - 1]);\n        if (!seen.insert(nxt).second) continue;      \n        q.push(move(nxt));\n      }\n    }\n    return -1;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    You are given an m * n matrix, mat, and an integer k, which has its rows sorted in non-decreasing order. You are allowed to choose exactly 1 element from each row to…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[44],"tags":[217,383,72],"class_list":["post-6709","post","type-post","status-publish","format-standard","hentry","category-searching","tag-hard","tag-kth","tag-priority-queue","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6709","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=6709"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6709\/revisions"}],"predecessor-version":[{"id":6712,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6709\/revisions\/6712"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6709"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6709"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6709"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}