Leetcode discuss: 1439. Find the Kth Smallest Sum of a Matrix With Sorted Rows

 Here is the link. 

Second practice - C# - copy idea - Time complexity - Each row maximum cost - Sorting

January 5, 2020
Introduction
It is so quick to learn a new idea and code is so easy to write. I really enjoyed the learning.

Copy idea - C# - changes
I made a few changes to make it work and fit into my style.

It is localize optimization algorithms as well. Do not worry about kth element smallest for given number of columns. Focus on each row, keep kth small numbers of prefix sums.

First row, just start from left to right, and keep kth smallest number. It is smart and easy to do.
Next row, brute force all comibination of two rows, first row has at most kth numbers, second row has size of columns numbers. So combination is easy, k * columns variations.

The time complexity is upper bounded by sorting those k * columns numbers, O(k * columns * log(k * columns)).

Time complexity
O(rows * k * columns * log(k * columns))
Each row upper bound of time complexity is related to sorting algorithm.

My first one hour
I spent one hour in mock interview, but I could not figure out a working solution.

Here are lesson learned:

1. Work on time complexity analysis - brute force, how to lower the the time compleixty
2. Brute force, find all sequence in which one number is selected for each row, the combinations are columns^rows. It will time out.
3. Next, work on exactly how to get next smallest sum for sequence - it is too hard to search - beyond a hard level
4. Next, relax the condition, each row, find kth smallest numbers. Easy task;
5. Start from second row, consider sequence of two numbers, keep kth smallest sequence as well. Time complexity, sorting, total upper bound of number - k * columns.
6. What did I miss in mock interview? Will add later.
7. Take a row by row solution, work on one row at a time. Next work on combination of two rows, sum of two number sequence, find kth smallest one.

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

namespace _1439_kth_element_II
{
    class Program
    {
        static void Main(string[] args)
        {
            var mat = new int[2][];

            mat[0] = new int[] { 1, 3, 11 };
            mat[1] = new int[] { 2, 4, 6 };

            var result = KthSmallest(mat, 5);
            Debug.Assert(result == 7); 
        }

        /// <summary>
        /// study code and copy idea 
        /// https://leetcode.com/problems/find-the-kth-smallest-sum-of-a-matrix-with-sorted-rows/discuss/609961/C-Without-Priority-Queue
        /// </summary>
        /// <param name="mat"></param>
        /// <param name="k"></param>
        /// <returns></returns>
        public static int KthSmallest(int[][] mat, int k)
        {
            var rows = mat.Length; 
            var columns = mat[0].Length; 

            var currentSum = new List<int>();

            for (int i = 0; i < columns && i < k; i++)
            {
                currentSum.Add(mat[0][i]);
            }            

            // start from second row 
            for (int row = 1; row < rows; row++)
            {
                var nextSum = new List<int>();

                for (int col = 0; col < columns; col++)
                {
                    var current = mat[row][col];

                    foreach (var sum in currentSum)
                    {
                        nextSum.Add(sum + current);
                    }

                    nextSum.Sort(); 

                    // remove those beyond k 
                    while (nextSum.Count > k) 
                    {
                        nextSum.RemoveAt(nextSum.Count - 1);
                    }
                }

                currentSum = nextSum;
            }

            currentSum.Sort();

            return currentSum[k - 1];
        }
    }
}