#3Sum
#https://leetcode.com/problems/3sum/description/

class Approch1(object):
    def __init__(self, array):
        self.array = array
        #sort the array time O(n log n)
        self.array.sort()

    def twoSum(self, lowPtr, restSum):
        highPtr = len(self.array)-1
        while(lowPtr < highPtr):
            if(self.array[lowPtr]+self.array[highPtr] == restSum):
                return True, self.array[lowPtr], self.array[highPtr]
            if(self.array[lowPtr]+self.array[highPtr] > restSum):
                highPtr = highPtr-1
            else:
                lowPtr = lowPtr+1
        return False, -1, -1

    def solution(self):
        output = []
        for i in range(len(self.array)):
            firstNum = self.array[i]
            restNumSum = 0 - firstNum
            #find rest 2 numbers that add up to restNumSum
            flag, secondNum, thirdNum = self.twoSum(i+1, restNumSum)
            if flag:
                output.append([firstNum, secondNum, thirdNum])
        print output
            
            
                

#Main
o = Approch1([-1, 0, 1, 2, -1, -4])
o.solution()