Not going to lie. I currently suck at coding problems. And I'm tired of it. So I'll do my best next year to start working on getting Leetcode problems to practice that which I currently lack.

I'll apply the process suggested in cracking the Coding Interview by Gayle Laakmann McDowell

1. Listen
2. Example
3. Brute Force
4. Optimize
5. Walkthrough
6. Implement
7. Test

So let's begin:

First, we start by reading the 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.

First, they will give you an array of integers and an integer as the target. Mind that they specifically request the indices instead of the numbers. This would mean that the order of appearance is important.

Also, they mention that there is only one solution and the element cannot be used twice. For example, if the sample array is

array = [1,2,3,4,5] 
target = 10

array [4,4] // Not a Solution since [4] can only be used once. 
array [n,n] // Not a solution 
array [n,m] // where n != m 

Let's see the examples provided

Example 1:

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

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]
Exaplanation: Because nums[1] + nums[2] == 6 and they are in order

Example 3:

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

Leetcode is providing us with the importance of order. Take example #2. If you sort the positions of the numbers to find the number, then you will mess up the order.

Finally, let's look at the constraints:

Constraints:

2 <= nums.length <= 104

-109 <= nums[i] <= 109

-109 <= target <= 109

Only one valid answer exists.

Looks like the numbers don't go too far. Ok, so this should process quite fast. Or at least it should since our algorithm should allow it.

Brute Force it

We have to get the position of two sums and then add them. The two sums cannot be equal: for example array[n, n]. It needs to be an array[n, n+1].

So we can double loop the array to find the sums.

class Solution: 
  def twoSum(self, nums: List[int], target: int) -> List[int]: 
    """  
    Time complexity: O(N*N)
    Space Complexity: O(1)
    """
       
    for i in range(0, len(nums) - 1): 
        for j in range(1 + i, len(nums)): 
            if nums[i] + nums[j] == target:
                return [i,j]
    return []

Optimize

The last example is technically an answer and will solve the problem.

But… It's slow.

Let's optimize this example. We know that the target is the sum of two numbers in the list nums so:

target = x + y where x != y

x and y are two different numbers in the list. We can setup the formula

y = target — x

and finally set a hash table in terms of f(x) = target — x. Now we can set up generate a hash table with a number potentialValue.

If the potential value exists in the dictionary, then return the number in the dictionary with the current position of the complementary number, else add the num pos as value in the hash table.

Implement

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        """
        Time complexity: O(N)
        Space Complexity: O(N)
        """

        answerNums = {}

        for pos, num in enumerate(nums):
            potentialValue = target - num
            if potentialValue in answerNums:
                return [answerNums[potentialValue], pos]
            else:
                answerNums[num] = pos
        return []

Test

Luckily, Leetcode gives us a testing suite to try the answer

Hope this helps. Best of Luck.

Current Leetcode rank:

Check out my YouTube video on solving LeetCode Problem 1: CodeWithNacho — Mastering LeetCode Step by Step!