Skip to content

Bug Report for median-of-two-sorted-arrays #6099

Description

@small13999

Bug Report for https://neetcode.io/problems/median-of-two-sorted-arrays

My solution passed all the tests, but it's not correct:
impl Solution {
pub fn find_median_sorted_arrays(nums1: Vec, nums2: Vec) -> f64 {
if nums1.is_empty() {
return (nums2[nums2.len()/2] + nums2[(nums2.len()-1)/2]) as f64 / 2.0;
} else if nums2.is_empty() {
return (nums1[nums1.len()/2] + nums1[(nums1.len()-1)/2]) as f64 / 2.0;
}

    let mut l1 = 0;
    let mut l2 = 0;
    let mut r1 = nums1.len() - 1;
    let mut r2 = nums2.len() - 1;

    loop {
        let len1 = r1 - l1 + 1;
        let len2 = r2 - l2 + 1;

        if nums1[l1] >= nums2[r2] {
            if len1 == len2 {
                return (nums1[l1] + nums2[r2]) as f64 /2.0;
            }

            if len1 > len2 {
                let ind1 = (len1+len2) / 2 - len2;
                let ind2 = (len1+len2-1) / 2 - len2;
                return (nums1[l1+ind1] + nums1[l1+ind2])as f64/2.0;
            } else {
                let ind1 = (len1+len2) / 2;
                let ind2 = (len1+len2-1) / 2;
                return (nums2[l2+ind1] + nums2[l2+ind2])as f64/2.0;
            }
        } else if nums2[l2] >= nums1[r1] {
            if len1 == len2 {
                return (nums1[l2] + nums2[r1])as f64/2.0;
            }

            if len1 > len2 {
                let ind1 = (len1+len2) / 2;
                let ind2 = (len1+len2-1) / 2;
                return (nums1[l1+ind1] + nums1[l1+ind2])as f64/2.0;
            } else {
                let ind1 = (len1+len2) / 2 - len1;
                let ind2 = (len1+len2-1) / 2 - len1;
                return (nums2[l2+ind1] + nums2[l2+ind2])as f64/2.0;
            }
        } 


        let middle1_left = (l1+r1)/2;
        let middle1_right = (l1+r1+1)/2;
        let middle2_left = (l2+r2)/2;
        let middle2_right = (l2+r2+1)/2;
        let med1 = (nums1[middle1_left] + nums1[middle1_right]) as f64 / 2.0;
        let med2 = (nums2[middle2_left] + nums2[middle2_right]) as f64 / 2.0;
        if med1 == med2 {
            return med1;
        }
        let med = (med1 + med2) / 2.0; 
        if med1 > med2 {
            r1 = middle1_right - 1 as usize;
            l2 = middle2_left + 1 as usize;
        } else {
            l1 = middle1_left + 1 as usize;
            r2 = middle2_right - 1 as usize;
        }

    }
}

}

Counterexample: nums1 = [1], nums2 = [0, 3]

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions