花花酱 LeetCode 1439. Find the Kth Smallest Sum of a Matrix With Sorted Rows

By zxi on May 5, 2020

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 form an array. Return the Kth smallest array sum among all possible arrays.

Example 1:

Input: mat = [[1,3,11],[2,4,6]], k = 5
Output: 7
Explanation: Choosing one element from each row, the first k smallest sum are:
[1,2], [1,4], [3,2], [3,4], [1,6]. Where the 5th sum is 7.

Example 2:

Input: mat = [[1,3,11],[2,4,6]], k = 9
Output: 17

Example 3:

Input: mat = [[1,10,10],[1,4,5],[2,3,6]], k = 7
Output: 9
Explanation: Choosing one element from each row, the first k smallest sum are:
[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.

Example 4:

Input: mat = [[1,1,10],[2,2,9]], k = 7
Output: 12

Constraints:

m == mat.length
n == mat.length[i]
1 <= m, n <= 40
1 <= k <= min(200, n ^ m)
1 <= mat[i][j] <= 5000
mat[i] is a non decreasing array.

Solution 1: Priority Queue

Generate the arrays in order.

Each node is {sum, idx_0, idx_1, …, idx_m},

Start with {sum_0, 0, 0, …, 0}.

For expansion, pick one row and increase its index

Time complexity: O(k * m ^ 2* log k)
Space complexity: O(k)

C++

// Author: Huahua

class Solution {

public:

int kthSmallest(vector<vector<int>>& mat, int k) {

const int m = mat.size();

const int n = mat[0].size();

priority_queue<vector<int>> q;

vector<int> node(m + 1); // {-sum, idx_0, idx_1, ..., idx_m}

for (int i = 0; i < m; ++i) node[0] -= mat[i][0];

q.push(node);

set<vector<int>> seen{{node}};

while (!q.empty()) {

const vector<int> cur = q.top(); q.pop();

if (--k == 0) return -cur[0];

for (int i = 1; i <= m; ++i) {

if (cur[i] == n - 1) continue;

vector<int> nxt(cur);

++nxt[i]; // increase i-th row's index.

// Update sum.

nxt[0] -= (mat[i - 1][nxt[i]] - mat[i - 1][nxt[i] - 1]);

if (!seen.insert(nxt).second) continue;

q.push(move(nxt));

}

return -1;

}

};

花花酱 LeetCode 230. Kth Smallest Element in a BST

By zxi on April 13, 2019

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note:
You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.

Example 1:

Input: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
Output: 1

Example 2:

Input: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
Output: 3

Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

Solution: Inorder traversal

Time complexity: O(n)
Space compleixty: O(n)

C++

class Solution {

public:

int kthSmallest(TreeNode* root, int k) {

return inorder(root, k);

}

private:

int inorder(TreeNode* root, int& k) {

if (!root) return -1;

int x = inorder(root->left, k);

if (k == 0) return x;

if (--k == 0) return root->val;

return inorder(root->right, k);

}

};

花花酱 LeetCode 668. Kth Smallest Number in Multiplication Table

By zxi on September 10, 2018

Problem

Nearly every one have used the Multiplication Table. But could you find out the k-th smallest number quickly from the multiplication table?

Given the height m and the length n of a m * n Multiplication Table, and a positive integer k, you need to return the k-th smallest number in this table.

Example 1:

Input: m = 3, n = 3, k = 5
Output: 
Explanation: 
The Multiplication Table:
1	2	3
2	4	6
3	6	9

The 5-th smallest number is 3 (1, 2, 2, 3, 3).

Example 2:

Input: m = 2, n = 3, k = 6
Output: 
Explanation: 
The Multiplication Table:
1	2	3
2	4	6

The 6-th smallest number is 6 (1, 2, 2, 3, 4, 6).

Note:

The m and n will be in the range [1, 30000].
The k will be in the range [1, m * n]

Solution 1: Nth element (MLE)

Time complexity: O(mn)

Space complexity: O(mn)

C++

// 59 / 69 test cases passed.

class Solution {

public:

int findKthNumber(int m, int n, int k) {

vector<int> s(m * n);

auto it = begin(s);

for (int i = 1; i <= m; ++i)

for (int j = 1; j <= n; ++j)

*it++ = i * j;

nth_element(begin(s), begin(s) + k - 1, end(s));

return s[k - 1];

}

};

Solution2 : Binary Search

Find first x such that there are k elements less or equal to x in the table.

Time complexity: O(m*log(m*n))

Space complexity: O(1)

C++

// Author: Huahua, 12 ms

class Solution {

public:

int findKthNumber(int m, int n, int k) {

int l = 1;

int r = m * n + 1;

while (l < r) {

int x = l + (r - l) / 2;

if (LEX(m, n, x) >= k)

r = x;

else

l = x + 1;

}

return l;

}

private:

// Returns # of elements in the m*n table that are <= x

int LEX(int m, int n, int x) {

int count = 0;

for (int i = 1; i <= m; ++i)

count += min(n, x / i);

return count;

}

};

Java

// Author: Huahua, 16 ms

class Solution {

public int findKthNumber(int m, int n, int k) {

int l = 1;

int r = m * n + 1;

while (l < r) {

int x = l + (r - l) / 2;

if (LEX(m, n, x) >= k)

r = x;

else

l = x + 1;

}

return l;

}

// Returns # of elements in the m*n table that are <= x

private int LEX(int m, int n, int x) {

int count = 0;

for (int i = 1; i <= m; ++i)

count += Math.min(n, x / i);

return count;

}

Python3

# Author: Huahua, 976 ms

class Solution:

def findKthNumber(self, m, n, k):

def LEX(m, n, x, k):

count = 0

for i in range(1, min(m + 1, x + 1)):

count += min(n, x // i)

if count >= k: return count

return count

l = 1

r = m * n + 1

while l < r:

x = l + (r - l) // 2

if LEX(m, n, x, k) >= k:

r = x

else:

l = x + 1

return l

Solution 1: Binary Search

Find the smallest x, such that there are k elements that are smaller or equal to x.

Time complexity: O(nlogn*log(max – min))

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 24 ms (beats 97.12%)

class Solution {

public:

int kthSmallest(vector<vector<int>>& matrix, int k) {

const int n = matrix.size();

long l = matrix[0][0];

long r = matrix[n - 1][n - 1] + 1;

while (l < r) {

long m = l + (r - l) / 2;

int total = 0;

int s = n;

for (const auto& row : matrix)

total += (s = distance(begin(row), upper_bound(begin(row), begin(row) + s, m)));

if (total >= k)

r = m;

else

l = m + 1;

}

return l;

}

};

Posts tagged as “kth”

花花酱 LeetCode 1439. Find the Kth Smallest Sum of a Matrix With Sorted Rows

Solution 1: Priority Queue

C++

花花酱 LeetCode 230. Kth Smallest Element in a BST

C++

花花酱 LeetCode 668. Kth Smallest Number in Multiplication Table

Problem

Solution 1: Nth element (MLE)

C++

Solution2 : Binary Search

C++

Java

Python3

Related Problems

花花酱 LeetCode 378. Kth Smallest Element in a Sorted Matrix

Solution 1: Binary Search