Leetcode 16 - 3 sum closest

May 17, 2016

Julia likes to write some code after she reads the blog:

http://www.cnblogs.com/TenosDoIt/p/3649607.html

Write C# practice on Leetcode 16 - 3 sum closest solution:

https://gist.github.com/jianminchen/d23598296e7ba665b6d45ae4acfeb600

First practice on Leetcode 16 - 3 sum closest solution on 

https://github.com/jianminchen/Leetcode_C-/blob/master/3sumCloset.cs

Previous blog:

http://juliachencoding.blogspot.ca/2016/01/leetcode-1-15-15-two-sum-3-sum-3-sum.html

Question and Answer:

1. What do you learn through the practice this time?

Julia learns the importance to do static analysis on the code. Do not rush, make sure every variable/ name is making sense, every line of code is best she can present, every executable path should be examined. Every scope of variable is close to minimum as possible. Walk through the examination steps loudly. 

2. What common steps Julia likes to build a ritual after her first writing - C# code - after she failed to present a two sum algorithm on May 4, 2016? 

Answer:

1. Julia likes to examine every line of code, see if she can improve the presentation; 

2. Check every variable, scope, meaningful name

3. Check every executable path, make sure that no bug

4. What test case will be executed on the line. 

5. Avoid early return error, other common errors. 

6. Read the code, speak out what she is doing on reviewing of each line, each variable. Talk about the change she likes to make, thing found needs to be taken care of.   

3. What is most important to solve the problem? 

Using two sum problem solving technique, extend the method to solve the 3 sum closest one. 

The idea is most important and also know how to do time complexity analysis - O(n^2) solution - best one. 

Since O(n^2) is the best time complexity we can solve the problem, sorting takes less than O(n^2); certainly, array can be sorted first. 

So, here is the analysis Julia does for the problem - 3 sum closest. 

Idea:

* 1. Sorting takes O(nlogn) for an array

* 2. And then, choose (i, j, k), assuming i<j<k, iterate on variable i,

*   we need to find two sum problem for each i, new target = target - nums[i]

*   since the array is sorted, two pointer solution can be used. One is the beginning

*   of array, another one is the end of the array.

*

*   So, this step 2 process takes O(n^2) time

*

* Overall, the algorithm will take O(n^2) time complexity

*

*

*   read the C# Array API - 10 minutes

*   https://msdn.microsoft.com/en-us/library/6tf1f0bc(v=vs.110).aspx