# O(n) time and cheating O(1) space solution, will there be a real O(1) solution?

• ``````class Solution {
public:
void wiggleSort(vector<int>& nums) {
// Only four Line
if (2>(n = nums.size())) return;
r_start = n/2;
dfs(nums, find_medin(nums));
re_order(nums);
}
private:
int n;
int r_start;
int pivot(vector<int> &nums, int i, int j) {
assert(i<j);
swap(nums[i],nums[(i+j)/2]);
int idx = i++;
int val = nums[idx];
while (i<j) {
if (nums[i]<=val) i++;
else if (nums[j]>=val) j--;
else swap(nums[i],nums[j]);
}
if (nums[i]>val) i--;
if (nums[i] != nums[idx]) swap(nums[i], nums[idx]);
return i;
}

double find_kth(vector<int> &nums, int k) {
int i = 0, j = n-1;
while (i<j) {
int m = pivot(nums,i,j);
int len = m-i+1;
if (k<len) {
j = m-1;
} else if (k>len) {
k-=len;
i = m+1;
} else {
return nums[m];
}
}
return nums[i];
}

double find_medin(vector<int> &nums) {
if (n&1) {
return find_kth(nums, 1+(n>>1));
} else {
return (find_kth(nums,n>>1) + find_kth(nums, 1+(n>>1)))/2;
}
}

//Dutch Flag Srot (reversed order)
void dfs(vector<int> &nums, double target) {
int i = 0, j = n-1, k = 0;
while (k<=j) {
if (nums[k]>target) {
swap(nums[i++], nums[k++]);
} else if (nums[k] < target) {
swap(nums[j--], nums[k]);
} else {
k++;
}
}
}

int get_next(int i) {
if (i>=r_start) return (i-r_start)<<1;
else return 1+(i<<1);
}
// giving up to think a legitimate O(1) space solution.
// cheat by using a mask to show whether it has
// been visited or not. This sub-problem is much harder compare
// to array rotation, I cannot use a count and increase
// the start by one whenever count < limit.
void re_order(vector<int> & nums) {
for (int mask = 1<<30, i, temp, start=0; start<n; ++start) {
temp = nums[i = start];
}
}
}
};``````

• That final reordering in O(1) space is easy. Just embed it into your `dfs` by treating `i`, `j` and `k` as virtual indexes and rewiring them to the appropriate real indexes:

``````//Dutch Flag Srot (reversed order)
void dfs(vector<int> &nums, double target) {
int i = 0, j = n-1, k = 0, N = n|1;
#define Nums(i) nums[(1+2*(i)) % N]
while (k<=j) {
if (Nums(k) > target) {
swap(Nums(i++), Nums(k++));
} else if (Nums(k) < target) {
swap(Nums(j--), Nums(k));
} else {
k++;
}
}
}
``````

To be clear: This replaces your `re_order` and `get_next`, which you then must not use anymore.

My question is "will there be a real O(n) time solution?". Because yours, like the others that claim this, is only O(n^2), not O(n).

• real `O(n)` can be achieved if we use "median of medians"wiki, to find the median.
It has worst case `O(n)` time performance with `O(1)` space

• Yes, I know. I'm just wondering whether anybody will bother to actually do that :-)
Using simple quickselect and falsely claiming O(n) seems much more popular :-(

• That is true.

• Thanks for you answer. First thing learned in 2016! Happy new year!
BTW: this solution is average O(n) time.

• if you get [2,2,2,2,1,1,1],after the three way partition, will you get [2,2,1,2,1,2,1]