DEV Community

dev.to staff
dev.to staff

Posted on

Daily Challenge #63- Two Sum

Write a function that takes an array of numbers (integers for the tests) and a target number. It should find two different items in the array that, when added together, give the target value. The indices of these items should then be returned in a tuple like so: (index1, index2).

For the purposes of this kata, some tests may have multiple answers; any valid solutions will be accepted.

The input will always be valid (numbers will be an array of length 2 or greater, and all of the items will be numbers; target will always be the sum of two different items from that array).

Based on: https://leetcode.com/problems/two-sum/

twoSum [1, 2, 3] 4 === (0, 2)

Thank you to wthit56 and CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

Discussion (21)

Collapse
citizen428 profile image
Michael Kohl • Edited

F#

The other solutions posted so far were O(n2 ), I opted for an O(n) solution with a map and a recursive nested helper instead. I also didn't want to trust the input list, so went for a (int * int) option return type.

module TwoSum

let twoSum l n =
    let rec twoSum' l i n m =
        match l with
        | [] -> None
        | (x :: xs) ->
            let diff = n - x
            match Map.tryFind diff m with
            | Some(j) -> Some(j, i)
            | _ -> twoSum' xs (i + 1) n (Map.add x i m)
    twoSum' l 0 n Map.empty

Tests:

module TwoSumTest

open FsUnit.Xunit
open Xunit
open TwoSum

[<Fact>]
let ``finding a sum in 3 element array`` () = 
   twoSum [1; 2; 3] 4 |> should equal (Some (0, 2))

[<Fact>]
let ``finding a sum in 2 element array`` () = 
   twoSum [4; 5] 9 |> should equal (Some (0, 1))

[<Fact>]
let ``finding a sum in bigger array`` () = 
   twoSum [4; 5; 6; 7; 8; 9] 17 |> should equal (Some (4, 5))

[<Fact>]
let ``too short array`` () =
    twoSum [1] 2 |> should equal None

[<Fact>]
let ``no sum`` () =
    twoSum [1; 2; 3;] 7 |> should equal None

Collapse
avalander profile image
Avalander • Edited

Haskell

A recursive solution that checks for each item x in the list if there is an item in the rest of the list that, added to x, results in the target value.

import Data.List (findIndex)

twoSum :: [Int] -> Int -> (Int, Int)
twoSum xs n = findSum (head xs) 0 (tail xs)
  where
    findSum x curr ys = case findIndex (isSum x) ys of
      Just(i) -> (curr, i + curr + 1)
      Nothing -> findSum (head ys) (curr + 1) (tail ys)

    isSum x y = x + y == n
Collapse
peledzohar profile image
Zohar Peled • Edited

The input will always be valid that's even worst than premature optimizations.

However, for the purpose of this challenge, I'll take that assumption, because while super important, input validation is boring.

My answer inspired by willsmart's answer.

C#, with comments on every line, so that everyone can understand it even if they don't speak the language:

The simple, O(n2) solution - using a nested loop.


    (int Index1, int Index2) TwoSum(int[] array, int target)
    {
        // iterate the array from 0 to length -2
        for (var i = 0; i < array.Length - 1; i++)
        {
            // iterate the array from i+1 to length -1
            for (var j = i + 1; j < array.Length; j++)
            {
                // if sum found
                if (array[i] + array[j] == target)
                {
                    // return both indexes
                    return (i, j);
                }
            }
        }
        // indicate no match found, required by the c# compier.
        return (-1, -1); 
    }

The sophisticated, O(n) solution - using a single loop and a helper hash map.

    int Index1, int Index2) TwoSumImproved(int[] array, int target)
    {
        // In .Net, A dictionary is basically a hash map. here the keys and values are both ints
        var map = new Dictionary<int, int>();

        // iterate the full length of the array.
        for (var i = 0; i < array.Length; i++)
        {
            // calculate the value needed to add to the current value to get the target sum
            var valueNeeded = target - array[i];

            // check if the map contains the value needed as it's key, If it does, return true and populate the int j
            // The TryGetValue time complexity is approaching O(1)
            if (map.TryGetValue(valueNeeded, out int j))
            {
                // return both indexes
                return (j, i);
            }
            // add to the map, where the key is the array value and the value is the index.
            map.Add(array[i], i);
        }
        return (-1, -1); // indicate no match found
    }

Try it online

Collapse
brightone profile image
Oleksii Filonenko

Inspired by Michael Kohl's solution in F# (O(n) rules!), I did the same thing in Rust. All the credit to him :)

fn two_sum(ns: &[i32], sum: i32) -> Option<(usize, usize)> {
    let mut map = HashMap::new();
    for (i, &n) in ns.iter().enumerate() {
        let diff = sum - n;
        if let Some(&j) = map.get(&diff) {
            return Some((j, i));
        }
        map.insert(n, i);
    }
    None
}
Collapse
devparkk profile image
Dev Prakash

global sum_value
sum_value = int(input("Enter the sum value :"))
arr = [ int(i) for i in input("Enter array elements :" ).split( )]
def two_sum (arr) :
    for i in range(len(arr)) :
        for j in  range(i+1 , len(arr)) :
            if arr[j] + arr[i] == sum_value :
                return (i , j)
        return "NO SUCH PAIRS FOUND"

print (two_sum(arr))

Another one

global sum_value
sum_value = int(input("Enter the sum value :"))
arr = [ int(i) for i in input("Enter array elements :" ).split( )]
def two_sum (arr) :
    for i in range(len(arr)) :
        second_num = sum_value - arr[i]
        if second_num in arr :
            return (i , arr.index(second_num))
    return "NO SUCH PAIRS FOUND"
print (two_sum(arr))
Collapse
peter279k profile image
peter279k

Here is the Python solution:

def two_sum(numbers, target):
    num_index = 0
    for number in numbers:
        index = 1
        while index < len(numbers):
            if number + numbers[index] == target:
                return [num_index, index]
            index += 1
        num_index += 1

    return [0, len(numbers)-1]
Collapse
colorfusion profile image
Melvin Yeo • Edited

In Python, written with a O(n) solution with the given assumptions using a dictionary and enumeration to generate an index.

def twoSum(arr: list, target: int) -> (int, int):
    num_dict = dict()
    for index, num in enumerate(arr):
        diff = target - num
        if diff in num_dict:
            return (min(index, num_dict[diff]), max(index, num_dict[diff]))
        num_dict[num] = index

    raise IndexError
Collapse
fennecdjay profile image
Jérémie Astor

In gwion:

fun <~int, int~>Tuple twosum(int data[], int total) {
  for(int i; i < data.size(); ++i) {
    for(i + 1 => int j; j < data.size(); ++j) {
      if((data[i]+data[j]) == total)
        return <(i, j);
    }
  }
  return null;
}

([1, 2, 3], 4) => twosum @=> >(index0, index1);
<<< index0, " ", index1 >>>;

The fun thing is that it undercovered a (now fixed) bug on tuple unpacking. 🍾

Collapse
playwright2poli profile image
playwrightpo • Edited

Ruby

The initial solution comes to mind which obviously could be improved in performance purposes having more time

  def two_sum(array, target)
    array.each_with_index do |item, i|
      (i + 1).upto(array.size - 1) do |j|
        return [i, j] if item + array[j] == target
      end
    end

    nil
  end
Collapse
craigmc08 profile image
Craig McIlwrath

Haskell:

import Control.Applicative
import Data.List (find) 

twoSum :: (Eq a, Num a) => [a] -> a -> Maybe (Int, Int) 
twoSum xs target = let withId = zip xs [0..]
                       sums = (\(x,a) (y,b) -> (x+y, (a, b))) <$> withId <*> withId
                   in find ((==target) . fst) sums >>= (return . snd)

I know the question said the input is always good, but I didn't want to ignore possible errors in when using the function...

I'm not sure of the speed of this code either. My guess is it only evaluates combinations until it finds a correct one? But I'm not an expert on lazy evaluation and I'm pretty sure this could be faster.

Collapse
citizen428 profile image
Michael Kohl

My guess is it only evaluates combinations until it finds a correct one?

Yes, Data.List.find will return the first list item satisfying the predicate.

Collapse
aminnairi profile image
Amin

JavaScript

Recursive solution.

"use strict";

const addWith = target => current => target + current;
const equalsTo = target => current => target === current;

function twoSum(numbers, sum, index = 0) {
    if (numbers.length === 0) {
        return null;
    }

    const [first, ...rest] = numbers;

    const foundIndex = numbers.map(addWith(first)).findIndex(equalsTo(sum));

    if (foundIndex > 0) {
        return [index, foundIndex + index];
    }

    return twoSum(rest, sum, index + 1);
}

console.log(twoSum([18, 7, 1, 6, 0, 15, 3, 12, 111, 1111], 4)); // [2, 6]

Try it online.

Collapse
willsmart profile image
willsmart

reduce is good for this one.
Here's a JS quickie with O(n) complexity.

twoSum = (numbers, target) => numbers.reduce(([result, partials], num, i) => ([
  result || (num in partials && [partials[num], i]), 
  Object.assign(partials, {[target - num]: i})
]), [undefined, {}])[0]

The partials map maps the index of each value to the value required to bring it up to the target. This can then be picked up by a later value to the get the answer.

Collapse
choroba profile image
E. Choroba

Perl solution. Walk the array, for each element, store the expected counterpart into a hash. If the element already exists in the hash, we have the pair.

#!/usr/bin/perl
use warnings;
use strict;

sub two_sum {
    my ($arr, $sum) = @_;
    my %expect;
    for my $i (0 .. $#$arr) {
        return [ $expect{ $sum - $arr->[$i] }, $i ]
            if exists $expect{ $sum - $arr->[$i] };
        $expect{ $arr->[$i] } = $i;
    }
}

use Test::More tests => 2;
is_deeply two_sum([1, 2, 3], 4), [0, 2];
is_deeply two_sum([1 .. 99], 197), [97, 98];
Collapse
themisir profile image
Misir Jafarov
const twoSum = (a,b) => {
  for (var x=0; x<a.length; x++)
  for (var y=x+1; y<a.length; y++) {
    if (a[x] + a[y] == b) return [x,y];
  }
}
Collapse
ahmed1921 profile image
ahmed1921

Swift Solution

class Solution {
static func twosum(numbers: [Double], target: Double) -> [Int] {
let result = numbers.filter({ return numbers.contains( target - $0 ) })

return [numbers.firstIndex(of: result[0])! , numbers.lastIndex(of: result [result.count - 1 ] )!] }
}

Collapse
ahmed1921 profile image
ahmed1921

class Solution {
static func twosum(numbers: [Double], target: Double) -> [Int] {
let result = numbers.filter({ return numbers.contains( target - $0 ) })

return [numbers.firstIndex(of: result[0])! , numbers.lastIndex(of: result [result.count - 1 ] )!] }
}

Collapse
srisrinu profile image
SRINU
def twoSum(arr,target):
    for i in range(len(arr)-1):
        for j in range(i+1,len(arr)):
            if(arr[i]+arr[j]==target):
                return([i,j])
    else:
        return("no indices found with that sum")
if __name__=="__main__":
    arr=list(map(int,input().split()))
    target=int(input())
    print(twoSum(arr,target))
Collapse
chrisachard profile image
Chris Achard

The target example is given as:

twoSum [1, 2, 3] 4 === (0, 2)

But I believe that should be something like:

twoSum [1, 2, 3] 4 === (1, 3)

correct?

Collapse
savagepixie profile image
SavagePixie

No, because it returns the indices, not the values.

The indices of these items should then be returned in a tuple like so: (index1, index2).

Collapse
chrisachard profile image
Chris Achard

OH! missed that :) Thanks!