0

I wrote the following code to find the median of two sorted arrays and it runs fine locally, but when I submit to leetcode I get runtime error: addition of unsigned offset (stl_vector.h)

here's the code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
double findMedian(vector<int> &nums, int begin, int end){
        int middle = (begin+end)/2;
        return (end - begin + 1) %2 == 0 ? \
        ((double)nums[middle] + (double)nums[middle+1])/2.0 \
        : nums[middle];
}
double divConq(vector<int>& input1, vector<int>& input2,\
               int s1, int e1, int s2, int e2){
        int len1 = e1 - s1 + 1;
        int len2 = e2 - s2 + 1;

        //cout << "length len1: " << len1 << " length len2: " << len2 << '\n';

        //nums1 always longer
        vector<int>& nums1 = len1 >= len2 ? input1 : input2;
        vector<int>& nums2 = len1 >= len2 ? input2 : input1;

        if (nums1 != input1){swap(s1, s2); swap(e1, e2);}

        double med1 = findMedian(nums1, s1, e1);
        double med2 = findMedian(nums2, s2, e2);

        //trivial cases
        if(len1 == 0){return med2;}
        if(len2 == 0){return med1;}

        //base case with list of length 1
        if(len1 == 1 && len2 == 1){return (med1 + med2)/2.0;}
        if(len2 == 1){
                int windowIndexLow = len1 %2 == 0? ((s1+e1)/2)-1 : ((s1+e1)/2);
                int windowIndexHigh = len1 % 2 == 0? windowIndexLow + 2 : windowIndexLow + 1;

                //cout << "length of nums2 is 1" << '\n';

                if(len1 % 2 == 0){
                        if(med2 >= nums1[windowIndexLow] && med2 <= nums1[windowIndexHigh]){
                               return ((double)(med2 + med1)) / 2.0;
                        }
                        else if(med2 > windowIndexHigh){
                                return findMedian(nums1, s1+1, e1);
                        }
                        else if(med2 < windowIndexLow){
                                return findMedian(nums1, s1, e1-1);
                        }
                }
                else{
                        if(med2 >= nums1[windowIndexLow] && med2 <= nums1[windowIndexHigh]){
                                return med2;
                        }
                        else if(med2 > windowIndexHigh){
                                return findMedian(nums1, s1+1, e1);
                        }
                        else if(med2 < windowIndexLow){
                                return findMedian(nums1, s1, e1-1);
                        }
                return -1.0;
                }
        }

        //base case with lists of length 2
        if(len2 == 2 && len1 == 2){
                return (max(nums1[0], nums2[0]) + \
                                min(nums1[1], nums2[1]))/2.0;
        }

        //case 1.1: delete top half of nums1 and some of nums2
        if(len1 <= len2 && med1 >= med2){
                int cut = (len1)/2;
                return divConq(nums1, nums2, s1, e1-cut, s2+cut, e2);
        }
        //case 1.2: delete bottom half of nums1 and some of nums2
        if(len1 <= len2 && med1 <= med2){
                int cut = (len1)/2;
                return divConq(nums1, nums2, s1+cut, e1, s2, e2-cut);
        }
        //case 1.3: delete top half of nums2 and some of nums1
        if(len1 >= len2 && med2 >= med1){
                int cut = (len2)/2;
                return divConq(nums1, nums2, s1+cut, e1, s2, e2-cut);
        }
        //case 1.4: delete bottom half of nums2 and some of nums1
        if(len1 >= len2 && med2 <= med1){
                int cut = (len2)/2;
                return divConq(nums1, nums2, s1, e1-cut, s2+cut, e2);
        }
        return -1.0;
}



public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        return divConq(nums1, nums2, 0, (int)nums1.size() - 1, 0, (int)nums2.size() - 1);
    }
};

Does anyone know why this would be the case and what I can do to fix this submission?

I ran my code locally, word for word identical on the g++ compiler and it works for every test case. I have searched online for this issue and don't see any similar complaints that have been satisfactorily answered. I checked the official solutions but my solutions seems much neater and cleaner and it seems to me like I am respecting the vector structure. Please can someone help me fix this issue?

PaulMcKenzie
  • 34,698
  • 4
  • 24
  • 45
Fergal Hennessy
  • 21
  • 3
    Please read [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) and [Why is "using namespace std;" considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) Whatever or whomever taught you those should not be used for learning in the future. And sites like leetcode or similar so-called "competition" or "judge" sites are not any kind of learning or teaching resource. Don't use them to learn the basics. – Some programmer dude Mar 24 '23 at 06:32
  • *Does anyone know why this would be the case and what I can do to fix this submission?* -- Instead of using `[]` to access the vector elements, use `at()`. If `at()` throws a `std::out_of_range` exception, then you need to debug your code, as it would indicate you are going out-of-bounds. There is also no [mcve] posted -- where is the `main` function with the test data that causes the issue? – PaulMcKenzie Mar 24 '23 at 06:33
  • @Someprogrammerdude Thank you! I do this locally but will not do this on SO in the future. However this did not fix my submission – Fergal Hennessy Mar 24 '23 at 06:37
  • 1
    *I checked the official solutions but my solutions seems much neater and cleaner* -- Your program has a logic bug. You cannot determine this by how neat and clean the code looks, or by doing useless web searches trying to find the program that matches your program. It requires debugging, a skill that for some reason, leetcode and similar sites do not emphasize. – PaulMcKenzie Mar 24 '23 at 06:40
  • Also unrelated to your problem: The casting in `(double)nums[middle] + (double)nums[middle+1])` is not needed. In fact, any time you feel the need to do a C-style cast like that, you should take it as a sign that you're probably doing something wrong, or at least something you should not do. – Some programmer dude Mar 24 '23 at 06:43
  • `if(med2 >= nums1[windowIndexLow] && med2 <= nums1[windowIndexHigh]){` --> `if(med2 >= nums1.at(windowIndexLow) && med2 <= nums1.at(windowIndexHigh)){` -- and similar changes you should be doing. That verifies whether you are going out-of-bounds or not. – PaulMcKenzie Mar 24 '23 at 06:44
  • 1
    As for your problem, begin by replacing all vector access using `[]` with the `at` member function. That will throw an exception if you go out of bounds. An exception that you can catch in a [*debugger*](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems). That will let you locate when and where the problem might be, or at least where it manifests. It will also let you examine variables and see their values to make sure that they are as expected. Compare indexes used with vector sizes. – Some programmer dude Mar 24 '23 at 06:45
  • 1
    If that's not the problem, then you need to use the debugger to step through the code line by line while monitoring variables and their values. Try to simplify expressions, using temporary variables for sub-expressions. And keep track of everything you do using pen and paper. Follow along your design and notes you wrote before the implementation to make sure the code does what it's supposed to do. – Some programmer dude Mar 24 '23 at 06:47
  • And if that doesn't help, start over! Start with a small and simple (basically empty) `main` function. Add one ***little*** piece of code, build it with extra warnings enabled and treat them as errors. Once it builds cleanly test it. Do not continue with the next *little* piece of code until the previous passes all tests. When there's a problem, you know where it is and can more easily debug it and fix it. – Some programmer dude Mar 24 '23 at 06:48
  • Not related to your question but all those backslashes are unnecessary. With the exception of single line comments and macro definitions C++ is not a line oriented language, and you can place newlines anywhere that you can place other whitespace – john Mar 24 '23 at 06:52
  • `if (nums1 != input1){swap(s1, s2); swap(e1, e2);}` is inefficient since it compares two vectors. In this context comparing their addresses works as well `if (&nums1 != &input1){swap(s1, s2); swap(e1, e2);}` – john Mar 24 '23 at 06:55
  • 2
    Oh and a tip regarding debugging: Since it's almost line-based, don't try to put too much on a single line. Especially, don't put multiple statements on a single line, one statement per line makes it much easier to debug (and often also easier to read and understand). – Some programmer dude Mar 24 '23 at 06:57
  • 1
    As for the bug, I'm guessing it is the 'trivial cases'. Your ``findMedian` function causes an array out of bounds error when given a ero length array. If you swap the `findMedian` calls with the trivial case check you might fix the error. – john Mar 24 '23 at 07:00
  • Beginners usually find this hard to believe, but it's actually much easier to avoid off-by-one bugs if you stick to the conventional half-open intervals than closed intervals. They're not conventional without reason. (See Dijkstra's classic [Why numbering should start at zero](https://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html) – molbdnilo Mar 24 '23 at 08:50
  • Thank you so much everyone for your help! I fixed the problem and will be using better coding practices in the future :) – Fergal Hennessy Mar 25 '23 at 20:50

1 Answers1

0

Your bug is probably related to what you call the trivial case. Given a zero length array the findMedian function causes an array out of bounds exception.

Perhaps then you may fix the bug by swapping the trivial case check with the calls to findMedian, i.e.

    //trivial cases
    if(len1 == 0){return -1.0;}
    if(len2 == 0){return -1.0;}

    double med1 = findMedian(nums1, s1, e1);
    double med2 = findMedian(nums2, s2, e2);

Although I don't understand enough about the problem to know if a dummy return value of -1.0 is correct.

john
  • 85,011
  • 4
  • 57
  • 81