Given two integer arrays sorted in ascending order and an integer k. Definesum = a + b, where_a_is an element from the first array and_b_is an element from the second one. Find the_k_th smallest sum out of all possible sums.

Have you met this question in a real interview?

Yes

Example

Given[1, 7, 11]and[2, 4, 6].

For k =3, return7.

For k =4, return9.

For k =8, return15.

Challenge

Do it in either of the following time complexity:

  1. O(k log min(n, m, k)). where n is the size of A, and m is the size of B.
  2. O( (m + n) log maxValue). where maxValue is the max number in A and B.

line 51 has to use const Node

&

other const

line 21 forgotten , usual errors

class Solution {

public:

/\*\*

 \* @param A an integer arrays sorted in ascending order

 \* @param B an integer arrays sorted in ascending order

 \* @param k an integer

 \* @return an integer

 \*/

int kthSmallestSum\(vector<int>& A, vector<int>& B, int k\) {

    // Write your code here

    if \(A.empty\(\)\) {

        return B\[k - 1\];

    }

    if \(B.empty\(\)\) {

        return A\[k - 1\];

    }

    vector<vector<bool> > used\(A.size\(\), vector<bool>\(B.size\(\), false\)\);

    priority\_queue<Node> heap;

    Node node\(0, 0, A\[0\] + B\[0\]\);

    used\[0\]\[0\] = true;

    heap.push\(node\);

    vector<vector<int> > dirs = { {1,0}, {0,1}};



    for \(int i = 0; i < k; ++i\) {

        if \(heap.empty\(\)\) {

            return -1;

        }

        auto node = heap.top\(\); heap.pop\(\);

        if \(i == k - 1\) {

            return node.val;

        }

        for \(auto& dir : dirs\) {

            int nx = node.x + dir\[0\];

            int ny = node.y + dir\[1\];

            if \(nx >= A.size\(\) \|\| ny >= B.size\(\) \|\| used\[nx\]\[ny\]\) {

                continue;

            }

            Node newNode\(nx, ny, A\[nx\] + B\[ny\]\);

            used\[nx\]\[ny\] = true;

            heap.push\(newNode\);

        }

    }



    return -1;

}

private:

struct Node {

  Node\(int \_x, int \_y, int \_val\) :

        x\(\_x\), y\(\_y\), val\(\_val\) {}

  bool operator < \(const Node& other\) const {

      return val > other.val;

  }

  int x, y, val;  

};

};

results matching ""

    No results matching ""