Runtime Error on OJ but running correct locally??


  • 0
    S

    Hi,

    my solution runs fine on my Visual Studio 2013 but keeps seeing runtime error on OJ.
    I'm testing exactly the same test case that OJ is complaining about.
    not sure if anyone had this issue before??

    The implementation is basically using binary search to find the pivot, and then use another basic binary search to find the target. hope it's easy to read:

    class Solution {
    public:
        int search(int input[], int n, int target) {
            A = input;
            int pivotIdx = findPivotIdx(0, n);
    
            if (pivotIdx == -1){
                // a normal sorted array
                return binarySearch(0, n, target);
            }
            else if (A[pivotIdx] == target){
                return pivotIdx;
            }
            else{
                // A[pivotIdx] is the smallest
                if ((target > A[n - 1]) && (target <= A[pivotIdx - 1])){
                    // in first part
                    return binarySearch(0, pivotIdx, target);
                }
                else if ((target > A[pivotIdx]) && (target <= A[n - 1])){
                    // in second part
                    return binarySearch(pivotIdx + 1, n - 1 - pivotIdx, target);
                }
                else{
                    return -1;
                }
            }
        }
        int* A = NULL;
        int findPivotIdx(int startIdx, int size){
            // let the pivot to be the true smallest element
            if (size <= 1){
                return -1;
            }
            else if (size == 2){
                if (A[startIdx] > A[startIdx + 1]){
                    return startIdx + 1;
                }
                else{
                    return -1;
                }
            }
            else{
                // more than 2 elements
                if (A[startIdx + 1] < A[startIdx]){
                    return startIdx + 1;
                }
                else if (A[startIdx + size - 1] < A[startIdx + size - 2]){
                    return startIdx + size - 1;
                }
            }
    
            // recursive
            int middleIdx = startIdx + (size >> 1);
            if ((A[middleIdx] < A[startIdx + size - 1]) && (A[startIdx + size - 1] < A[startIdx])){
                // middle idx is the pivot
                return middleIdx;
            }
            else if (A[middleIdx] > A[middleIdx + 1]){
                return middleIdx + 1;
            }
            else if ((A[startIdx] > A[middleIdx]) && (A[middleIdx] > A[startIdx + size - 1])){
                // pivot is in the left, startIdx,...., (middleIdx - 1)
                return findPivotIdx(startIdx, middleIdx - startIdx);
            }
            else{
                // A[size - 1] > A[middleIdx] > A[startIdx]
                // pivot is in the right, (middleIdx + 1),...., (size - 1)
                return findPivotIdx(middleIdx + 1, size - 1 - middleIdx);
            }
    
        }
    
    
        int binarySearch(int startIdx, int size, int target){
            // base cases
            if (size == 0){
                return -1;
            }
            else if (size == 1){
                if (target == A[startIdx]){
                    return startIdx;
                }
                else{
                    return -1;
                }
            }
            else{
                // size >= 2
                if (target == A[startIdx]){
                    // first element
                    return startIdx;
                }
                else if (target == A[startIdx + size - 1]){
                    // last element
                    return startIdx + size - 1;
                }
                else if ((target < A[startIdx]) || (target > A[startIdx + size - 1])){
                    // out of range
                    return -1;
                }
            }
    
            // recursive
            int middleIdx = startIdx + (size >> 1);
            if (target == A[middleIdx]){
                return middleIdx;
            }
            else if (target > A[middleIdx]){
                return binarySearch(middleIdx + 1, size - 1 - middleIdx, target);
            }
            else{
                // target < A[middleIdx]
                return binarySearch(startIdx, middleIdx - startIdx, target);
            }
    
        }
    };

Log in to reply
 

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