Adding duplicate keys to Python dictionary ("Two Sum" Problem)

Question

I've been trying to add duplicate keys to my python dictionary (table) in order to solve the "two Sum" problem.

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

I've now realized this is impossible to do and would appreciate any ideas or suggestions on how to go about solving this problem without brute force. Please keep in mind i started trying to learn Python this week. So i apologize of theres a simple solution

numbers = [0, 0, 0, 0, 0, 0, 0]  # initial list
target = 6  # The sum of two numbers within list

# Make list into dictionary where the given values are used as keys and 
actual values are indices
table = {valueKey: index for index, valueKey in enumerate(numbers)}

print(table)

>>> {0: 6}

welcome to stackoverflow! your question might already have an answer here: https://stackoverflow.com/questions/10664856/ — MCO, Sep 20 '18 at 20:35
@khachik Well my reasoning for duplicate keys was that i would store the values as keys and the index as the actual value. Then i could get (target - current iteration) and just lookup the result. I now know that its not possible lol — FlightlessBird, Sep 21 '18 at 01:21

Woody1193 · Accepted Answer · 2018-09-21T14:00:52.913

You don't need to store the index at all because the two sum problem isn't concerned with where a number is located, just with finding them. This can be accomplished by:

target = 6
numbers = [1, 5, 11, -5, 2, 4, 6, 7, 21]
hashTable = {}
results = []
for n in numbers:
    if ((target - n) in hashTable and hashTable[target - n] == None):
        hashTable[target - n] = n
    else:
        hashTable[n] = None

results = [[k, v] for k, v in hashTable.items() if v != None]
print(results)

In the case where you want the index of your numbers, you could add a second dictionary indices:

indices = {}
for i, n in enumerate(numbers):
    if ((target - n) in hashTable and hashTable[target - n] == None):
        hashTable[target - n] = n
    else:
        hashTable[n] = None
    indices[n] = i

results = [[indices[k], indices[v]] for k, v in hashTable.items() if v != None]
print(results)

Note that for both of these solutions to work, you need to guarantee that each element only appears once in the list. Otherwise, your sums would be ambiguous. You could modify indices to store a list of the indices where a particular value occurs and that would solve that problem.

I need the index of both numbers returned not the numbers themselves. And your last line returned an error but i see what your getting at. Thank you! — FlightlessBird, Sep 21 '18 at 01:26
Ah, well in that case, I would suggest using a class or tuple. — Woody1193, Sep 21 '18 at 13:50

score 0 · Answer 2 · answered Sep 20 '18 at 20:43

Not really sure what specifically you need the dup keys for, but you can use a list of values:

import collections

table = collections.defaultdict(list)

for i, value in enumerate(numbers):
    table[value].append(i)

diffs = enumerate(target - number for number in numbers)

for i, diff in diffs:
    if diff in table:
        indices = table[diff]
        indices.remove(i)
        if indices:
            print i, indices

I believe there are better solutions for this task, would be good to see other answers.

score 0 · Answer 3 · answered Sep 20 '18 at 20:44

0

I don't see why you need a dict, unless you had multiple targets. I would use a set instead.

numbers = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 9
answer = set()
for i, iNumber in enumerate(numbers):
    for j, jNumber in enumerate(numbers):
        if i == j:
            continue
        mySum = iNumber + jNumber
        if (mySum == target):
            answer.add((i,j))

answered Sep 20 '18 at 20:44

mannyglover

2,139
14
18

3

That is what the OP is calling "brute force" and is trying to avoid, it is n^2. – khachik Sep 20 '18 at 20:45
Hmmm... yeah, I know it could be expressed more succinctly and "pythonically", @khachik, but I don't see how the computation time could be sped up, without any restrictions on the input array. Can you devise a way? – mannyglover Sep 20 '18 at 20:49
1

I did in my answer – khachik Sep 20 '18 at 20:50
1

and it is not about "pythonical" or something else, it is about run time complexity. – khachik Sep 20 '18 at 20:52

score 0 · Answer 4 · answered Sep 20 '18 at 20:48

I would sort the array, do some kind of binary search to search your target's index (or the immediate minor) and look for the "two sum" in the index between the smaller and the index found using binary search.

For example: array = [5,1,8,13,2,4,10,22] target = 6

sorted_array = [1,2,4,5,8,10,13,22] binary_search_index = 4 (number 5)

So know you reduced your array to: [1,2,4,5] and you can look de "two sum" there, probably using de min and the max index.

Adding duplicate keys to Python dictionary ("Two Sum" Problem)

4 Answers4