Cracking the Coding Interview -Wiggle Sort (Google)-I

This is a question asked in google as listed on leetcode premium subscription. This is marked as a medium difficulty question.

Problem Statement

Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]..

For example, given nums = [3, 5, 2, 1, 6, 4], one possible answer is [1, 6, 2, 5, 3, 4].

Solution

Let us try to break the question and focus on given points one by one.

num[0]≤num[1]≥num[2].This gives us that hint that we might need to make numbers present at even places larger than the surrounding one and we will get our solution. So let us keep the focus on finding and replacing the even index with a bigger number available.

It’s provided that we need to sort array in place .No extra space is allowed.

For the basic approach, we can sort the array and can swap the numbers at even place with the number next to them.

array after sorting : [1, 2, 3, 4, 5, 6]
now we need to swap the numbers at even place with the next number to them.
[1,2,3,4,5,6] --> [1,3,2,4,5,6] --> [1,3,2,4,5,6] --> [1,3,2,5,4,6]
Resulting array 
[1,3,2,5,4,6]

Code

Let us start with basic functions to swap two values in an array.

private void swap(int[] num, int i, int j) {
    int temp = num[i];
    num[i] = num[j];
    num[j] = temp;
}

Now we will sort array and loop over every element and swap elements on reaching even places

public void wiggleSort(int[] num) {
    Arrays.sort(num);
    for (int i = 1; i < num.length - 1; i += 2) { 
        swap(num, i, i + 1);
    }
}

just started loop with 2nd index and checking only values at even place.

Complexity :

Time: Depends upon sorting part.As we have used Arrays.sort which is based on the TimSort algorithm, giving us a time complexity of O(n log(n)).

Space: As we have altered the given array in this approach. Space complexity will depend upon the sorting approach too.

Fix while traversing approach

We can solve this in a better-optimized way by comparing elements on the go. As we traverse through the array we will check the current element with its next element and in case the order is wrong, fix it.

We will keep a variable to store the condition which we need to maintain at the given index. For this case at an odd place, we need to maintain that element should be smaller than the next and at an even place, we need to maintain that element is larger than its next element. we will use a toggle flag which we will switch with every element.

public void wiggleSort(int[] num) {
    boolean isSmaller = true;
    for (int i = 0; i < num.length - 1; i++) {
        if (isSmaller) {
            if (num[i] > num[i + 1]) {
                swap(num, i, i + 1);
            }
        } else {
            if (num[i] < num[i + 1]) {
                swap(num, i, i + 1);
            }
        }
        isSmaller = !isSmaller;
    }
}

Complexity :

Time: As it will require us to traverse the array once and every element will be at the proper place. We will end up with time complexity of O(n).

Space: No extra space is required in this solution. Space complexity will be O(1)

Compacting Solution

This might not be required in the interview as keeping things simple and more understandable is the way to code for interviews.

As we know the value of isSmaller (toggle flag) depends on whether the index is even or odd, we can compact our condition.

if (((i % 2 == 0) && num[i] > num[i + 1])
                || ((i % 2 == 1) && num[i] < num[i + 1])) {
            swap(num, i, i + 1);
        }

we can further concise the above two statements into a single one. As we can observe that the above two conditions are dependent on each other.

We need to swap

1. When we are at an even index and the number is smaller than the next.
2. When we are at odd index and the number is greater than the next.

(num[i] < num[i + 1]) == true and (index%2 == 1) ==true 
                           |
                           |
(num[i] < num[i + 1]) == (index%2 == 1)

This is my first attempt at writing a post. Your feedback is highly appreciated.