{"id":6494,"date":"2020-03-15T01:05:03","date_gmt":"2020-03-15T08:05:03","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6494"},"modified":"2020-03-15T01:07:28","modified_gmt":"2020-03-15T08:07:28","slug":"leetcode-1380-lucky-numbers-in-a-matrix","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/array\/leetcode-1380-lucky-numbers-in-a-matrix\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1380. Lucky Numbers in a Matrix"},"content":{"rendered":"\n

Given a m * n<\/code> matrix of distinct <\/strong>numbers, return all lucky numbers in the matrix in any <\/strong>order.<\/p>\n\n\n\n

A lucky number is an element of the matrix such that it is the minimum element in its row and maximum in its column.<\/p>\n\n\n\n

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

Input:<\/strong> matrix = [[3,7,8],[9,11,13],[15,16,17]]\nOutput:<\/strong> [15]\nExplanation:<\/strong> 15 is the only lucky number since it is the minimum in its row and the maximum in its column\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> matrix = [[1,10,4,2],[9,3,8,7],[15,16,17,12]]\nOutput:<\/strong> [12]\nExplanation:<\/strong> 12 is the only lucky number since it is the minimum in its row and the maximum in its column.\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> matrix = [[7,8],[1,2]]\nOutput:<\/strong> [7]\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • m == mat.length<\/code><\/li>
  • n == mat[i].length<\/code><\/li>
  • 1 <= n, m <= 50<\/code><\/li>
  • 1 <= matrix[i][j] <= 10^5<\/code>.<\/li>
  • All elements in the matrix are distinct.<\/li><\/ul>\n\n\n\n
    Solution: Pre-processing<\/strong><\/h2>\n\n\n\n
    Two pass. First pass, record the min val of each row, and max val of each column.
    Second pass, identify lucky numbers.<\/p>\n\n\n\n
    Time complexity: O(m * n)
    Space complexity: O(m + n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector luckyNumbers (vector>& matrix) {\n    const int m = matrix.size();\n    const int n = matrix[0].size();\n    vector rows(m, INT_MAX);\n    vector cols(n, INT_MIN);\n    for (int i = 0; i < m; ++i)\n      for (int j = 0; j < n; ++j) {\n        rows[i] = min(rows[i], matrix[i][j]);\n        cols[j] = max(cols[j], matrix[i][j]);\n      }\n    vector ans;\n    for (int i = 0; i < m; ++i)\n      for (int j = 0; j < n; ++j) \n        if (matrix[i][j] == rows[i] &&\n            matrix[i][j] == cols[j])\n          ans.push_back(matrix[i][j]);\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    Given a m * n matrix of distinct numbers, return all lucky numbers in the matrix in any order. A lucky number is an element of the matrix such that it is…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[184],"tags":[222,216,366],"class_list":["post-6494","post","type-post","status-publish","format-standard","hentry","category-array","tag-easy","tag-matrix","tag-omn","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6494","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=6494"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6494\/revisions"}],"predecessor-version":[{"id":6496,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6494\/revisions\/6496"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6494"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6494"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6494"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}