2 sum problem

2 sum is a problem I come across while studying for interviews. I like this problem.

A couple of days ago, I posted my attempt of the solution, asking if anyone knows the problem with my code. Link here - takes you to my instagram page. Screenshots here for those who don't have an instagram page.

As I solved the question again today, I added a few comments that I think will be useful for people who are not programmers.

The code I wrote below is an accepted solution, as well as how I look at the dictionary data structure.

It's in c#. This is the 2 sum problem, link goes to leetcode.

public int[] TwoSum(int[] nums, int target) {
        
        // initialize variables I need.
        int[] ans = new int[2];
        int index = 0;

        /*
        Included an explanation for dictionary. It's further at the bottom
        */
        Dictionary<int, int> map = new Dictionary<int,int>();


        // loop
        foreach(int num in nums) {
            
         // problem already says 2 numbers add up to target. 
         // So following statment is....bulls eye. Get it? target. bulls eye.
            var complement = target - num; 

          // If the dictionary doesn't contain the key, then it's safe to 
          assume that we have not come across it before
            if(map.ContainsKey(complement)) {
            
                ans[0] = map[complement];
                ans[1] = index;

                // if we have located both numbers, it's time to return....to writing
                return ans;
            }

            // Sadly, we continue the loop. To not continue this journey forever, we add this number to the loop

            map[num] = index;
            index++;
            
        }

        return null;
    }
}

In the real world, when we use a dictionary, we look for a word, and get the meaning.

As kids we are taught that if we go alphabetically, we'll find the word "life", and hence the meaning of life

Anyway, in computer science lingo, a real-life dictionary is a hashmap, with a hash function.

Since computers are not smart, we need to tell a computer exactly what to do.

So essentially we are telling the computer, anytime I add something, I also want something else stored along with it.

The fun, however, starts with the hashing function. The hashing function is a function that tries very hard to give the value instanteously.

I can't go into more details of the hash function now, since beyond this an actually strong explanation is required. That is beyond my skill level right now.

What I can do, is tell a story, to encourage you to think of hash functions like this:

Once upon a time, there was a child, an adult and a word called life.

Child asks for meaning of life.

Adult says look in dictionary.

Child can't read.

Child gives adult dictionary.

Adult can read, and knows that the words are alphabetically organized in dictionary.

Or, the words in a dictionary are ordered lexicographically.

She knows 'life' comes before 'monkey'.

Using this fact, she uses lexical ordering, and looks for words starting with the letter L, but not 'lose'.

Then, after seeing how the hash function has to do with ordering, she tells the kid the meaning of life.