I'm trying to solve Three Number Sum in python by using For loop instead of worst time & space complexity I want to use for better understanding

Question

sample input array = [12, 3, 1, 2, -6, 5, -8, 6] targetSum = 0

sample output [[-8, 2, 6], [-8, 3, 5], [-6, 1, 5]]

my code is as follows:


def threeNumberSum(array, targetSum):

    array.sort()    
    for i in range(len(array) - 2):
        nums = []
        firstNum = array[i]
        for j in range(i + 1, len(array) - 1):
            secondNum = array[j]
            for k in range(j + 1, len(array)):
                thirdNum = array[k]
                potentialTarget = firstNum + secondNum + thirdNum
                if potentialTarget == targetSum:
                    nums.append(firstNum)
                    nums.append(secondNum)
                    nums.append(thirdNum)
                    return [[firstNum, secondNum, thirdNum]]
                
    return []

The explanation of what the algorithm should do is not clear to me. Can you explain more in detail? — ymmx, Jun 03 '22 at 14:38
Are you trying to obtain all matching tuples of length 3 (as [here](https://en.wikipedia.org/wiki/3SUM#Quadratic_algorithm)), or just the first one? Note that some optimization strategies can be found at the link. — constantstranger, Jun 03 '22 at 14:39
A `duplicated` post here - https://stackoverflow.com/questions/46066652/ — Daniel Hao, Jun 03 '22 at 14:51
@DanielHao My post is about for loop, might be duplicate for the problem but I was looking for the different solution. — AXz, Jun 03 '22 at 14:56

Samwise · Answer 1 · 2022-06-03T14:59:47.120

3

Your current algorithm is O(n^3). You could get it down to O(n^2) by iterating over all the 2-combinations, and using a O(1) hash lookup to find the third instead of doing another O(n) iteration:

def three_num_sum(nums, target):
    d = {n: i for i, n in enumerate(nums)}
    res = []
    for i, x in enumerate(nums[:-2]):
        for j, y in enumerate(nums[i+1:-1], i+1):
            z = target - x - y
            if d.get(z, 0) > j:
                res.append([x, y, z])
    return res

print(three_num_sum([12, 3, 1, 2, -6, 5, -8, 6], 0))
# [[-8, 2, 6], [-8, 3, 5], [1, -6, 5]]

edited Jun 03 '22 at 14:59

answered Jun 03 '22 at 14:44

Samwise

68,105
3
30
44

Thank you for the explanation. I understand it but I was trying to use for loop deliberately but I was not getting the result. – AXz Jun 03 '22 at 14:54
1

You can replace the `combinations` call with two nested `for` loops; I just used `combinations` for simplicity. The main point is that you can do it in two nested loops (instead of three) by using `Counter` to look up the third item in the sum. – Samwise Jun 03 '22 at 14:55
I iterated on this a bit and came up with a version that's much closer to your original code -- it's a little tougher to follow IMO because of the way the loops interact with each other, but it should actually be more efficient because it's using your original strategy of eliminating part of the list with each level of search. This lets us get rid of duplicates without having to use sets, and shortens some of the iterations, while still getting the benefit of eliminating the third level of iteration. Note that instead of using a Counter to track the items we have a dict of item to position. – Samwise Jun 03 '22 at 15:01

ymmx · Accepted Answer · 2022-06-03T14:46:45.547

1

I think you should place result in a list otherwise you will end the function before finding all possibilities

def threeNumberSum(array, targetSum):
    array.sort()
    possibilities = []
    for i in range(len(array) - 2): 
        firstNum = array[i]
        for j in range(i + 1, len(array) - 1):
            secondNum = array[j]
            for k in range(j + 1, len(array)):
                thirdNum = array[k]
                potentialTarget = firstNum + secondNum + thirdNum
                if potentialTarget == targetSum: 
                    possibilities.append([firstNum, secondNum, thirdNum])
    return possibilities

array = [12, 3, 1, 2, -6, 5, -8, 6]
targetSum = 0
print(threeNumberSum(array,targetSum))

answer

[[-8, 2, 6], [-8, 3, 5], [-6, 1, 5]]

edited Jun 03 '22 at 14:46

answered Jun 03 '22 at 14:40

ymmx

4,769
5
32
64

Maybe, but the code didn't give the correct answer – ymmx Jun 03 '22 at 14:42
@DanielHao I'm not considering for optimization in this solution, for that I can use pointer but I was trying to use list, I couldn't succeed though. Thanks for the help – AXz Jun 03 '22 at 14:47

score 0 · Answer 3 · answered Jun 03 '22 at 14:48

0

you can use itertools :

import itertools

arr = [12, 3, 1, 2, -6, 5, -8, 6]

def threeNumberSum(array, target_sum):
    return [perm for perm in itertools.combinations(arr, 3)  # you can change the perm number if you want another number combination length.
            if sum(perm) == target_sum]


# test
arr = [12, 3, 1, 2, -6, 5, -8, 6]
print(threeNumberSum(arr, target_sum=0))

output:

[(3, 5, -8), (1, -6, 5), (2, -8, 6)]

answered Jun 03 '22 at 14:48

mrCopiCat

899
3
15

Ok, I don't have this library and never used this. What it does? just for iteration? – AXz Jun 03 '22 at 14:51
1

This is still an O(n^3) iteration. – Samwise Jun 03 '22 at 14:52
1

no, the itertools combination is Ω[r (n choose r)] and the loop above it is O(n) so it is slightly better .. ( the complexity of itertools.combinations can be found in this post : https://stackoverflow.com/questions/53419536/what-is-the-computational-complexity-of-itertools-combinations-in-python ) – mrCopiCat Jun 03 '22 at 14:54

I'm trying to solve Three Number Sum in python by using For loop instead of worst time & space complexity I want to use for better understanding

3 Answers3