Leetcode problem — Two Sum

If you are finding motivation to read this blog series rather than any other, then here are some reasons:

1. Blog covers major of the questions that should be asked to recruiter. This gives an idea of which type of questions can be asked to recruiter. Asking clarifying questions to a recruiter is important since this shows that an individual doesn’t start to directly work on problem and then have to reverse the work simply because of a misunderstanding(which wastes company’s resources), instead gives in time to understand the problem and then start solving the problem.
2. Blog cover why to choose the particular approach and why can’t we do this problem using other approaches. It explains significance of every line in code which helps us to understand the code better plus gives us an idea of when to use in future.
3. Blog gives an idea of alternative approach that can be or cannot be used. This would help you to understand when/when not use an approach. This would also help in coming up with new approaches in interview and in general as well.

Problem: 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].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

This question provides all the details needed to solve the problem but a recruiter won’t provide all the details and we need to ask questions to really understand the correct question.

Questions to ask recruiter:

1. Is the list sorted?
2. Could there be multiple solutions possible?
3. Is there a possibility of no solution? If yes, then what would be returned if no solution exists?
4. Are all elements in nums integers? Negatives?
5. Can same element be used twice?
6. Does the order of result indices matter or can they be sent in any order?
7. What needs to be returned, elements or their indices?
8. Do we have enough space to store dictionary containing (key, value) pair.
9. Do i need to check if the list is a valid list? I mean do we need to check if the length is less than two or not?

These are some questions that i think need to be asked in order to understand the problem more efficiently. Please add questions in comment that you think will help in better understand the problem.

Approach 1: This is a bruteforce approach where we perform linear search for every element and check if there’s any element that is equal to target —(current element). If found, we return the pair of indices in list otherwise we traverse the array for the element in list. This process is repeated until we find any result pair.

Time complexity: O(n²)

Space compexity: O(1)

Note: This approach can be used when we have memory limitations i.e. we don’t have enough available memory for hashmap.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for index in range(len(nums)):
            other_number = target - nums[index]
            #Linear Search O(n)#
            for index2 in range(index+1, len(nums)):
                if other_number == nums[index2]:
                    return [index1, index2]

Since we do linear search for every element in nums, the option of binary search comes into mind to reduce time complexity of search to O(lg n). But we cannot use binary search since we need to return indices and sorting the list would change the order of indices.

Approach 2: The next approach would be to traverse array once and add all the elements in (key, value) format i.e. (element, index) in dictionary. Traverse the list again and for every element, check if (target - current element) is present in hash maps. If it is, return the current index and corresponding index.

Time complexity: O(N)

Space complexity: O(N)

class Solution:
     def twoSum(self, nums: List[int], target: int) -> List[int]:
          buffer_dictionary = {}
          for index in range(len(nums)):
              buffer_dictionary[nums[index]] = index
          for index in range(len(nums)):
              other_number = target — nums[index]
              if other_number in buffer_dictionary:
                   return [buffer_dictionary[other_number], index]

This approach can even be done in one pass rather than two pass. Won’t affect time complexity but will affect the time for program to execute.

Approach 3: The third approach is to use a dictionary(key, value -> elements in array, corresponding indices) and whenever we see an element, we check if target-(current element) is already present in dictionary. If it is, then we simply return the current index and the index corresponding to (target-current element). Otherwise, we add (element, corresponding index) to dictionary.

Time complexity: O(n)

Space complexity: O(n)

class Solution:
     def twoSum(self, nums: List[int], target: int) -> List[int]:
          buffer_dictionary = {}
          for index in range(len(nums)):
              other_number = target — nums[index]
              if other_number in buffer_dictionary:
                   return [buffer_dictionary[other_number], index]
              buffer_dictionary[nums[index]] = index

Key points to note:

1. No need for return statement after for loop at the end as there is exactly one solution. So, it would never exit for loop since at one point, it would return the two indices. We would return [-1, -1](check with interviewer what to return) if there was a possibility
2. If we had to return the elements instead of indices, we could have used set to store elements in list rather than store (element, index) pair in dictionary.
3. Since exactly one solution should exist, we don’t need to add to check for cases when there is no element or just one element in list.

Check if other data structures that can be used:

1. Linked list: Nope. Since there isn’t any element in linked list and adding it into list help either because we’ll still have to search for other element and we either have to traverse the entire list or we have to put it in map. So, it won’t improve space or time complexity.
2. Stack/ Queue: We can add every element to stack/queue and simultaneously we need to add element to dictionary to store the element, index pair. When traversing list, for every element we will check if (target- element), if yes then we will return current index and corresponding index in map. Else, we will add that element to stack and add (element, index) pair in map as well. Time: O(N); Space: O(N) {Additional space is needed to store stack as well.}
3. Heaps: Nope. Same as linked list
4. Trees: Maybe binary search tree. First, we add all the elements to a BST. For every element, we search in the tree to check if (target-element) is present in tree. Time complexity to search in BST is O(lgN). But space complexity would be lot more to create tree and store all the values in it. Time: O(NlgN); Space: O(N)
5. Graph: Nope. There is no connection between any two elements. All the elements are in list and there isn’t any connectivity between nay two elements.
6. Bit manipulation: Nope. Since by using xor, and, or we cannot find the other element. It’s addition of two elements that makes target and xor, and,or cannot be used.

Let me know in comment if there’s any problem that you want me to write similar blog on. Hope you liked reading it and it was informative.