Leetcode discuss: 2263. Make Array Non-decreasing or Non-increasing

Here is the link. 

C# | Quick learner | Maximum heap | Sorted<Tuple<int, int>> | Tip: Add twice

June 3, 2022
I like to be a quick learner. I could not figure out the trick by reading C++, Java code shared by votrubac. So I debugged and then figured out how to make the test case work.

Test case | {3, 2, 4, 5, 0} | Trick: Add twice into the max heap
I like to go over the test case {3, 2, 4, 5, 0} and explain why it takes 4 operations to make a non-decreasing order in reverse order.

I chose to use C# SortedSet<Tuple<int, int>> to simulate a maximum heap.
I tried to work on the above case step by step by myself. I am working on

cost(nums, -1)

First, last element in the array, index = 4, add it to Max heap, heap - new Tuple<int, int>, (0, 0)
Next, index = 3, value 5, add it to heap, (5, 1)
Next, index = 2, value 4, heap.Max.Item1 = 5 > 4, so result variable increments (5 - 4) = 1, remove (5, 1) from heap,
add (4, 2) to heap <- inside if statement

if (heap.Count > 0 && heap.Max.Item1 > current)
{
	result += heap.Max.Item1 - current;
    heap.Remove(heap.Max);
    heap.Add(new Tuple<int, int>(current, count++)); 
}

Next, it is to add (4, 3) to the heap by executing the statement outside if statement

// explain: why {3, 2, 4, 5, 0} reverse order, 4 will be added twice? 
heap.Add(new Tuple<int, int>(current, count++));

Mext. it is to add (2, 4) to the heap, and result += (4 - 2), result = 3, remove (4, 3) from heap
Last, it is to add (3, 5) to the heap, and result += (4 - 3), result = 4, remove (4, 2) from heap.

votrubac | Analysis
I just quickly copied the idea and analysis from votrubac in the following:

The greedy logic is quite tricky. We process numbers left-to-right, and put them into a max heap.

When the current number n is smaller than the largest so far m, we know that we need to do m - n adjustments.

Now, the tricky part. We can increase n and/or decrease m so that they become the same. But for the purpose of the greedy algorithm, we assume we decrease m all the way to be the same as n, and put the new value to the heap.

The following C# code passes online judge.

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

namespace _2263_make_array_non_decreasing
{
    class Program
    {
        static void Main(string[] args)
        {
            var result = ConvertArray(new int[]{3, 2, 4, 5, 0});
            Debug.Assert(result == 4); 
        }

        /// <summary>
        /// study code
        /// https://leetcode.com/problems/make-array-non-decreasing-or-non-increasing/discuss/2011905/Greedy
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public static int ConvertArray(int[] nums)
        {
            return Math.Min(cost(nums), cost(nums, -1)); 
        }

        /// <summary>
        /// checklist:
        /// 1. Maximum heap
        /// 2. Tricky part - greedy - decrease m all the way to be the same as n, and put the new value to the heap
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="d"></param>
        /// <returns></returns>
        private static int cost(int[] nums, int d = 1)
        {
            int result = 0;
            var heap = new SortedSet<Tuple<int, int>>();

            var length = nums.Length;
            var count = 0; 
            for (int i = (d == 1 ? 0 : length - 1); i < length && i >= 0; i += d)
            {
                var current = nums[i];

                if (heap.Count > 0 && heap.Max.Item1 > current)
                {
                    result += heap.Max.Item1 - current;
                    heap.Remove(heap.Max);
                    heap.Add(new Tuple<int, int>(current, count++)); 
                }

				// explain: why {3, 2, 4, 5, 0} reverse order, 4 will be added twice? 
                heap.Add(new Tuple<int, int>(current, count++));
            }

            return result; 
        }
    }
}