Mysterious runtime error when submitting


  • 0
    N

    I was able to compile and run the code below on my computer as well as on Leetcode with custom test cases, but Leetcode gave me an unspecified runtime error when submitted and said the last input was [2,3,3,2,2,2,1,1]. When I tried that input as one of the custom test cases, it was fine! I can't think of anything else that might be happening behind the scene. Thanks for your help!

    class Solution {
    public:
        void wiggleSort(vector<int>& nums) {
        	int n = nums.size();
        	if (n == 0 || n == 1) return;
        
        	// k is the upper median value. Since we assume all inputs have valid answers,
        	// putting a number >= k next to a number < k will create wiggle sort
        	int upper_median = (n % 2 == 0) ? (int) (n/2) : (int) (n/2 + 2);
        	int k = randomizedSelect(nums, 0, n - 1, upper_median);
        
        	// cout << k << endl;
        	// cout << "------" << endl;
        	// for (int i = 0; i < n; i++) {
        	// 	cout << nums[i] << " ";
        	// }
        	// cout << endl;
        
        	// count numbers of smaller and bigger values than the upper median
        	int count_smaller = 0, count_bigger = 0;
        	for (int i = 0; i < n; i++) {
        		if (nums[i] < k) count_smaller++;
        		else if (nums[i] > k) count_bigger++;
        	}
        	int num_bigger = (int) (n / 2);
        	int count_k = n - count_smaller - count_bigger; // frequency of upper median
        	
        	// put smaller values in their places
        	vector<int> tmp_nums = nums;
        	int j = (n % 2 == 0) ? (n - 2) : (n - 1);
        	for (int i = 0; i < n; i++) {
        		if (tmp_nums[i] < k) {
        			nums[j] = tmp_nums[i];
        			j -= 2;
        		}
        	}
        
        	// if there are not enough smaller values, treat some median values k as smaller
        	while (count_smaller <  num_bigger) {
        		nums[j] = k;
        		j -= 2;
        		count_smaller++;
        		count_k--;
        	}
        
            // put the rest in their places
        	j = (n % 2 == 0) ? (n - 1) : (n - 2);
        	for (int i = 0; i < count_k; i++) {
        		nums[j] = k;
        		j -= 2;
        	}
        
        	for (int i = 0; i < n; i++) {
        		if (tmp_nums[i] > k) {
        			nums[j] = tmp_nums[i];
        			j -= 2;
        		}
        	}
        	
        			
        	// cout << "------" << endl;
        	// for (int i = 0; i < n; i++) {
        	// 	cout << nums[i] << " ";
        	// }
        	// cout << endl;
        }
            
        int randomizedSelect(vector<int>& nums, int p, int r, int i) {
        	if (p == r) return nums[p];
        	int q = randomizedPartition(nums, p, r);
        	
        	int k = q - p + 1;
        	if (i == k) return nums[q];
        	else if (k > i) return randomizedSelect(nums, p, q - 1, i);
        	else return randomizedSelect(nums, q + 1, r, i - k);
        }
            
        int randomizedPartition(vector<int>& nums, int p, int r) {
        	int q = p + (rand() % (r - p + 1)); // random index between p and r
        	int tmp = nums[r];
        	nums[r] = nums[q];
        	nums[q] = tmp;
                
        	int i = p - 1;
        	for (int j = p; j < r; j++) {
        		if (nums[j] <= nums[r]) {
        			i++;
                        
        			tmp = nums[i];
        			nums[i]= nums[j];
        			nums[j] = tmp;
        		}
        	}
        	tmp = nums[i + 1];
        	nums[i+1] = nums[r];
        	nums[r] = tmp;
        	return i + 1;
        }
    
    }; 
    

Log in to reply
 

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