Here is the link.
First practice - C# - TLE 35/71 - DFS
Jan. 5, 2020
Introduction
It is the last algorithm in one of mock onsite on Leetcode premium. I spent over one hour but I could not figure out working solution - not brute force. It is hard to figure out next smaller. After the mock session, I wrote a DFS solution and then ran into TLE error.
Test case 35/ 71
Timeout - I will quickly figure out how to fix this issue. I believe that I should apply some pruning so it will be able to avoid TLE.
Time compleixty
DFS algorithm will exhaust all options, upper bound will be related to columns^ rows, which is the number of sequence, in which one for each row.
The working solution will take less than 20 minutes to write, and time complexity can be low as O(rows * k * columns * log(k * columns)).
Here is my working solution.
My first one hour
I spent one hour in mock interview, but I could not figure out a working solution.
Here are lesson learned:
- Work on time complexity analysis - brute force, how to lower the the time compleixty
- Brute force, find all sequence in which one number is selected for each row, the combinations are columns^rows. It will time out.
- Next, work on exactly get next smallest sum for sequence - it is too hard to search - beyond a hard level
- Next, relax the condition, each row, find kth smallest numbers. Easy task;
- 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.
- What did I miss in mock interview? Will add later.
- 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
{
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)
{
if (mat == null || mat.Length == 0 || mat[0].Length == 0)
{
return -1;
}
var rows = mat.Length;
var columns = mat[0].Length;
var sorted = new SortedSet<Tuple<int, int>>();
var list = new List<int>();
var index = 0;
runDFS(mat, k, sorted, 0, list, ref index);
return sorted.Last().Item1;
}
private static void runDFS(int[][] mat, int k, SortedSet<Tuple<int, int>> sorted, int row, List<int> list, ref int index)
{
if (row >= mat.Length)
{
var total = list.Sum();
if (sorted.Count < k)
{
sorted.Add(new Tuple<int, int>(total, index++));
}
else if (sorted.Count == k && sorted.Last().Item1 > total)
{
sorted.Remove(sorted.Last());
sorted.Add(new Tuple<int,int>(total, index++));
}
return;
}
var rows = mat.Length;
var columns = mat[0].Length;
for (int col = 0; col < columns; col++)
{
var current = mat[row][col];
// check the sum so far - compare to sorted
if (sorted.Count == k && sorted.Last().Item1 < list.Sum() + current)
{
break;
}
list.Add(mat[row][col]);
runDFS(mat, k, sorted, row + 1, list, ref index);
list.RemoveAt(list.Count - 1);
}
}
}
}