Leetcode discuss: 324. Wiggle Sort II

April 25, 2022

Here is the link. 

C# | Find median value first, wiggle solution - even index, any number smaller than median

April 25, 2022
Introduction
It is interesting journay to come cross this algorithm. I am preparing meta onsite in May 2022, and then I decided to go over top voted algorithms by StefanPhchmann.

Analysis by StefanPhchmann | My analysis
Explanation
Assuming that there is O(N) time complexity to find nth_element.

Three-way partitioning
Let me introduce 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.

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.

Leetcode C# discuss post | Study code | Figure out time complexity of partition
I copied one of C# discuss post, and then tried to understand the partition algorithm time complexity, can it be O(N) which is better than O(NlogN) - sorting algorithm? Based on quick select algorithm and it's worst case is with time complexity O(N^2), I guessed that the partition algorithm cannot be O(N).

The following C# code passes online judge.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _324_Wiggle_sort_II
{
    class Program
    {
        static void Main(string[] args)
        {
            //[1,5,1,1,6,4]
            var test = new Program();
            var numbers = new int[] { 1, 5, 1, 1, 6, 4 };
            test.WiggleSort(numbers);
        }

        /// <summary>
        /// code review: 
        /// </summary>
        /// <param name="nums"></param>
        public void WiggleSort(int[] nums)
        {
            int medianIndex = nums.Length / 2;
            int median = FindKthLargest(nums, medianIndex);  // using O(N) time complexity

            int start = 0;
            int end = nums.Length - 1;
            int i = 0;
            int index = 0;

            // go over the example
            // understand how to put median vlaue in the middle of the array
            // even index - any number < median
            // odd index  - any number > median
            while (i <= end)
            {
                index = newIndex(nums, i);
                if (nums[index] > median)
                {
                    swap(nums, newIndex(nums, start), index);
                    start++;
                    i++;
                }
                else if (nums[index] < median)
                {
                    swap(nums, newIndex(nums, end), index);
                    end--;
                }
                else
                {
                    i++;
                }
            }
        }

        private int newIndex(int[] nums, int index)
        {
            return (1 + 2 * index) % (nums.Length | 1);
        }

        /// <summary>
        /// Code review - April 25, 2022
        /// Using time complexity O(N) to find kth largest element 
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="k"></param>
        /// <returns></returns>
        public int FindKthLargest(int[] nums, int k)
        {
            int start = 0;
            int pivot = start;

            int end = nums.Length - 1;
            int index = k - 1;

            while (start < end)
            {
                pivot = partition(nums, start, end); 

                if (pivot < index)  // ? 
                {
                    start = pivot + 1;
                }
                else if (pivot > index)
                {
                    end = pivot - 1;
                }
                else
                {
                    return nums[pivot];
                }
            }

            return nums[start];
        }

        /// <summary>
        /// code review:
        /// April 25, 2022
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="start"></param>
        /// <param name="end"></param>
        /// <returns></returns>
        private int partition(int[] nums, int start, int end)
        {
            int pivot = start;
            while (start <= end)
            {
                // Find two numbers to swap, nums[start] > nums[pivot], and nums[end] < nums[pivot]
                while (start <= end && nums[pivot] <= nums[start])
                {
                    start++;
                }

                while (start <= end && nums[end] <= nums[pivot])
                {
                    end--;
                }

                if (end < start)
                {
                    break;
                }

                swap(nums, start, end);
            }

            swap(nums, end, pivot);
            return end;
        }

        private void swap(int[] nums, int i, int j)
        {
            int tmp = nums[i];

            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }
}