Java O(N) solution

• ``````public class Solution {
public void wiggleSort(int[] nums) {
for(int i=0;i<nums.length;i++)
if(i%2==1){
if(nums[i-1]>nums[i]) swap(nums, i);
}else if(i!=0 && nums[i-1]<nums[i]) swap(nums, i);
}
public void swap(int[] nums, int i){
int tmp=nums[i];
nums[i]=nums[i-1];
nums[i-1]=tmp;
}
}``````

• Good idea, just can be shorter:

``````public void wiggleSort(int[] nums) {
for (int i=1; i<nums.length; i++) {
int a = nums[i-1];
if ((i%2 == 1) == (a > nums[i])) {
nums[i-1] = nums[i];
nums[i] = a;
}
}
}
``````

• very concise, thank you

• Wow, this looks cool.

• The usage of "==" is excellent !

• @Youchen Yeah, I love the "if and only if" operator :-)

• Can this handle 1, 1, 1, 3, 3, 3, 2, 2, 2?

• Why wouldn't it?

• Hi, I have posted a follow-up question. I don't know if it can be solved in O(n) time. What's your opinion? : )

• @johnsonys I think I have an O(n) solution, but it's really complicated :-)

• This post is deleted!

• hey Stefan I tried googling for the usage of "==" with respect to how you have used it for this question, didn't come up with anything, help with any resources to could look at?

• @rajdev Not sure what you mean. It's just a normal comparison. It's maybe unusual to compare booleans, but nothing special that needs extra explanation.

• Maybe

``````for (int i=1; i<nums.length; i++) {
int previous = nums[i-1];
if ((nums[i] > previous) != (i%2 == 1)) {
nums[i-1] = nums[i];
nums[i] = previous;
}
}
``````

would be clearer? We want a number to be larger than the previous (`nums[i] > previous`) if and only if it's at an odd index (`i%2 == 1`). With `==` it's effectively "if and only if", but I want to swap when that's violated, so I negate to `!=` here. Maybe

``````    if (! ((nums[i] > prev) == (i%2 == 1))) {
``````

would be clearer to some, but I don't like the extra parentheses and operator.

• Thank you, makes more sense now, I'm just accustomed to seeing "&&, || !" with booleans I guess

• Hi @StefanPochmann, could you please let me know how long it takes for you to come up with a solution like this? I've been wondering these days :P

• I think if you first encounter this question in an interview, it is very hard to come up with this solution. I rather prefer sort the array first, which is more straight-forward

• Can someone explain why the same logic of mine fails:

``````public class Solution {

public void wiggleSort(int[] nums) {
for(int i=0;i<nums.length;i++)
if(i%2==1 &&(nums[i-1]>nums[i])){ // I have combined here thats why it fails
swap(nums, i);
}else if(i!=0 && nums[i-1]<nums[i]) swap(nums, i);

}
void swap ( int [] nums, int i) {
int temp=nums[i];
nums[i]=nums[i-1];
nums[i-1]=temp;
}

}``````

• @StefanPochmann Could you explain the difference of using == and && ? Still don't understand "if and only if". Thank you so much

• This post is deleted!

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