How I solve a simple problem, as a developer

Whoa, It been a while since my proposal to write but it is better late than never :D

I had a friend who is just into the IT field lately and yesterday we had a session on solving a program puzzle on Leetcode.com yesterday. It is simple to me, but to explain what to do to my friend - a newbie, I had to specify my way of thinking to him so that after all - it is him who solve the puzzle

And the puzzle was:

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the/same/element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1]

And we will do them in Python - a language I never did before and he only began to learn

‘Where do we go from here?’ - Thanh Bui

1. First thing first, understand the problem

To think on the problem, the least thing to do is to know about it first.

I explain to my friend what ‘indices’ is and told him to rephrase the question in his own way. Then we came up with this:

With a given array of integers, find the position of two elements whose sum equal to a given target.

There is only one solution for each input and the element will now be added to itself.

2. Break the problem into smaller problems:

To me, complicated problem is just a bunch of mixed simple ones, it always has been.

From the rephrased question, to produce a valid result we will need:
- Read the value from an array
- Combine all the possible pair of numbers
- Compare if their sum equal to the target

The easiest objective is the third one:
if the number a plus number b equal target then print them out

if (a + b) == target
  print(a, b)

The first one is something we will just mock them, like the example:

 nums = [2, 7, 11, 15]
 target = 9

Later we can use the leetcode’s template to get the input from the website. This is easy.

The most tricky lies in the second simple problem - Combine all the possible pair of numbers, how to let the computer do that

When I tried to explain to him about a loop within a loop, all the memories about my struggles when I first started learning programming came back and also how I came over them.

During my time in high school, I am not good at math (all my childhood friend can confirm this). But I have been also not been afraid of math. The young Nemo always tried to look at the question closely and not to avoid understanding the teacher’s answer when he can not came up with his own answer, his given logic along the way. Practice this help me a lot in studying IT and later develop my own thinking, and ESPECIALLY refactoring other people’s legacy code.

P/s: I had to review my knowledge on ECDSA, the last time I read about it I was so sleepy I skipped half of the explanation.

This is the result when we try to visualize all the combination of two in the given array:

Oh boy, I hope you do not crash…

My friend fell into silence for a while, I could see the duck on his face. I, myself also get overwhelmed by alien symbol that a supposed-to-be-simple problem produce.

But then, the most important thing is that you must not be afraid!

So we try to repeat the process of drawing this but with much more attention, line by line, we decide to observe if a pattern come up in the process of drawing lines. Then we realize: the idea is to map each of the element in the array to the rest of the array. What we do with ‘a’, we will apply the same pattern with ‘b’,’ ‘c’ and ‘d’.

So I told my friend to think about the idea of a loop within a loop, and how to express that in Python. It is him who need to catch up, not me, though. I have been raped by those struggle already.

3. Fill knowledge gap to achieve main objective:

You can find anything on Internet. Just make sure that you validate the information yourself and make them your knowledge at the end

`Modern programming is all about googling the right keyword` — Nemo Pham

In programming, for these problem like this. I have my own priority on reference:
- The brightest hope for instant solution will be from Stackoverflow or gitHub issues
- For a more of tutorial content, go for tutorial point or w3school
- For a deeper research, Medium or original pages on your interested field(mongoDb, ethereum) is the place to go
- Other sites is for desperate situation only
(Please remember everyone’s reference differs)

Now that we know what we want, let’s google it:

And be ready for one article lead to another article, a knowledge require some prerequisite knowledge. A result may not hold all the answer that you need but you also should try to focus on the main objective, do not get lost in the ocean of data.

After quite a while, he came up with this:

for (index1, num1) in enumerate (nums):
 for (index2, num2) in enumerate(nums):
  # skip condition
  if (index1 == index2):
   continue
  if (num1 + num2 == target):
   print(index1, index2)

And a list of ‘to read later’:
- Loop syntax
- Enumerate usage
- Tab scope

We run the code and it actually works! Produce the correct answer.

But there is more to do..

4. Try to make it work better:

Reviewing the way of looping, I told my friend that there are duplicated pair and we should do something about that

We will need to achieve this:

No duplicate pair included!

And that will reduce the earlier alien symbol into this:

Less line, less computation needed, less processing time

In the picture, we will not try to pair 1st number to the 2nd number that have the index lower than the current index of 1st number

for (index1, num1) in enumerate(nums):
 for (index2, num2) in enumerate(nums):
  # skip condition
  if (index1 >= index2):
   continue
  if (num1 + num2 == target):
   print(index1, index2)

In fact, the complexity of my code reduce from

n^2 - n

to

(n^2 / 2) + n

NOTE: n is the length of the given array

Or for more general conclusion: they reduce about half of the work of pairing

The final code, together with the template from the leetcode submission’s page:

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for (index1, num1) in enumerate(nums):
    for (index2, num2) in enumerate(nums):
     # skip condition
     if (index1 >= index2):
      continue
     if (num1 + num2 == target):
      return[index1, index2]

The result I got from Leetcode after submission:

I later spent sometime explaining on the space - time spectrum to my friend but sure it is not within the scope of this article

# The end.

And yeah, that was it. If you read till this point, it is either I am an amazing tutor or you have too much of your free time and read this. Anyway, I hope I gave you a good approach on dealing with problem and see the fun behind all the academic knowledge.