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


  • 0
    E

    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];
    	}
    }
    

  • 0

    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


Log in to reply
 

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