O(n)-time O(1)-space solution with detail explanations


  • 43

    Methodology:

    Idea 1.

    As @whnzinc pointed out in this thread, all elements in nums can be classified into three categories:

    (1) Larger than the median;

    (2) Equal to the median;

    (3) Smaller than the median.

    Note that it's possible to find the median within O(n)-time and O(1)-space.

    Note: We can use nth_element to find the median, but it's not O(n)-time and O(1)-space. For the sake of simplicity, I might use nth_element as well.

    Idea 2.

    As @StefanPochmann pointed out in this thread, we can arrange the elements in the three categories in a deterministic way.

    (1) Elements that are larger than the median: we can put them in the first few odd slots;

    (2) Elements that are smaller than the median: we can put them in the last few even slots;

    (3) Elements that equal the median: we can put them in the remaining slots.

    Update: According to @StefanPochmann's thread, we can use a one-pass three-way partition to rearrange all elements. His idea is to re-map the indices into its destined indices, odd indices first and even indices follow.

    Example:

    Original Indices:    0  1  2  3  4  5  6  7  8  9 10 11
    Mapped Indices:      1  3  5  7  9 11  0  2  4  6  8 10
    

    (its reverse mapping is)

    Mapped Indices:      0  1  2  3  4  5  6  7  8  9 10 11
    Original Indices:    6  0  7  1  8  2  9  3 10  4 11  5   (wiggled)
    

    In order to achieve this, we can use a function alike

    int map_index(int idx, int n) {
        return (2 * idx + 1) % (n | 1);
    }
    

    where (n | 1) calculates the nearest odd that is not less than n.


    Complexities: (On the condition that finding median is O(n)-time and O(1)-space)

    • Time: O(n)

    • Space: O(1)


    C++ (Updated, 44ms):

    class Solution {
    public:
    	void wiggleSort(vector<int>& nums) {
    		if (nums.empty()) {
    			return;
    		}    
    		int n = nums.size();
    		
    		// Step 1: Find the median    		
    		vector<int>::iterator nth = next(nums.begin(), n / 2);
    		nth_element(nums.begin(), nth, nums.end());
    		int median = *nth;
    
    		// Step 2: Tripartie partition within O(n)-time & O(1)-space.    		
    		auto m = [n](int idx) { return (2 * idx + 1) % (n | 1); };    		
    		int first = 0, mid = 0, last = n - 1;
    		while (mid <= last) {
    			if (nums[m(mid)] > median) {
    				swap(nums[m(first)], nums[m(mid)]);
    				++first;
    				++mid;
    			}
    			else if (nums[m(mid)] < median) {
    				swap(nums[m(mid)], nums[m(last)]);
    				--last;
    			}				
    			else {
    				++mid;
    			}
    		}
    	}    
    };

  • 0
    J

    Is there a equivalent of the vector<int>::iterator nth = next(nums.begin(), semisize); in java? Cuz I had to write a quick select and it's a pain.


  • 0

    @johnwyz The next function in C++ is merely a +


  • 0
    J

    Sorry I was referring to nth_element(nums.begin(), nth, nums.end()); Is there a equivalent in java?

    Answering my own question: I guess not - http://stackoverflow.com/questions/7019872/whats-the-equivalent-nth-element-function-in-java


  • 0

    @johnwyz88 Java does not have an equivalence of nth_element.


  • 7

    This still isn't "true O(n)", because nth_element only guarantees O(n) average complexity.

    Also, I'm not aware of any space complexity guarantees of nth_element. Where did you get that it only takes O(1) space?

    I checked it both on cplusplus.com and on cppreference.com. If they're wrong/incomplete, please show us something better.


  • 0

    @StefanPochmann You are right. nth_element is not always O(n), and it seems that its average space complexity is O(log n) and worse case space complexity is O(n). I will try to correct those erroneous statements. Thank you for pointing these out! :)


  • 0

    Nice to see another explanation and an implementation that's "more portable" (than my C++ macro :-)

    Another cool thing would be if someone could write custom iterators (I'm not familiar enough with them) so the solution function simply becomes:

    void wiggleSort(vector<int>& nums) {
        sort(wiggleBegin(nums), wiggleEnd(nums));
    }
    

  • 0
    C

    Hey, I'm a little confused. If we use quickselect, then we have an average time complexity of O(n), and guarantees for space complexity of O(1). While if we choose median of medians, then we would have guarantees of time complexity of O(n), while best case space complexity of O(logn). Am I right?


  • 0

    @cheng44 Yes. Looks like you're not confused after all :-)

    (Well, there's apparently a way to "emulate" median-of-medians with O(n) time and O(1) extra space, but I think that counts as a separate algorithm. See this answer and the comments under it if you're interested.


  • 0
    M

    @johnwyz88 I think we can use use selection algorithm to find median in expected O(n) time, if we want to implement in Java.


  • 1
    J

    Just wonder how you arrived at the following mapping. Need some thought process. Thanks!

    int map_index(int idx, int n) {
        return (2 * idx + 1) % (n | 1);
    }
    

  • 0
    S

    I used your idea and this is java complete version, it gives me 189ms. I don't know why is it so slow

    public class Solution {
        public void wiggleSort(int[] nums) {
            int median = median(nums, (nums.length - 1) / 2);
            int l = 0; int m = 0; int r = nums.length - 1;
            while(m <= r){
                if(nums[get(nums, m)] > median)
                    swap(nums, get(nums, m++), get(nums, l++));
                else if(nums[get(nums, m)] < median)
                    swap(nums, get(nums, m), get(nums, r--));
                else m++;
            }
        }
        
        private void swap(int[] nums, int i, int j){
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        
        private int median(int[] nums, int k){
            int left = 0, right = nums.length - 1;
            while(left <= right){
                int pi = partition(nums, left, right);
                if(pi == k) return nums[pi];
                else if(pi > k) right = pi - 1;
                else left = pi + 1;
            }
            return 0;
        }
        
        private int partition(int[]nums, int left, int right){
            int pivot = nums[right];
            int lessIndex = left - 1;
            for(int i = left; i < right; i++){
                if(nums[i] <= pivot){
                    lessIndex++;
                    swap(nums, i, lessIndex);
                }
            }
            swap(nums, lessIndex + 1, right);
            return lessIndex + 1;
        }
        
        private int get(int[] nums, int i){
            if(i <= (nums.length / 2 - 1)) return i * 2 + 1;
            return (i - nums.length / 2) * 2;
        }
    }
    

  • 1
    S

    It is interesting when I use the simplest method while the time complexity is O(nlogn) and space complexity is O(n), it gives me 6ms as a result.

    public void wiggleSort(int[] nums) {
            int[] copy = new int[nums.length];
            Arrays.sort(nums);
            for(int i = 0; i < nums.length; i++) copy[i] = nums[i];
            int index = 1;
            for(int i = nums.length - 1; i > (nums.length - 1) / 2; i--){
                nums[index] = copy[i];
                index += 2;
            }
            index = 0;
            for(int i = (nums.length - 1) / 2; i >= 0; i--){
                nums[index] = copy[i];
                index += 2;
            }
        }
    

  • 0

    @ShawYoungTang
    I was using the same idea as you used in your solution. Here is the more concise version, not satisfied the O(n) time and O(1) space requirement though...

    public void wiggleSort(int[] nums) {
            if (nums == null || nums.length < 2) return;
            Arrays.sort(nums);
            int len = nums.length, small = (len - 1) / 2, big = len - 1; 
            int[] copy = Arrays.copyOf(nums, len);
            for (int i = 0; i < len; i++) {
                nums[i] = i % 2 == 0 ? copy[small--] : copy[big--];
            }
        }
    

  • 0
    C

    @ShawYoungTang it seems that in your quick select step, there is no need to swap. You can assign the value directly and put the pivot value back to the last position in the end


Log in to reply
 

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