Kth element of two sorted lists Editorial

Practice Problem Link: Kth element of two sorted lists | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given two sorted arrays A and B, and another value k, print the kth element of the resultant sorted array.

Naive Approach

A simple solution is to merge the two arrays, sort the array and return the Kth element.

Analysis

• Time Complexity: O((m + n).(log(m + n)))
• Space Complexity: O(m + n)

where m and n are the size of the two arrays.

Implementation

C++

int getKthElement(vector<int> firstArr, vector<int> secondArr, int k) {
    vector<int> mergedArr;
    for(int i = 0; i < firstArr.size(); i++) {
        mergedArr.push_back(firstArr[i]);
    }
    for(int i = 0; i < secondArr.size(); i++) {
        mergedArr.push_back(secondArr[i]);
    }
    sort(mergedArr.begin(), mergedArr.end());
    return mergedArr[k - 1];
}

Java

class Solution {
   int getKthElement(int[] firstArr, int[] secondArr, int k) {
        int[] mergedArr = new int[firstArr.length + secondArr.length];
        int indx = 0;
        for(int i = 0; i < firstArr.length; i++) {
            mergedArr[indx] = firstArr[i];
            indx++;
        }
        for(int i = 0; i < secondArr.length; i++) {
            mergedArr[indx] = secondArr[i];
            indx++;
        }
        Arrays.sort(mergedArr);
        return mergedArr[k - 1];
   }
}

Optimal Approach

Since both the arrays are sorted, a binary search algorithm can efficiently solve the problem. Here, both arrays can be searched simultaneously to find the Kth element.

• The initial k / 2 elements of both the array should be checked first. Here two different cases will be encountered.
• Case 1: firstArr[k / 2] > secondArr[k / 2]
  In this case, the initial k / 2 elements of the second array will definitely be less than the k-th element, so a  recursive binary search can be called to find the rest of the k / 2 element in the first array and the other half of the second array.
• Case 2: firstArr[k / 2] <= secondArr[k / 2]
  In this case, the initial k / 2 elements of the first array will definitely be less than or equal to the k-th element, so a  recursive binary search can be called to find the rest of the k / 2 element in the second array and the other half of the first array.

Analysis

• Time Complexity: O(log(n * m))
• Space Complexity: O(1)

Implementation

C++

int findKth(vector<int> &firstArr, vector<int> &secondArr, int firstStart, int secondStart, int firstSize, int secondSize, int k) {
    if(k >(firstSize + secondSize) || k < 1) {
        return -1;
    }
    if(firstSize > secondSize) {
        return findKth(secondArr, firstArr, secondStart, firstStart, secondSize, firstSize, k);
    }
    if(firstSize == 0) {
        return secondArr[secondStart + k - 1];
    }
    if(k == 1) {
        return min(firstArr[firstStart], secondArr[secondStart]);
    }
    int i = min(firstSize, k / 2), j = min(secondSize, k / 2);
    if(firstArr[firstStart + i - 1] > secondArr[secondStart + j - 1]) {
        return findKth(firstArr, secondArr, firstStart, secondStart + j, firstSize, secondSize - j, k - j);
    } else {
        return findKth(firstArr, secondArr, firstStart + i, secondStart, firstSize - i, secondSize, k - i);
    }
}
int getKthElement(vector<int> &firstArr, vector<int> &secondArr, int k) {
   return findKth(firstArr, secondArr, 0, 0, firstArr.size(), secondArr.size(), k);
}

Java

class Solution {
   int findKth(int[] firstArr, int[] secondArr, int firstStart, int secondStart, int firstSize, int secondSize, int k) {
       if(k >(firstSize + secondSize) || k < 1) {
           return -1;
       }
       if(firstSize > secondSize) {
           return findKth(secondArr, firstArr, secondStart, firstStart, secondSize, firstSize, k);
       }
       if(firstSize == 0) {
           return secondArr[secondStart + k - 1];
       }
       if(k == 1) {
           return Math.min(firstArr[firstStart], secondArr[secondStart]);
       }
       int i = Math.min(firstSize, k / 2);
       int j = Math.min(secondSize, k / 2);
       if(firstArr[firstStart + i - 1] > secondArr[secondStart + j -1]) {
           return findKth(firstArr, secondArr, firstStart, secondStart + j, firstSize, secondSize - j, k - j);
       } else {
           return findKth(firstArr, secondArr, firstStart + i, secondStart, firstSize - i, secondSize, k - i);
       }
   }
   int getKthElement(int[] firstArr, int[] secondArr, int k) {
       return findKth(firstArr, secondArr, 0, 0, firstArr.length, secondArr.length, k);
   }
}