Solution by awice


  • 1

    Approach #1: Brute Force [Memory Limit Exceeded]

    Intuition and Algorithm

    Create the multiplication table and sort it, then take the k-th element.

    Python

    class Solution(object):
        def findKthNumber(self, m, n, k):
            table = [i*j for i in range(1, m+1) for j in range(1, n+1)]
            table.sort()
            return table[k-1]
    

    Java

    class Solution {
        public int findKthNumber(int m, int n, int k) {
            int[] table = new int[m*n];
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    table[(i - 1) * n + j - 1] = i * j;
                }
            }
            Arrays.sort(table);
            return table[k-1];
        }
    }
    

    Complexity Analysis

    • Time Complexity: $$O(mn)$$ to create the table, and $$O(mn\log(m*n))$$ to sort it.

    • Space Complexity: $$O(m*n)$$ to store the table.


    Approach #2: Next Heap [Time Limit Exceeded]

    Intuition

    Maintain a heap of the smallest unused element of each row. Then, finding the next element is a pop operation on the heap.

    Algorithm

    Our heap is going to consist of elements (val, root), where val is the next unused value of that row, and root was the starting value of that row.

    We will repeatedly find the next lowest element in the table. To do this, we pop from the heap. Then, if there's a next lowest element in that row, we'll put that element back on the heap.

    Python

    class Solution(object):
        def findKthNumber(self, m, n, k):
            heap = [(i, i) for i in range(1, m+1)]
            heapq.heapify(heap)
    
            for _ in xrange(k):
                val, root = heapq.heappop(heap)
                nxt = val + root
                if nxt <= root * n:
                    heapq.heappush(heap, (nxt, root))
    
            return val
    

    Java

    class Solution {
        public int findKthNumber(int m, int n, int k) {
            PriorityQueue<Node> heap = new PriorityQueue<Node>(m,
                Comparator.<Node> comparingInt(node -> node.val));
    
            for (int i = 1; i <= m; i++) {
                heap.offer(new Node(i, i));
            }
    
            Node node = null;
            for (int i = 0; i < k; i++) {
                node = heap.poll();
                int nxt = node.val + node.root;
                if (nxt <= node.root * n) {
                    heap.offer(new Node(nxt, node.root));
                }
            }
            return node.val;
        }
    }
    
    class Node {
        int val;
        int root;
        public Node(int v, int r) {
            val = v;
            root = r;
        }
    }
    

    Complexity Analysis

    • Time Complexity: $$O(k * m \log m) = O(m^2 n \log m)$$. Our initial heapify operation is $O(m)$. Afterwards, each pop and push is $$O(m \log m)$$, and our outer loop is $$O(k) = O(m*n)$$

    • Space Complexity: $$O(m)$$. Our heap is implemented as an array with $$m$$ elements.


    Approach #3: Binary Search [Accepted]

    Intuition

    As k and m*n are up to $$9 * 10^8$$, linear solutions will not work. This motivates solutions with \log complexity, such as binary search.

    Algorithm

    Let's binary search for the answer A.

    Say enough(x) is true if and only if there are k or more values in the multiplication table that are less than or equal to x. Colloquially, enough describes whether x is large enough to be the k-th value in the multiplication table.

    Then (for our answer A), whenever x >= A, enough(x) is True; and whenever x < A, enough(x) is False.

    In our binary search, our loop invariant is that enough(hi) = True. At the beginning, enough(m*n) = True, and whenever hi is set, it is set to a value that is "enough" (enough(mi) = True). That means hi will be the lowest such value at the end of our binary search.

    This leaves us with the task of counting how many values are less than or equal to x. For each of m rows, the i-th row looks like [i, 2*i, 3*i, ..., n*i]. The largest possible k*i <= x that could appear is k = x // i. However, if x is really big, then perhaps k > n, so in total there are min(k, n) = min(x // i, n) values in that row that are less than or equal to x.

    After we have the count of how many values in the table are less than or equal to x, by the definition of enough(x), we want to know if that count is greater than or equal to k.

    Python

    class Solution(object):
        def findKthNumber(self, m, n, k):
            def enough(x):
                count = 0
                for i in xrange(1, m+1):
                    count += min(x // i, n)
                return count >= k
    
            lo, hi = 1, m * n
            while lo < hi:
                mi = (lo + hi) / 2
                if not enough(mi):
                    lo = mi + 1
                else:
                    hi = mi
            return lo
    

    Java

    class Solution {
        public boolean enough(int x, int m, int n, int k) {
            int count = 0;
            for (int i = 1; i <= m; i++) {
                count += Math.min(x / i, n);
            }
            return count >= k;
        }
    
        public int findKthNumber(int m, int n, int k) {
            int lo = 1, hi = m * n;
            while (lo < hi) {
                int mi = lo + (hi - lo) / 2;
                if (!enough(mi, m, n, k)) lo = mi + 1;
                else hi = mi;
            }
            return lo;
        }
    }
    

    Complexity Analysis

    • Time Complexity: $$O(m * \log (m*n))$$. Our binary search divides the interval [lo, hi] into half at each step. At each step, we call enough which does $$O(m)$$ work.

    • Space Complexity: $$O(1)$$. We only keep integers in memory during our intermediate calculations.


Log in to reply
 

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