Leetcode Random Challenge - Wk5 (4)

C

Cicero

Expert Member
Joined
Jul 20, 2010
Messages
2,286
Reaction score
14
Location
Coastal
Hi all,

New challenge time. Like a ghost town last week, haha.

This week though, I've chosen a medium difficulty problem from the beginning of the problem pool, as some of the later questions can be a little annoying, and the early ones are more popular and have many more community submissions.

4. Median of Two Sorted Arrays - https://leetcode.com/problems/median-of-two-sorted-arrays/description/
There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:
Code: 
nums1 = [1, 3]
nums2 = [2]
The median is 2.0

Example 2:
Code: 
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
Click to expand...

How it works/Rules:
  • We use the random question picker (sometimes), and all attempt it, one question a week.
  • No cheating/looking at the editorial solution until your soln is accepted on leetcode, and you're convinced you can't get it any quicker.
  • Language is up to you, this may help people appreciate other languages as well
  • Only post your time taken, language, and percentage of submissions beaten at first. Use spoiler+php tags for your code.
 
Ok, I'll kick this off:

C, 28ms, beats 94.79%
But I must admit, the time calculation from leetcode for this challenge has been totally dodgy. Jumps around all over the place whilst I was trying to get this a bit better.

First attempt was just a full merge as below - 32ms beats 67.18%.
PHP: 
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int arrSize, nums1Ind, nums2Ind, arrInd;
    int *arr;
    
    arrSize = nums1Size + nums2Size;
    arr = (int*)malloc(arrSize*sizeof(int));
    
    nums1Ind = 0;
    nums2Ind = 0;
    arrInd = 0;
    
    while ((nums1Ind < nums1Size) && (nums2Ind < nums2Size)) {
        if (nums1[nums1Ind] < nums2[nums2Ind]) {
            arr[arrInd++] = nums1[nums1Ind++];
        } else {
            arr[arrInd++] = nums2[nums2Ind++];
        }
    }
    
    if (nums1Ind < nums1Size) memcpy(&arr[arrInd], &nums1[nums1Ind], (nums1Size-nums1Ind)*sizeof(int));
    if (nums2Ind < nums2Size) memcpy(&arr[arrInd], &nums2[nums2Ind], (nums2Size-nums2Ind)*sizeof(int));
    
    if (arrSize%2) {
        return (double)arr[arrSize/2];
    } else {
        nums1Ind = arrSize/2-1;
        //printf("%i + %i, %i", arr[nums1Ind],arr[nums1Ind+1],arrSize);
        return (((double)arr[nums1Ind]+(double)arr[nums1Ind+1])/2);        
    }
    
    return 0;
}

Final 28ms submission, without the extra memory usage, and only running to the median index. Still think this could be much better because I don't like how long it is and too many nested if's, but I lack the time to really get into it:
PHP: 
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int arrSize, nums1Ind, nums2Ind, arrInd, medInd;
    double med[2];
    double result;
    
    arrSize = nums1Size + nums2Size;   
    
    nums1Ind = 0;
    nums2Ind = 0;
    arrInd = 0;
    
    medInd = arrSize/2;
    
    if (nums1Size == 0) {
        if (arrSize%2) {
            result = nums2[medInd];
        } else {
            result = (((double)nums2[medInd-1]+(double)nums2[medInd])/2);        
        }
        return result;
    }
    
    if (nums2Size == 0) {
        if (arrSize%2) {
            result = nums1[medInd];
        } else {
            result = (((double)nums1[medInd-1]+(double)nums1[medInd])/2);        
        }
        return result;
    }
    
    while ((nums1Ind < nums1Size) && (nums2Ind < nums2Size) && (arrInd <= medInd)) {
        if (nums1[nums1Ind] < nums2[nums2Ind]) {
            if (arrInd == (medInd-1)) {
                med[0] = nums1[nums1Ind];
            }
            if (arrInd == medInd) {
                med[1] = nums1[nums1Ind];
            }
            
            nums1Ind++;
        } else {
            if (arrInd == (medInd-1)) {
                med[0] = nums2[nums2Ind];
            }
            if (arrInd == medInd) {
                med[1] = nums2[nums2Ind];
            }
            
            nums2Ind++;
        }
        arrInd++;
    }
    
    if (arrInd == medInd) {
        arrInd++;
        if (nums1Ind < nums1Size) {
            med[1] = nums1[nums1Ind++];
        }
        if (nums2Ind < nums2Size) {
            med[1] = nums2[nums2Ind++];
        }
    }
    
    if (arrInd < medInd) {        
        /* median lies fully in either nums1/2 */
        if (nums1Ind < nums1Size) {
            medInd = nums1Ind+(medInd-arrInd);
            med[0] = nums1[medInd-1];
            med[1] = nums1[medInd];
        }
        if (nums2Ind < nums2Size) {    
            medInd = nums2Ind+(medInd-arrInd);
            med[0] = nums2[medInd-1];
            med[1] = nums2[medInd];
        }
    }
    
    if (arrSize%2) {
        result = med[1];
    } else {
        result = (med[0]+med[1])/2;        
    }
    return result;
}
 
Last edited:
Also, could someone have a look at what I've done and tell me if it even gets close to satisfying the O(log(m+n)) requirement? My bigO understanding is lacking.
 
Cicero said:
Also, could someone have a look at what I've done and tell me if it even gets close to satisfying the O(log(m+n)) requirement? My bigO understanding is lacking.
Click to expand...

Both of your solutions look to be O(n+m). You will need to do a form of binary search to get the target complexity.
 
cguy said:
Both of your solutions look to be O(n+m). You will need to do a form of binary search to get the target complexity.
Click to expand...
Yeah, I see what you mean, I'll have to put more thought into it, just goes to show my lack of algorithm knowledge.

I knew the first one was O(m+n) as its a full merge, but I thought the second was O((m+n)/2), if such a thing, as it only loops until the median. Still...not log(n+n) as per requirement.
 
Last edited:
Cicero said:
Yeah, I see what you mean, I'll have to put more thought into it, just goes to show my lack of algorithm knowledge.

I knew the first one was O(m+n) as its a full merge, but I thought the second was O((m+n)/2), if such a thing, as it only loops until the median. Still...not log(n+n) as per requirement.
Click to expand...

O(c*f(n)) is equal to O(f(n)). I.e. Two algorithms that differ in run time by a (positive) constant multiplier have the same order.
 
Swift submission:
Short and simple, but not the fastest; 89ms beats 35.2% of Swift submissions.
PHP: 
func findMedianSortedArrays(_ nums1: [Int], _ nums2: [Int]) -> Double {
  let merge = (nums1 + nums2).sorted(), n = merge.count
  return n % 2 != 0 ? Double(merge[(n - 1) / 2]) : Double(merge[(n - 1) / 2] + merge[n / 2]) / 2
}
Not short or simple (recursive); but it's quite fast; 23ms beats 100% of Swift submissions.
PHP: 
func findMedianSortedArrays(_ nums1: [Int], _ nums2: [Int]) -> Double {
  let (c1, c2) = (nums1.count, nums2.count), c = c1 + c2
  func bSeek(_ i1: Int, _ i2: Int, _ offset: Int) -> Int {
    if i1 >= c1 { return nums2[i2 + offset - 1] }
    if i2 >= c2 { return nums1[i1 + offset - 1] }
    if offset == 1 { return min(nums1[i1], nums2[i2]) }
    return (i1 + offset / 2 - 1 >= c1 ? Int.max : nums1[i1 + offset / 2 - 1]) < (i2 + offset / 2 - 1 >= c2 ? Int.max : nums2[i2 + offset / 2 - 1])
      ? bSeek(i1 + offset / 2, i2, offset - offset / 2)
      : bSeek(i1, i2 + offset / 2, offset - offset / 2)
  }
  return c % 2 == 0
    ? Double(bSeek(0, 0, c / 2) + bSeek(0, 0, c / 2 + 1)) / 2.0
    : Double(bSeek(0, 0, c / 2 + 1))
}
Alternative fast solution (while loop as opposed to recursion); 25ms beats 99.5% of Swift submissions.
PHP: 
func findMedianSortedArrays5(_ nums1: [Int], _ nums2: [Int]) -> Double {
  let (c1, c2) = (nums1.count, nums2.count), mid = (c1 + c2 + 1) / 2
  guard !(c1 > c2) else { return findMedianSortedArrays5(nums2, nums1) }
  var idx = (left: 0, right: c1)
  while idx.left <= idx.right {
    let i = (idx.left + idx.right) / 2, j = mid - i
    guard !(j > 0 && i < c1 && nums2[j - 1] > nums1[i]) else { idx.left = i + 1; continue }
    guard !(i > 0 && j < c2 && nums1[i - 1] > nums2[j]) else { idx.right = i - 1; continue}
    let leftMax = i == 0 ? nums2[j - 1] : j == 0 ? nums1[i-1] : max(nums1[i - 1], nums2[j - 1])
    guard (c1 + c2) % 2 == 0 else { return Double(leftMax) }
    return Double(leftMax + (i == c1 ? nums2[j] : j == c2 ? nums1[i] : min(nums1[i], nums2[j]))) / 2.0
  }
  return 0.0
}
 
Last edited:
You must log in or register to reply here.
Back
Top
Sign up to the MyBroadband newsletter
X