# O(log(min(m,n))) solution in clear Java

• I wanted to share my approach as I found many of the other solutions fairly hard to parse. This is my stab at solving it in a way that I feel is highly readable and logically separated into nicely decoupled abstractions.

``````public class Solution {

/**
* Medians always exist at a known index, when given a collection of a known
* size.
*
* The approach that seems cleanest and easiest to reason about is to treat
* it as two abstractions: from the top, a single list we can ask for the
* n-th element, and against which we perform standard median lookups; and
* from the bottom, an adapter which supports ordinal lookups across the two
* lists as if they were one. Internally it uses a binary search over the
* range of possible locations for the requested index.
*
* This achieves better than the O(log(m+n)) time constraint. It's actually
* O(log(min(m,n))) since we limit the search range to the smaller of the
* two arrays and then binary search that. Best case is one array is empty,
* in which case it's a constant. Worst case is both are equal size, in
* which case it's still just O(log(k)) where k==m==n.
*
* Although note that in the case where the total count is even we'll
* actually be doing it twice, since we'll look up both n and n+1.
*/
public double findMedianSortedArrays(int[] nums1, int[] nums2) {

int totalLength = nums1.length + nums2.length;
int i = (totalLength - 1) / 2;

double result = get(nums1, nums2, i);
if (totalLength % 2 == 0) {
result += get(nums1, nums2, i + 1);
result /= 2.0;
}
return result;
}

double get(int[] nums1, int[] nums2, int i) {
int start = Math.max(i - nums2.length, 0);
int end = Math.min(nums1.length, i);
return getWithRange(nums1, nums2, i, start, end);
}

/**
* Recursive get element by index from dual sorted arrays.
*
* Here 'start' and 'end' are inclusive range boundaries against nums1. The
* range for nums2 can be computed from them, so no need to pass that
* around.
*/
private double getWithRange(int[] nums1, int[] nums2, int i, int start, int end) {

// find the pivots in each array, the indexes for target item candidates
int piv1 = (end - start) / 2 + start;
int piv2 = i - piv1;

// find the largest 'consumed' value in each array
int cons1 = get(nums1, piv1 - 1);
int cons2 = get(nums2, piv2 - 1);

// find the target item candidate values themselves
int next1 = get(nums1, piv1);
int next2 = get(nums2, piv2);

if (cons1 > next2) {
// shift nums1 window left, as it's larger
return getWithRange(nums1, nums2, i, start, piv1 - 1);
}
if (cons2 > next1) {
// shift nums1 window right, as it's smaller
return getWithRange(nums1, nums2, i, piv1 + 1, end);
}
// if both pairs are in order, we found the right candidate pair
return Math.min(next1, next2);
}

/**
* A bounds-safe get which returns MIN or MAX when overflowing off the
* bottom or top respectively. Only safe to use for comparisons.
*/
private int get(int[] nums, int i) {
if (i < 0) {
return Integer.MIN_VALUE;
}

if (i > nums.length - 1) {
return Integer.MAX_VALUE;
}

return nums[i];
}
}
``````

• Hello your solution is very nice. Can you please check my solution and please tell me how it got AC because I think my code is a bit slow. https://discuss.leetcode.com/topic/92960/is-there-anything-wrong-in-my-code/2

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.