# [C++] Algorithm returns correct result on local machine but got Wrong Answer on the judge.

• I have tested my following code on my local machine it always get correct result, but I am not sure why it always gets Wrong Answer on the judge?

``````class Solution {
public:

// dutch flag partition
void three_way_partition(vector<int> &nums, int pivot_value) {
int l=-1,m=0,r=nums.size();
while(m<r) {
if(nums[r] < pivot_value)
swap(nums[++l], nums[m++]);
else if(nums[r] > pivot_value)
swap(nums[--r], nums[m]);
else
++m;
}
}

// partition nums by value nums[pivot_index] and return the newest pivot index
int partition(vector<int> &nums, int pivot_index, int left, int right) {
swap(nums[right], nums[pivot_index]);

int l=left-1, r=left;
while(r < right) {
if(nums[r]>=nums[right])
r++;
else
swap(nums[++l],nums[r++]);
}
swap(nums[l+1], nums[right]);
return l+1;
}

// find kth(zero based) smallest element in nums
int select(vector<int> &nums, int k) {
int left=0, right = (int)nums.size() - 1;

while(left <= right) {
default_random_engine gen((random_device())());
uniform_int_distribution<int> dis(left, right);
int pivot_index = dis(gen);
int m = partition(nums, pivot_index, left, right);
if(m == k)
return nums[m];
if(m < k)
left = m+1;
else
right = m-1;
}
return -1;
}

void wiggleSort(vector<int>& nums) {
int size = nums.size();
if(size <=1)
return;

vector<int> tmp(size);
int i=(size+1)/2 -1 ,j=size-1,k=0;
int median = select(nums, i);
three_way_partition(nums, median);
while(k<size) {
tmp[k] = k&1 ? nums[j--] : nums[i--];
k++;
}

for(int u=0;u<size;u++)
nums[u] = tmp[u];
}

};
``````

• @newtt See if this helps:
https://leetcode.com/faq/#different-output

Try to check for array out of bound access, as that would cause undefined behavior.

• Of course you may get correct answer on local machine because you use random pivot. I think you may ignore the real hard part which is reordering from the semi-sorted array (small-mid-large).

• I think I found the issue I have a typo in the three_way_partition below is the correct algo that Accepted.

'''
while(m<r) {
if(nums[m] < pivot_value)
swap(nums[++l], nums[m++]);
else if(nums[m] > pivot_value)
swap(nums[--r], nums[m]);
else
++m;
}
'''

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