Why did I get stack overflow in my program?


  • 0
    A
    public class Solution {
    public double findMedianSortedArrays(int A[], int B[]) {
        //log n algorithm we need a tree structure
        //no time to construct a tree as takes O(m+n)
        //sorted array they are bst
        //3 4 5  A 
        //6 7      B
        if(A.length>B.length){
            return findMRecursive(B,0,B.length-1,A,0,A.length-1);
        }
        else{
            return findMRecursive(A,0,A.length-1,B,0,B.length-1);
        }
    }
    
    public double findMRecursive(int A[],int startA,int endA, int B[],int startB,int endB){
        //deal with some base cases:
        //A = 0,B = 0
        //A = 0,B !=0
        if(endA==-1){
            return B[(endB-startB)/2];
        }
        //A = 1, B = 1
        if(startA==endA && startB==endB){
            return (A[startA] + B[startB])/2;
        }
        //A = 1, B = odd
        if(startA==endA && (endB - startB)%2==0){
            int mid = (endB - startB)/2;
            return (B[mid] + mo3(A[startA],B[mid-1],B[mid+1]))/2;
        }
        //A = 1, B = even
        if(startA==endA && (endB - startB)%2==1){
            int mid = (endB - startB)/2;
            return mo3(A[startA],B[mid],B[mid+1]);
        }
        //A = 2, B = 2
        if(endA-startA==1 && endB-startB==1){
            return mo4(A[startA],A[endA],B[startB],B[startB]);
        }
        //A = 2, B = odd
        if(endA-startA==1 && (endB - startB)%2==0){
            int mid = (endB - startB)/2;
            return mo3(Math.min(A[startA],B[mid-1]),B[mid],Math.max(A[endA],B[mid+1]));
        }
        //A = 2, B = even
        if(endA-startA==1 && (endB - startB)%2==1){
            int mid = (endB - startB)/2;
            return mo4(Math.min(A[startA],B[mid-1]),B[mid],B[mid+1],Math.max(A[endA],B[mid+2]));
        }
        //A is the longer array
        //compare A median and B median 
        //if A > B then cut the left half of B
        //if A <= B then cut the right half of 
        //and}then cut the same length of A in the opposite side
        //do recursively
        int midA = (endA - startA)/2;
        int midB = (endB - startB)/2;
        
        if(A[midA]>B[midB]){
            return findMRecursive(A,startA,midA,B,startB+(endA-midA),endB);
        }
        
            return findMRecursive(A,midA,endA,B,startB,endB-(midA-startA));
        
        
    }
    //help funciton
    public double mo3(int a,int b,int c){
        return a+b+c-Math.max(Math.max(a,b),c) - Math.min(Math.min(a,b),c);
    }
    
    public double mo4(int a,int b,int c,int d){
        int max = Math.max(Math.max(Math.max(a,b),c),d);
        int min = Math.min(Math.min(Math.min(a,b),c),d);
        
        return (a+b+c+d-max-min)/2;
    }
    

    }

    I got a runtime error stackoverflow in my program when encountered the input test case: [3 3 3 3],[3 3 3 3]. It said I got stack overflow here return findMRecursive(A,0,A.length-1,B,0,B.length-1);

    Here is the idea of my algorithm: Assume A is the shorter array.
    I have 7 base cases for the program

    1. A = 0,B !=0
    2. A = 1, B = 1
    3. A = 1, B = odd
    4. A = 1, B = even
    5. A = 2, B = 2
    6. A = 2, B = odd
    7. A = 2, B = even

    If the input is not in these base cases, I will compare the median of the two arrays and if medianA is the bigger one, I will cut the right side of array A and cut the left side of array B of the same length of the right side of array A. And put them into the recursion. if medianA is the smaller one, i will do the opposite. My algortihm takes O(log(n)+log(m))


  • 1
    U

    There is an infinite loop in your code for the input case [3 3 3 3], [3 3 3 3].

    Consider the startA, endA, startB, endB values in the recursion.

    First iteration: startA = 0, endA = 3, startB = 0, endB = 3. No problem.

    Second iteration: startA = 1, endA = 3, startB = 0, endB = 2
    Then midA = (3 - 1) / 2 = 1
    The code will go to this branch

    findMRecursive(A,midA,endA,B,startB,endB-(midA-startA));
    

    Third iteration: startA = 1, endA = 3, startB = 0, endB = 2 - (1 - 1) = 2

    You see the parameters are exactly the same as those in round 2. The infinite loop begins.


  • 0
    A

    thank so much!


Log in to reply
 

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