Two Sum - Leet Code
Tags: algorithms
Published: 2020-10-31 17:28:00

I worked on the TwoSum leet code problem this week.
https://leetcode.com/problems/two-sum/

After reading and viewing multiple problems solving approaches. I have listed the steps I am using to solve the problems. Want to use the post as a future reference.

Do not immediately start coding once you see the problem. 
 
**Step A (Analyze)**: Analyze and note the important points
   * two number add up to the target
   * exactly one solution
   * do not use same element twice
   * return indices answer in any order. 
   * [Note: we need to retrun indices sometimes in rush to get to solution we might miss this and return numbers]

   * In real interview ask and clarify any questions
	 Datatype of num. i.e Is num an integer ?		  
         Num range ?
	 Case where there is no match ?
		          
 **Step T (Test Cases)**:
  * If no test data write test cases and confirm 			Think of possitive, edge and negative test cases
  *  T1: [2,7,11,15] target = 9  => [0,1]
			Since we can have negative numbers add test case on negative numbers
  * T2: [2,7,-11,15] target = 4  => [2,3]
			Reason to pick target 4: If you are using element twice you get wrong answer [0,0]
			and also it covers the negative numbers case
  * T3: [2,7,11,-15] target -4 => [2,3]
      
**Step B (Brute Force)**:
 * Think of BruteForce and calculate its time complexity
 * Take two for loops to get each pair in the array of size N and check if it adds up to target.
 * Time complexity is O(N^2) 
        
**Step O (Optimize)**: 
 * BUD technique from Cracking the Coding Interview book.
 * Look for BUD: (Bottlenecks, Unnecessary Work, Duplicated work)
 * Goal is to get to linear time O(N) or close to linear time.			
  * Bottleneck is iterating the array twice.        
			
**Step S (Solution)**:
 * Mantain a map to store the expected Num (Target - elementValue ) as key and element index as value.
 * At each index first check if the elemenet is in expectedNum map.
	* If yes return the current index and the expectNum index in an array
	* If no return store the expected Num (Target - elementValue ) and current index in the map.	

* Time Complexity is O(N)
               
**Step C  (Code)**:
	
```
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        
       /* Algorithm
        1. expectedMap = {}
        2. for i in range(len(nums)):
              if nums[i] in expectedMap:
                 return [i,expectedMap[nums[i]]
              else:
                 num2 = target - nums[i]
                 expectedMap[num2] = i         
        */

        //Map to store the expected Num with which we can make target
        map<int, int> expectedMap;
        vector<int> result;

        for (auto i = 0; i < nums.size(); i++) {

            //check if the num is in expected map 
            auto it = expectedMap.find(nums[i]);          

            if (it != expectedMap.end()) {
                result.push_back(i);
                result.push_back(it->second);
                return result;
            }
            else {
                //Find the num to make the target and store it in map
                auto num2 = target - nums[i];               
                expectedMap.insert(make_pair(num2, i));
            }
        }

        return result;
        
    }
};
```
**Step V (Verify with test data)**:
 * Iterate your code with test data before submitting it.
			
**SUBMIT** the code.
		
**Lessons from mistakes**:
 * Check if we are storing the correct num in the map
 * Iterate the code with the test data and check what variable hold at each steps
		
**Tips**:
  * When you are stuck start with a smaller problem size. 
  * Check if sorting the array can improve the performance.
  * Does using additional data structure like map improve the performance.
  * Two pointers

Please share your inputs which can help me to improve.