Runtime error on the very long input. Works fine on dev c++ compiler. Used qsort.


  • 1
    H
    typedef struct indval{
        int val;
        int index;
    }indval;
    
    int comp(const void *p1, const void * p2){
        indval * iv1 = (indval *)p1;
        indval * iv2 = (indval *)p2;
        return (*iv1).val - (*iv2).val;
    }
    
    class Solution {
    public:
        vector<int> twoSum(vector<int> &numbers, int target) {
            vector<int> v;
            sort(numbers.begin(), numbers.end());
            int start = 0, end = numbers.size()-1;
            if(numbers.size() == 0){
                return v;
            }
            indval iv[numbers.size()];
            for(int i=0; i<numbers.size(); i++){
                iv[i].index = i;
                iv[i].val = numbers[i];
            }
            qsort(iv, numbers.size(), sizeof(indval), comp);
            int sum;
            while(start < end){
                sum = iv[start].val + iv[end].val;
                if(sum == target){
                	if(iv[start].index < iv[end].index){
                		v.push_back(iv[start].index + 1);
    					v.push_back(iv[end].index + 1);	
                	}
                    else{
                    	v.push_back(iv[end].index + 1);
    					v.push_back(iv[start].index + 1);	
                    }
                }
                if(sum > target){
                    end--;
                }
                else{
                    start ++;
                }
            }
            return v;
        }
    };

  • 0
    V

    The run time error might be caused due to the large size of the input array.The Random Access Memory might be insufficient to perform quick sort on such large inputs as in the best case an in-place quick sort require O(log n) extra space on average and O(n) extra space in the worst case.


  • 0
    H

    Hmm.. maybe that might be the case. Thanks for pointing out.


  • 1
    D

    In

    int comp(const void *p1, const void * p2){
        indval * iv1 = (indval *)p1;
        indval * iv2 = (indval *)p2;
        return (*iv1).val - (*iv2).val;
    }
    

    return (*iv1).val - (*iv2).val; may cause integer overflow

    change it to

    return ((*iv1).val > (*iv2).val) ? 1 : -1;
    

    should fix the issue


Log in to reply
 

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