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

Dec. 26, 2021

Here is the link. 

C# | One row a time to keep first kth smallest sum | warmup on Dec. 26, 2021

Dec. 26, 2021
Introduction
It is a hard level algorithm. I came cross the algorithm to prepare for my Microsoft Vancouver online assessment. It is important for me to learn to be humble and learn from my own mistake in 2021 practice.

One row a time | Keep first kth smallest sum | Sort once for one row | computation of sum: k * columns

It is easy to figure out all possible sum for two rows, first row only has k columns, second row has columns of given mat. Next is to sort the list and keep only first kth ones.

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 code_assessment
{
    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);
        }

        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]);
            }

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

                for (int col = 0; col < columns; col++)
                {
                    var value = mat[row][col];
                    foreach (var sum in currentSum)
                    {
                        nextSum.Add(sum + value); 
                    }
                }

                nextSum.Sort();

                while (nextSum.Count > k)
                {
                    nextSum.RemoveAt(nextSum.Count - 1);
                }

                currentSum = nextSum; 
            }

            return currentSum[k - 1];
        }        
    }
}