Leetcode 402: remove K digits - Brute force solution

April 18, 2019

Introduction

It is so painful since I could not pass all test cases after more than 40 minutes in second mock interview. It is a medium level algorithm. I will fix the bug and also analyze my solution written in mock interview.

Code study

I spent 40 minutes in mock interview but I only passed one test case. Afterwards, I spent almost one hour to play all test cases and then make it work.

It is a brute force solution. Somehow my nature to find a solution and also write a solution does not produce good fruit. I like to make it work and then compare to the solution using Stack, I learn the huge difference in terms of ease to write and efficient of time complexity.

I am not the material of stack thinking yet. I will be one day. I just need to practice daily, and make it like lunch or dinner activity.

	public class Solution {
	/// <summary>
	/// Leetcode 402 remove K digits
	/// 4/19/2019
	/// I learned two lessons.
	/// first I should evaluate time complexity; if I choose to use stack then it will much easy to write;
	/// Second the edge case is not handled time efficent way.
	/// </summary>
	/// <param name="num"></param>
	/// <param name="k"></param>
	/// <returns></returns>
	public string RemoveKdigits(string num, int k)
	{
	if (k == 0)
	return num;
	if (num == null || num.Length == 0)
	return num;
	var length = num.Length;
	var chose = new StringBuilder();
	// time complexity is not efficient O(removed * removed) + O(length)
	int start = 0;
	int removed = k;
	while (removed > 0)
	{
	// 10200 - k = 1, only choose the first two digits
	// find the minimum digit from start position
	// removed + 1 digits
	// reserve digits for
	var range = removed + 1;
	var minIndex = start;
	var minValue = 10;
	// edge case: "10", 2
	var end = start + range;
	if (end > length)
	{
	if (chose.ToString().Length == 0)
	return "0";
	else
	return chose.ToString();
	}
	for (int i = start; i < end; i++)
	{
	var current = num[i] - '0';
	var isSmaller = current < minValue;
	minValue = isSmaller ? current : minValue;
	minIndex = isSmaller ? i : minIndex;
	}
	// edge case: "0200" -> "20"
	var leadingZero = chose.ToString().CompareTo("0") == 0;
	if (leadingZero)
	{
	chose.Clear();
	chose.Append(num[minIndex]);
	}
	else
	chose.Append(num[minIndex]);
	// count how many digits removed
	removed -= minIndex - start;
	start = minIndex + 1;
	}
	for (int i = start; i < length; i++)
	{
	// edge case: "0200" -> "20"
	var leadingZero = chose.ToString().CompareTo("0") == 0;
	if (leadingZero)
	{
	chose.Clear();
	chose.Append(num[i]);
	}
	else
	chose.Append(num[i]);
	}
	return chose.ToString();
	}
	}

view raw Leetcode402RemoveKDigits.cs hosted with ❤ by GitHub

Naive solution 

I came out the naive solution first, and without searching for optimal linear solution, I started to write code.

It is such great learning experience to practice the algorithm in mock interview. I have 60 minutes, this was the second algorithm, and I came out the idea to find minimum number using O(N * N) algorithm. Without searching for optimal solution, I decided to write the code to implement the idea.