Daily Coding Problem: Problem #1

With the COVID-19 and lock-down in effect, I have decided to sharpen my coding skills. So I started looking for products in ProductHunt that can help me out. I then stumbled upon this product called DailyCodingProblem. I understand this product is an old one, but this is the first I have ever come across this!.

When you subscribe to DailyCodingProblem, they send you a problem every day to solve. I tried to solve the problem and thought why not post it as a blog on medium and improve my writing skills as well. I will be implementing the problems in Python and Go programming languages.

Problem

Given a list of numbers and a number k, return whether any two numbers from the list add up to k.

For example, given [10, 15, 3, 7] and k of 17, return true since 10 + 7 is 17.

Bonus: Can you do this in one pass?
Note: This problem was asked by Google.

We will come to the bonus part later.

The most straightforward approach that comes to our mind is to run two loops and check if the elements add up to the given target. If you arrived at the same solution at first glance, it’s okay!. That is the answer.

Solution 1: Using two loops

Python:

Go:

Time Complexity: O(n²)

Space Complexity: O(1)

If we observe closely, we are checking if the difference between the value k and the element exists in the array or not. Doing so makes us iterate the array once again hence our time complexity becomes O(n²). What if we can check if the element exists in the array in O(1) time. Yes, we can! using a hash-table. Every time we compute the difference, we check if the difference is present in the hash-table. If the difference is present, we can return True and end the computation. If not, we have not come across such element and add the current element to the hash-table. At the end we will return False if no elements match the target sum k.

Solution 2: Using hash-table

Python:

Go:

Time Complexity: O(n)

Space Complexity: O(n)

I hope you guys enjoyed this post.

If you find it helpful, please share and claps are much appreciated! 😄

Feel to ask your queries in the comments section!.