DSA

K-th element of two Arrays

Covers: Naive, Two Pointer. Optimal — Time O(n+m), Space O(1).

August 8, 2026
DSABinary SearchLeetCodePracticeHeapPriority QueueSorting

Practice Link

Given two sorted arrays a[] and b[] and an element k, the task is to find the element that would be at the kth position of the combined sorted array.

Naive Solution#

Merge both arrays into one, sort the combined result, and return the element at index k-1. This is simple but wastes the sorted property and uses O(n+m) extra space.

cpp
class Solution {
public:
    int kthElement(vector<int>& a, vector<int>& b, int k) {
        vector<int> merged;

        for(int num : a) 
            merged.push_back(num);
        for(int num : b) 
            merged.push_back(num);

        sort(merged.begin(), merged.end());

        return merged[k - 1];
    }
};

Time Complexity: O((n + m) * log(n + m)).

Space Complexity: O(n + m)

Better Solution - Two Pointer#

Simulate the merge-sort merge step without materializing the merged array. Advance two pointers i (into a) and j (into b), always picking the smaller current element, for exactly k steps. The element picked on the k-th step is the answer. Space is O(1) and time is O(k) ≤ O(n+m).

cpp
class Solution {
  public:
    int kthElement(vector<int>& a, vector<int>& b, int k) {
        int n = a.size();
        int m = b.size();
        
        int idx = 0;
        int i=0,j=0;
        
        for(int cnt=0;cnt<k;cnt++)
        {
            if(i!=n && j!=m)
            {
                if(a[i] < b[j])
                    idx = a[i++];
                else
                    idx = b[j++];
            }else if(i<n)
                idx = a[i++];
            else
                idx = b[j++];
        }
        return idx;
    }
};

Time Complexity: O(n+m)

Space Complexity: O(1)

Related articles

DSAMedian of 2 sorted ArraysCovers: Naive, Two Pointer. Optimal — Time O(n+m), Space O(1).DSAFind Kth RotationBinary Search. Time O(logn), Space O(1).DSAKth Largest in unsorted ArrayCovers: Naive, Use Min Heap. Optimal — Time O(nlogk), Space O(1).