Home

Daily Coding Problem #1 - Two Sum

February 17, 2019

From today I’ll try to solve a programming problem every single day using Golang and push it up to https://github.com/khoi/daily-coding-problem-in-go/ These programing problems are tailored, curated by Daily Coding Problem. I highly recommend that you subscribe to them to exercise your brain everyday.

The first problem I’m solving today is Two Sum, which should be a trivial one.

Problem

This problem was recently asked by Google. 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?

Solution

This can be solved in just 1 pass, by storing all the number that we’ve passed through in a map[int]struct{}. And for each element, we check whether the map[k - currentNumber] exist. If it exists, then we find a match!

1_two_sum.go

package daily_coding_problem_in_go

func TwoSum(nums []int, k int) bool {
	m := make(map[int]struct{})

	for _, e := range nums {
		if _, ok := m[k-e]; ok {
			return true
		}
		m[e] = struct{}{}
	}

	return false
}

1_two_sum_test.go

package daily_coding_problem_in_go

import "testing"

var tests = []struct {
	arr      []int
	k        int
	expected bool
}{
	{[]int{10, 15, 3, 7}, 17, true},
	{[]int{10, 15, 3, 7}, 10, true},
	{[]int{10, 15, 3, 7}, 3, false},
	{[]int{10, 15, 3, 7}, 26, false},
}

func TestTwoSum(t *testing.T) {
	for _, tc := range tests {
		if actual := TwoSum(tc.arr, tc.k); actual != tc.expected {
			t.Errorf("arr = %v, k = %v, got %v, want %v", tc.arr, tc.k, actual, tc.expected)
		}
	}
}

Time Complexity: O(n)