K-th element of two Arrays

Given two sorted arrays arr1 and arr2 and an element k. The task is to find the element that would be at the k^th position of the combined sorted array.

Examples :

Input: k = 5, arr1[] = [2, 3, 6, 7, 9], arr2[] = [1, 4, 8, 10]
Output: 6
Explanation: The final combined sorted array would be - 1, 2, 3, 4, 6, 7, 8, 9, 10. The 5th element of this array is 6.

Input: k = 7, arr1[] = [100, 112, 256, 349, 770], arr2[] = [72, 86, 113, 119, 265, 445, 892]
Output: 256
Explanation: Combined sorted array is - 72, 86, 100, 112, 113, 119, 256, 265, 349, 445, 770, 892. 7th element of this array is 256.

Expected Time Complexity: O(log(n) + log(m))
Expected Auxiliary Space: O(log (n))

Constraints:
1 <= k<= arr1.size()+arr2.size()
1 <= arr1.size(), arr2.size() <= 10⁶
0 <= arr1[i], arr2[i] < 10⁸

Approach 01:

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    // Function to find the k-th smallest element in the combined sorted arrays
    int kthElement(int k, const vector<int>& array1, const vector<int>& array2) {
        // Create a vector to hold the combined elements from both arrays
        vector<int> combinedArray;
        
        // Add elements from the first array
        combinedArray.insert(combinedArray.end(), array1.begin(), array1.end());
        // Add elements from the second array
        combinedArray.insert(combinedArray.end(), array2.begin(), array2.end());
        
        // Sort the combined array
        sort(combinedArray.begin(), combinedArray.end());
        
        // Return the k-th smallest element (1-based index, so k-1 for 0-based index)
        return combinedArray[k - 1];
    }
};

from typing import List

class Solution:
    def kthElement(self, k: int, array1: List[int], array2: List[int]) -> int:
        # Create a list to hold the combined elements from both arrays
        combinedArray = array1 + array2
        
        # Sort the combined array
        combinedArray.sort()
        
        # Return the k-th smallest element (1-based index, so k-1 for 0-based index)
        return combinedArray[k - 1]

Time Complexity

• Combining the Arrays:

  Inserting elements from array1 and array2 into combinedArray takes \( O(m + n) \) time, where \( m \) is the size of array1 and \( n \) is the size of array2.

• Sorting the Combined Array:

  Sorting combinedArray takes \( O((m + n) \log(m + n)) \) time using the sort function.

• Overall Time Complexity:

  The overall time complexity is \( O((m + n) \log(m + n)) \), as sorting dominates the time complexity.

Space Complexity

• Space for Combined Array:

  The space required for combinedArray is \( O(m + n) \), where \( m \) and \( n \) are the sizes of array1 and array2, respectively.

• Overall Space Complexity:

  The overall space complexity is \( O(m + n) \) due to the space needed to store the combined array.

Approach 02:

#include <algorithm>
#include <queue>
#include <vector>

class Solution {
  public:
    int kthElement(std::vector<int>& array1, std::vector<int>& array2, int k) {
        // Priority queue is used to store elements in ascending order
        std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

        // Insert elements of the first array
        for (int& element : array1) {
            minHeap.push(element);
        }

        // Insert elements of the second array
        for (int& element : array2) {
            minHeap.push(element);
        }

        // Pop k-1 elements to reach the kth smallest element
        k--;
        while (!minHeap.empty() && k--) {
            minHeap.pop();
        }

        int result = minHeap.top(); // The kth smallest element
        return result;
    }
};

import heapq

class Solution:
    def kthElement(self, array1, array2, k):
        # Min-heap to store elements in ascending order
        minHeap = []

        # Insert elements of the first array
        for element in array1:
            heapq.heappush(minHeap, element)

        # Insert elements of the second array
        for element in array2:
            heapq.heappush(minHeap, element)

        # Pop k-1 elements to reach the kth smallest element
        k -= 1
        while minHeap and k > 0:
            heapq.heappop(minHeap)
            k -= 1

        result = heapq.heappop(minHeap)  # The kth smallest element
        return result

Time Complexity

• Inserting elements into the Min-Heap:
  • Let \(n\) be the size of array1 and \(m\) be the size of array2.
  • We push all \(n + m\) elements into the min-heap. Each insertion into the heap takes \(O(\log(n + m))\) time.
  • The total cost of this step is \(O((n + m) \log(n + m))\).
• Popping \(k-1\) elements from the Min-Heap:
  • Removing the smallest element from the heap takes \(O(\log(n + m))\) time per operation.
  • For \(k-1\) pops, the total cost is \(O(k \log(n + m))\).
• Overall Time Complexity:

  The overall time complexity is \(O((n + m) \log(n + m)) + O(k \log(n + m))\), which simplifies to \(O((n + m) \log(n + m))\) if \(k \leq n + m\).

Space Complexity

• Min-Heap:
  • The min-heap stores \(n + m\) elements at most, requiring \(O(n + m)\) space.
• Other Variables:
  • Variables like result, loop variables, and counters use \(O(1)\) space.
• Overall Space Complexity:

  The space complexity is \(O(n + m)\), dominated by the min-heap.