Need help to convert "find k-th smallest of two sorted arrays" into "kth-largest"

I have some C++ code that finds k-th smallest item of two sorted arrays in O(log(m * n)) time. I know it's not the most optimal solution, and I know it is possible to solve it in O(log(min(m, n))), however I'm not interested in it yet.

I want to convert this function to make it return k-th largest item instead, and I struggle to make it work. It must be a matter of careful tweaking some comparisons here and there, but I could not make it work. Can I have some help here?

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <unordered_map>

using namespace std;

// speed: O(log( m * n) ))
// space: O(1)
int solveKthSmallest(vector<int>& A, vector<int>& B, int k, int aStart, int aEnd, int bStart, int bEnd)
{
    std::cout << "solveKthSmallest: (" << k << "): [" << aStart << "," << aEnd << "] [" << bStart << "," << bEnd << "]\n";

    // If the segment of on array is empty, it means we have passed all
    // its element, just return the corresponding element in the other array.
    if (aEnd < aStart) {
        return B[k - aStart];
    }
    if (bEnd < bStart) {
        return A[k - bStart];
    }

    // Get the middle indexes and middle values of A and B.
    int aIndex = (aStart + aEnd) / 2;
    int bIndex = (bStart + bEnd) / 2;
    int aValue = A[aIndex];
    int bValue = B[bIndex];

    // If 'k' is in the right half of A + B, remove the smaller left half.
    if (aIndex + bIndex < k) { 
        if (aValue > bValue) {
            return solveKthSmallest(A, B, k, aStart, aEnd, bIndex + 1, bEnd);
        } else {
            return solveKthSmallest(A, B, k, aIndex + 1, aEnd, bStart, bEnd);
        }
    } 
    // Otherwise, remove the larger right half.
    else { 
        if (aValue > bValue) {
            return solveKthSmallest(A, B, k, aStart, aIndex - 1, bStart, bEnd);
        } else {
            return solveKthSmallest(A, B, k, aStart, aEnd, bStart, bIndex - 1);       
        }
    }
    return -1;
}

double findKthSmallest(vector<int>& nums1, vector<int>& nums2, int kIdx) {
    return solveKthSmallest(nums1, nums2, kIdx, 0, nums1.size() - 1, 0, nums2.size() - 1);
}

void t1()
{
    vector nums1{ 1, 4, 5, 8, 9 }; 
    vector nums2{ 2, 3, 6, 7 };

/*
    A: [ 1, 4, 5, 8, 9  ] : An = 5
    B: [ 2, 3, 6, 7 ]     : Bn = 4

    Al        Am        Ar
      [ 1, 4, 5, 8, 9  ]         

    Bl     Bm       Br
      [ 2, 3, 6, 7 ]

    Al <= Am <= Bm <= (Ar & Br)
*/

    cout << findKthSmallest(nums1, nums2, 3) << "\n";
}

int main()
{
    t1();

    return 0;
}

I know it is possible to work around it and call it like this:

double findKthLargest(vector<int>& nums1, vector<int>& nums2, int kIdx) {
    int revIdx = nums1.size() + nums2.size() - 1 - kIdx;
    cout << "revIdx: " << revIdx << "\n";

    return solveKthSmallest(nums1, nums2, revIdx, 0, nums1.size() - 1, 0, nums2.size() - 1);
}

But what I want is to modify solveKthSmallest method (copy it and rename solveKthLargest) to so that it can retain its original algorithm but be called like this

return solveKthLargest(nums1, nums2, kIdx, 0, nums1.size() - 1, 0, nums2.size() - 1);

What you call a "work around" is the most sensible way to do it. Reason is that k is now a reversed position, which you still need to translate to an index. And to do that you need to involve the size of both arrays. As solveKthGreatest will be a recursive function, you'll need to do that conversion on each recursive call. It would look like this:

int solveKthGreatest(vector<int>& A, vector<int>& B, int kIdx, int aStart, int aEnd, int bStart, int bEnd)
// Use of different parameter name                   ^^^^^^^^
{
    std::cout << "solveKthGreatest: (" << kIdx << "): [" << aStart << "," << aEnd << "] [" << bStart << "," << bEnd << "]\n";
    // Calculate the index from the reversed index we got as argument
    int k = A.size() + B.size() - 1 - kIdx;
    if (aEnd < aStart) {
        return B[k - aStart];
    }
    if (bEnd < bStart) {
        return A[k - bStart];
    }

    int aIndex = (aStart + aEnd) / 2;
    int bIndex = (bStart + bEnd) / 2;
    int aValue = A[aIndex];
    int bValue = B[bIndex];

    if (aIndex + bIndex < k) { 
        if (aValue > bValue) {
            return solveKthGreatest(A, B, kIdx, aStart, aEnd, bIndex + 1, bEnd);
//                                        ^^^^
        } else {
            return solveKthGreatest(A, B, kIdx, aIndex + 1, aEnd, bStart, bEnd);
        }
    } 
    else { 
        if (aValue > bValue) {
            return solveKthGreatest(A, B, kIdx, aStart, aIndex - 1, bStart, bEnd);
        } else {
            return solveKthGreatest(A, B, kIdx, aStart, aEnd, bStart, bIndex - 1);       
        }
    }
    return -1;
}

The only changes are:

• The name of the argument changed from k to kIdx
• Definition of a local variable k
• The recursive calls pass kIdx as argument instead of k

You could move the calculation of k to the expressions where k is used (there are three of them), and so omit the variable k, but that looks even less elegant.

Unless you have other constraints, I would still stick to the solution you presented yourself.