Insane slightly non-deterministic optimal solution in C#


  • 0
    M

    I can't believe this passed. It essentially binary searches each array with prospective answers and depending on how many values there are to the left and right of the prospective answers, determines whether the binary search should move left or right. There were a lot of edge cases to handle, including two cases where the lower bound would cross the upper bound of the search, so I reinitialized the lower bound with a random index haha. So ~O(log(m + n)), with high probability. Another interesting case was where it might guess a solution early, for instance in the case [1] ,[2,3,4], since 1 + 4 = 5 and 5 / 2 = 2.5 (the actual median). This was bad on one of the really large tests where it got a value of like 162440.6 instead of 162440.5. To correct for this, I binary search each array for the prospective answer and compute the actual median from the surrounding values (there's a maximum of four). My binary search is based off of the C# binary search (https://msdn.microsoft.com/en-us/library/w4e7fxsh(v=vs.110).aspx).

    public class Solution {
        
        private static Random rgen = new Random();
        
        public double FindMedianSortedArrays(int[] nums1, int[] nums2)
        {
            if (nums1.Length == 0)
            {
                return SimpleMedian(nums2);
            }
            
            if (nums2.Length == 0)
            {
                return SimpleMedian(nums1);
            }
            
            double med1 = SimpleMedian(nums1);
            double med2 = SimpleMedian(nums2);
            
            if (med1 == med2)
            {
                return med1;
            }
            
            int upper1 = nums1.Length - 1;
            int lower1 = 0;
            int upper2 = nums2.Length - 1;
            int lower2 = 0;
            int mid1, mid2, midVal1, midVal2, valsToLeft1, valsToLeft2, valsToLeft3, valsToRight1, valsToRight2, valsToRight3;
            double midVal3;
            mid1 = (lower1 + upper1) >> 1;
            mid2 = (lower2 + upper2) >> 1;
            int prevVal1 = nums1[mid1];
            int prevVal2 = nums2[mid2];
            
            for (int ind = 0; ; ind++)
            {
                mid1 = (lower1 + upper1) >> 1;
                mid2 = (lower2 + upper2) >> 1;
                
                midVal1 = nums1[mid1];
                midVal2 = nums2[mid2];
                midVal3 = (double)(midVal1 + midVal2)/2.0;
                
                int dum1;
                int dum2;
                
                if (IsValidMedian(nums2, nums1.Length, mid1, (double)midVal1, out valsToLeft1, out valsToRight1))
                {
                    return midVal1;
                }
                
                if (IsValidMedian(nums1, nums2.Length, mid2, (double)midVal2, out valsToLeft2, out valsToRight2))
                {
                    return midVal2;
                }
                
                double avg1 = (double)(midVal1 + prevVal1)/2.0;
                if (IsValidMedian(nums1, nums2, avg1, out dum1, out dum2))
                {
                    return MedianNearVal(nums1, nums2, avg1);
                }
                
                double avg2 = (double)(midVal2 + prevVal2)/2.0;
                if (IsValidMedian(nums1, nums2, avg2, out dum1, out dum2))
                {
                    return MedianNearVal(nums1, nums2, avg2);
                }
                
                if (IsValidMedian(nums1, nums2, midVal3, out valsToLeft3, out valsToRight3))
                {
                    return MedianNearVal(nums1, nums2, midVal3);
                }
                
                if ((ind & 1) > 0)
                {
                    AdvanceOneStep(nums1.Length, mid1, valsToLeft1, valsToRight1, ref upper1, ref lower1);
                    prevVal1 = midVal1;
                }
                else
                {
                    AdvanceOneStep(nums2.Length, mid2, valsToLeft2, valsToRight2, ref upper2, ref lower2);
                    prevVal2 = midVal2;
                }
            }
        }
        
        private static double MedianNearVal(int[] nums1, int[] nums2, double val)
        {
            int ind1 = Normalize(BinarySearch(val, nums1));
            int ind2 = Normalize(BinarySearch(val, nums2));
    
            List<int> vals = new List<int>(4);
            vals.AddRange(ValsOnEitherSide(nums1, ind1));
            vals.AddRange(ValsOnEitherSide(nums2, ind2));
            vals.Sort();
            
            for(int i = 0; i < (vals.Count - 1); i++)
            {
                if (val > vals[i] && val < vals[i + 1])
                {
                    return (double)(vals[i] + vals[i + 1])/2.0;
                }
            }
            
            return val;
        }
        
        private static List<int> ValsOnEitherSide(int[] nums, int ind)
        {
            int x, y;
            List<int> els = new List<int>(2);
            if (InBounds(nums, ind))
            {
                els.Add(nums[ind]);
            }
            
            if (InBounds(nums, ind - 1))
            {
                els.Add(nums[ind - 1]);
            }
            
            return els;
        }
        
        private static bool InBounds(int[] nums, int ind)
        {
            return ind >= 0 && ind < nums.Length;
        }
        
        private void AdvanceOneStep(int len, int mid, int valsToLeft, int valsToRight, ref int upper, ref int lower)
        {
            if (valsToLeft > valsToRight)
            {
                upper = Math.Max(mid - 1, 0);
            }
            else if (valsToLeft < valsToRight)
            {
                lower = Math.Min(mid + 1, len - 1);
            }
            
            if (lower > upper)
    		{
    			upper = rgen.Next(0, len);
    		}
        }
        
        private static bool IsValidMedian(int[] nums1, int[] nums2, double val, out int valsToLeft, out int valsToRight)
        {
            return IsValidMedian(nums2, nums1.Length, BinarySearch(val, nums1), val, out valsToLeft, out valsToRight);
        }
        
        private static bool IsValidMedian(int[] nums, int len1, int ind1, double val, out int valsToLeft, out int valsToRight)
        {
            int ind2 = BinarySearch(val, nums);
            
            valsToLeft = Normalize(ind1) + Normalize(ind2);
            valsToRight = len1 + nums.Length - 2 - Math.Min(Normalize(ind1), len1 - 1) - Math.Min(Normalize(ind2), nums.Length - 1);
            
            if (ind1 < 0 && Normalize(ind1) != len1)
            {
                valsToRight++;
            }
            
            if (ind2 < 0 && Normalize(ind2) != nums.Length)
            {
                valsToRight++;    
            }
            
            if (ind2 > 0 && ind1 > 0)
            {
                if (valsToLeft > valsToRight)
                {
                    valsToRight++;
                }
                else
                {
                    valsToLeft++;
                }
            }
            
            return valsToLeft == valsToRight;
        }
        
        private static int Normalize(int x)
        {
            return x < 0 ? ~x : x;
        }
    
        private static int BinarySearch(double num, int[] arr)
        {
            if (arr.Length == 0)
            {
                return ~1;
            }
            
            int upper = arr.Length - 1;
            int lower = 0;
            int midInd = 0;
            double midVal = 0;
            
            while (lower <= upper)
            {
                midInd = (lower + upper) >> 1;
                midVal = (double)arr[midInd];
                
                if (num > midVal)
                {
                    lower = midInd + 1;
                }
                else if (num < midVal)
                {
                    upper = midInd - 1;
                }
                else
                {
                    return midInd;
                }
            }
            
            if (lower == arr.Length)
            {
                return ~(arr.Length);
            }
            else
            {
                if(num > midVal)
                {
                    return ~(midInd + 1);
                }
                else
                {
                    return ~(midInd);
                }
            }
        }
        
        private static double SimpleMedian(int[] arr)
        {
            bool oddLen = (arr.Length & 1) > 0;
            int mid = (arr.Length - 1) >> 1;
            if (oddLen)
            {
                return (double)arr[mid];    
            }
            else
            {
               return ((double)arr[mid] + (double)arr[mid + 1]) / 2.0;
            }
        }
    }
    

Log in to reply
 

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