find_Triplets_with_zero_sum.py

'''
Author : Mohit Kumar
Python program to find triplets in a given  array whose sum is zero
'''
# function to print triplets with 0 sum


def find_Triplets_with_zero_sum(arr, num):

    ''' find triplets in a given  array whose sum is zero

        Parameteres :
            arr : input array
            num = size of input array

        Output :
            if triplets found return their values
            else return "No Triplet Found"

    '''
    # bool variable to check if triplet found or not
    found = False

    # sort array elements
    arr.sort()

    # Run a loop until l is less than r, if the sum of array[l], array[r]
    # is equal to zero then print the triplet and break the loop
    for index in range(0, num - 1):

        # initialize left and right
        left = index + 1
        right = num - 1

        curr = arr[index]  # current element

        while (left < right):

            temp = curr + arr[left] + arr[right]

            if (temp == 0):
                # print elements if it's sum is zero
                print(curr, arr[left], arr[right])

                left += 1
                right -= 1

                found = True

            # If sum of three elements is less  than zero
            # then increment in left
            elif (temp < 0):
                left += 1

            # if sum is greater than zero than decrement in right side
            else:
                right -= 1

    if (found is False):
        print(" No Triplet Found")

# DRIVER CODE STARTS

if __name__ == "__main__":

    n = int(input('Enter size of array\n'))
    print('Enter elements of array\n')

    arr = list(map(int, input().split()))

    print('Triplets with 0 sum are as : ')

    find_Triplets_with_zero_sum(arr, n)

'''
SAMPLE INPUT 1 :
    Enter size of array : 5
    Enter elements of array : 0, -1, 2, -3, 1
OUTPUT :
    Triplets with 0 sum are as :
                    -3 1 2
                    -1 0 1

COMPLEXITY ANALYSIS :

Time Complexity : O(n^2).
    Only two nested loops is required, so the time complexity is O(n^2).

Auxiliary Space : O(1), no extra space is required,
so the time complexity is constant.

'''