Two Sum - Leet Code

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.