Coding Practice - Easy - Two Sum

Here in the article I would love to share a methodology how to attack the coding/algorithms problem during the DS interview.

Let's start with Leetcode simple problem - Two Sum:

Given an array of integers?nums?and an integer?target, return?indices of the two numbers such that they add up to?target.

You may assume that each input would have?exactly?one solution, and you may not use the?same?element twice. You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].        

1. Brute Force Solution

First of all you should ask clarification questions to make sure you understand clearly the task and conditions. In our case important information worth mentioning - is each case has exactly 1 solution, you cannot use the same element twice, you can return the indices in any order.

Having that said we can describe a simple and intuitive (but not always optimal) solution to show that we really can solve the problem properly and then discuss its optimization. (Here we will do it in Python).

Note* It is also important to show your ability to write the proper and clean code not only to solve the problem.

Tips - use meaningful variable names, use spaces to make code blocks more visible/readable, use comments when needed, use classes and functions, and follow the rule "Do not repeat yourself".

# Brute Force

class Solution:
  

  def twoSum( nums, target):


    scale = len(nums)


    for i in range(scale-1):
      for j in range(i+1, scale):
        
        if nums[i] + nums[j] == target:

          return [i, j]


    return None        

Let's analyze out solution in terms of Complexity O - how many operations we have to perform in order to find solution in general case.

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

i = 11 -> [j = 15, j = 2, j = 7]
i = 15 -> [j = 2, j = 7]
i = 2 -> [j = 7]

The Complexity of this algorithm is the sum of all iterations that we perform -> (n-1)+(n-2)+(n-3) which in general case mean (n-1)+(n-2)+(n-3)+...(n-(n-1)) = n/2 * (n-1) = (n^2)/2 - n/2 

        

The highest order is our key indicator. We also can drop any constants around the highest order (this property comes with limit theory) so we have n-squared number of operations for n-length vector or O(n^2) Complexity.

In general interviewing case you are expected to build more efficient algorithm. Let's improve our attempt. On of a traditional way to improve the Operations complexity is using hashes - data structure that remember all previous steps so we can go through the array only once. It is called Space vs Complexity trade-off. The improved solution with using hash looks like following:

# Hash Solution

class Solution:
  

  def twoSum( nums, target):
    

    hashmap = {}


    for index, value in enumerate(nums):


      if value not in hashmap:
        
        hashmap[target - value] = index

      else:
        

        return [hashmap[value], index]



    return None        

in this case we loop through the array only once and return the needed answer. This solution has linear Complexity where the number of operations corresponds the dimension of the problem - O(n).

Note*. Please pay attention to the IF - statement. The condition "value not in hashmap" is controversial. Someone may say that checking if a value is not in a list or dict is also linear - O(n) and not O(1) as we assume. In this case we can use the condition "hashmap.get(value)" the dictionary is indexed and getting value by index is O(1) operation. But Leetcode does not accept this construction. Jupiter Notebook does.

My best wishes to all DS interns and all readers mastering their algorithms skills!

Best regards!