O(n)+O(1) after median --- Virtual Indexing


  • 218

    This post is mainly about what I call "virtual indexing" technique (I'm sure I'm not the first who came up with this, but I couldn't find anything about it, so I made up a name as well. If you know better, let me know).


    Solution

    void wiggleSort(vector<int>& nums) {
        int n = nums.size();
        
        // Find a median.
        auto midptr = nums.begin() + n / 2;
        nth_element(nums.begin(), midptr, nums.end());
        int mid = *midptr;
        
        // Index-rewiring.
        #define A(i) nums[(1+2*(i)) % (n|1)]
    
        // 3-way-partition-to-wiggly in O(n) time with O(1) space.
        int i = 0, j = 0, k = n - 1;
        while (j <= k) {
            if (A(j) > mid)
                swap(A(i++), A(j++));
            else if (A(j) < mid)
                swap(A(j), A(k--));
            else
                j++;
        }
    }
    

    Explanation

    First I find a median using nth_element. That only guarantees O(n) average time complexity and I don't know about space complexity. I might write this myself using O(n) time and O(1) space, but that's not what I want to show here.

    This post is about what comes after that. We can use three-way partitioning to arrange the numbers so that those larger than the median come first, then those equal to the median come next, and then those smaller than the median come last.

    Ordinarily, you'd then use one more phase to bring the numbers to their final positions to reach the overall wiggle-property. But I don't know a nice O(1) space way for this. Instead, I embed this right into the partitioning algorithm. That algorithm simply works with indexes 0 to n-1 as usual, but sneaky as I am, I rewire those indexes where I want the numbers to actually end up. The partitioning-algorithm doesn't even know that I'm doing that, it just works like normal (it just uses A(x) instead of nums[x]).

    Let's say nums is [10,11,...,19]. Then after nth_element and ordinary partitioning, we might have this (15 is my median):

    index:     0  1  2  3   4   5  6  7  8  9
    number:   18 17 19 16  15  11 14 10 13 12
    

    I rewire it so that the first spot has index 5, the second spot has index 0, etc, so that I might get this instead:

    index:     5  0  6  1  7  2  8  3  9  4
    number:   11 18 14 17 10 19 13 16 12 15
    

    And 11 18 14 17 10 19 13 16 12 15 is perfectly wiggly. And the whole partitioning-to-wiggly-arrangement (everything after finding the median) only takes O(n) time and O(1) space.


    If the above description is unclear, maybe this explicit listing helps:

    Accessing A(0) actually accesses nums[1].
    Accessing A(1) actually accesses nums[3].
    Accessing A(2) actually accesses nums[5].
    Accessing A(3) actually accesses nums[7].
    Accessing A(4) actually accesses nums[9].
    Accessing A(5) actually accesses nums[0].
    Accessing A(6) actually accesses nums[2].
    Accessing A(7) actually accesses nums[4].
    Accessing A(8) actually accesses nums[6].
    Accessing A(9) actually accesses nums[8].


    Props to apolloydy's solution, I knew the partitioning algorithm already but I didn't know the name. And apolloydy's idea to partition to reverse order happened to make the index rewiring simpler.


  • 1
    W

    This does solve my O(1) space question in my previous post ingeniously, given the assumption of O(1) space for nth_element. Thanks for sharing!


  • -1
    N

    BRILLIANT IDEA!


  • -1
    N

    but wouldn't quickselect be enough here?because after applying quickselect whole array on the left of the median is already smaller, and on the right is already bigger.
    EDIT: forget it, i assumed we have additional space for the output of the array


  • 5
    C
    // Index-rewiring.
    #define A(i) nums[(1+2*(i)) % (n|1)]
    

    This is really hard for me to understand. Could you explain more clearly?


  • 0

    It really just means that the indexes aren't where they usually are, as shown in the example. Hard to tell why it's hard for you, whether it's being a macro, whether it's the formula, or whether it's the idea I'm showing. Check out zhiqing_xiao's explanation and implementation as well, that shows the same idea a bit differently.


  • 2

    Well, maybe this helps. Consider my example again, where nums has ten numbers. Then:

    Accessing A(0) actually accesses nums[1].
    Accessing A(1) actually accesses nums[3].
    Accessing A(2) actually accesses nums[5].
    Accessing A(3) actually accesses nums[7].
    Accessing A(4) actually accesses nums[9].
    Accessing A(5) actually accesses nums[0].
    Accessing A(6) actually accesses nums[2].
    Accessing A(7) actually accesses nums[4].
    Accessing A(8) actually accesses nums[6].
    Accessing A(9) actually accesses nums[8].


  • 0
    S

    Can this solution solve the [4,5,5,6] case? or [4,5,5,5,5,6,6,6] case?


  • 0

    @sunzc Sure. It builds [5,6,4,5] and [5,6,5,6,5,6,4,5].


  • 0
    C

    What is shown here is very clear. Thanks. What I wanted to express is that the formula "nums[(1+2*(i)) % (n|1)" is hard to understand. I might write more complex code to implement the same functionality.


  • 1
    M

    What is the solution for [1,1,1] (so all the same)?


  • 0

    @mehran Reordering that has no effect and there is no solution, so it's invalid input. Why are you asking that?


  • 0
    G

    Can you please explain why partitioning the array using the rewritten indices results in the wiggle order of the array? Is there any proof of correctness?


  • 1

    @guohua
    I have a proof here. The code there uses full sorting, but the explanation/proof then talks about "M/S/L" numbers (median, smaller, larger) because only that partitioning is relevant.


  • 0
    G

    Thanks a lot.


  • 1
    M

    I dont think the statement that the number array can look like this (when median is 15) is true:

    number: 18 17 19 16 15 11 14 10 13 12

    std::nth_element() guarantees that elements after the nth position are NOT LESS THAN the element at the nth position.


  • 0

    @michael164
    I said after nth_element *and partitioning* (the one I described two paragraphs earlier).


  • 0
    M

    Ah I see! Sorry about the misunderstanding and thanks for the reply!


  • 0
    C

    Good Job, Stephen


  • 1
    K

    Brilliant work!
    The idea is similar to the two-pointer one-pass solution to Sort Colors, where 0, 1, 2 are replaced by numbers greater than median, median, numbers smaller than median.
    And the mapping function redirects the indexing to realize wiggle positioning.


Log in to reply
 

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