Cracking the Coding Interview With LeetCode — Day 2

We will solve our first Leetcode problem with the basic knowledge from our Day 1 article of this series. If you miss that post, please revise it. The first problem well will solve is the TwoSum problem from Leetcode.

Photo by Christina Morillo from Pexels

Before diving into the question of this problem, let’s see what the leetcode already provides for us. Assume that we don’t have any knowledge about this code. Step by step, we are going to understand.

Notes 1: [code-1]

class Solution:
 def twoSum(self, nums: List[int], target: int) -> List[int]:

From the code, the first line starts with a class named Solution. We will talk about the class in detail later. But, If you want, you can learn from w3School. Then, the second line is a function named TwoSum. In the function, we can see some parameters with their data type. Though we know, python is a dynamically typed language, that’s means we don’t have to declare any variables data type. So, why do they use data type? Because it helps the developer to understand. To make life easier, nothing else.

Let’s understand with an example:

Picture- 1A

From picture-1A, we can see that we use two integer parameters(line 2), but we pass one integer and a character in the arguments(line 5). Python accepts both and shows the output. Because python is not a strongly typed language, we use data type to help other coders what data should be passed.

Picture: 1B

The red circle data type reminds a developer that this function will return an integer data type.

Notes 2: Now, we will learn about the list as we can see from the note one code, leetcode use a nums list in the function. And this list contains integer data.

There is no array in python. Array type all work done by list in python. So, a List is a container that stores different types of data.

For Example: [code-2]

profile = ['mahmud',1216,'Mirpur']

Table: List of Profile [code-2]

The first value of the profile list is a string whose index or position number is zero, then an integer value and index number are one, and the last one is also string with index number two.

If you want to add another value to this list, you can use the following code,

Picture: 2A

We use append to add new data to our list, and this value-added to the last index = [3] of the list.

Notes 3: Now, we will try to print out the values with their index number, and it’s essential to solve today’s problem. Let’s learn how to print in both languages.

In python, we can use enumerate function to print both: [code-3]

profile = [ 'mahmud',1216,'mirpur'] # list
profile.append('bio.info/imash') # add a value
print(profile) # outout
# loop with index and value
for idx, val in enumerate(profile):
print(idx, val)

The output of code 3:

Picture: 3A

Here, ‘0’ — is the index, and ‘mahmud’ is the value.

‘1’ — is the index and ‘1216’ is out value. And so on.

In Go array can only store the same type of data. [code-4]

package main
import 'fmt'
func main() {
var nums = [3]int{1, 2, 3}
for i, element := range nums {
    fmt.Println(“element”)
    fmt.Println(element)
    fmt.Println(“index”)
    fmt.Println(i)
   }
}

Picture: 3B (output of code-4)

First of all, We create an array called nums, with three integer elements {1,2,3}. Then, we use a loop where range extract indexes from nums and store them in ‘i’ and value in element variables.

Notes 4: Let’s solve the Leetcode problem.

The question tells us that It will provide us with an array of integers and a target number. We have to find two numbers; the addition of these two numbers will be the target value.

For Example:

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

Using Go we will solve first:

Generally, If we think about how a human will find the answer. We will take two values and add them to get the answer. See how in detail:

Table: Two Sum Solutions Algorithm

Using this calculation let’s code with GO:

Step 1: The array’s length is 4 -1 = 3, which means, from index zero to index 3, we will find the target value.

Step 2: the first loop picks one value to add with other indexes.

Like: index [0] = 2

Step 3: Second loop runs from the next index of the first step and ends with the last list index. index [1,2,3]

Step 4: add two index and check the sum with target value, 2[0]+ 7[1] == 9

Step 5: If the condition is True then return a list with the index value,

return []int{i,j} 

Here, [] — represent a list, int — list of an integer value, {i,j} — items of the list.

Notes 5: Solve the problem in Python3 code:

We use the same logic as we used in Go.

Here, range(0,6) -> means it will consider zero to 5, not 6.

Notes 6: In both programs, the time complexity is O(n²).

How did we find that?

For a single value from the list, like 2. We have to add and check this with three other items on the list. For Example,

2 -> 7,11,15 [n-1] (Here n is number of items in the array r list)

We can say for ‘n’ elements, we have to check for (n-1) number of elements.

So, the calculation is:

n*(n-1) -> n²-n -> n² (In worst case)

If the list has four elements, then 4² = 16 times the program has to calculate.

Now, If you run the code, it will Accept. But DON’T Submit.

There is another point in the question,

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

We will try to deduct the ‘n’ calculation and make it O(n²) to O(n).

I know many things are not clear about this time complexity. In the following article, we will cover them all. This article is intended to show solving one problem with the basic syntax we learned.

To make the program O(n), we have to use Hashmap or Dictionary in python or map in Go, concept.

First, learn what is Dictionary in Python is?

Dictionaries are used to store data values in key: value pairs. Like:

profile_dictionary = {'nane': 'mahmud', 'location': 'mirpur'}

In this container of profile dictionary, the name is a key, and its value is mahmud. Dictionary is not like a list that linearly stores data.

No, we will understand why we use a Dictionary instead of a list.

>> num_dictionary = {2:7, 4:9, 5:2, 6:10} #dictionary
>> num_list = [2,4,5,6] # list
>> 4 in num_list
>> True
>> 4 in num_dictionary
>> True

From the code, when we search an item from a list, it will search linearly and check three times from the list, as it has a total of four items. But, if the list had 1 million items, you can imagine how much time it will need. However, in the dictionary, it will only ask whether the key is available or not for one time.

To understand this hashmap process, you can read Chapter 11 (Hash Table) from the book Introduction to Algorithms.

Using the concept, we are going to solve the Two Sum question.

Let's understand the code step by step:

Step 1: Length of the given list,

Assume our list if nums = [2,7,11,15]

So, length= 4

Step 2: hashmap = {} — Its an empty dictionary where we will store key and its valu.

Step 3: Run a loop from zero to 3

Step 4: we will subtract targe with nums[i]

Here, target = 9

nums[i] = nums[0] = 2

So, k = 9–2 = 7

Step 5: check k is in hashmap: No, 7 is not in the dictionary.

Step 6: store the num[0] item 2 as key and the index [0] as the value in the hashmap dictionary.

Now, hashmap= {2:0}

Again Following the steps we find,

Here, i = 1, k = 9–7 = 2

And, k=2 is in the hashmap: return the index of 2 from the hashmap [0] and the value of i= 1.

So, our output is [0,1]

As a result, we only work with a set of ‘n’ numbers, and the time complexity is O(n). We satisfy the follow-up requirement.

Notes 6: Code the new solution on Go Language.

The calculation is the same but the syntax is just different.

Here, we use a map, instead of a dictionary. But, it works the same as a dictionary.

We will discuss more on Go lang in our next article with more important context.

I know it’s a log article and maybe It will take too much time to understand. I recommend you to seat with pen and paper to understand the code in more detail.

I will be very glad if you comment on your suggestion and while reading if you find any mistake let me know. and Follow me on medium and get my other links from here: bio.link/imash Thank you. :)

Creaking the Coding Interview With LeedCode — Day 1