w3resource

Python Bisect: Find three integers which gives the sum of zero in a given array of integers using Binary Search


Write a Python program to find three integers which give the sum of zero in a given array of integers using Binary Search (bisect).

Sample Solution:

Python Code:

from bisect import bisect, bisect_left
from collections import Counter
class Solution:
    def three_Sum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        triplets = []
        if len(nums) < 3:
            return triplets
        num_freq = Counter(nums)
        nums = sorted(num_freq)  # Sorted unique numbers
        max_num = nums[-1]
        for i, v in enumerate(nums):
            if num_freq[v] >= 2:
                complement =  -2 * v
                if complement in num_freq:
                    if complement != v or num_freq[v] >= 3:
                        triplets.append([v] * 2 + [complement])

            # When all 3 numbers are different.
            if v < 0:  # Only when v is the smallest
                two_sum = -v

                # Lower/upper bound of the smaller of remainingtwo.
                lb = bisect_left(nums, two_sum - max_num, i + 1)
                ub = bisect(nums, two_sum // 2, lb)                       
                for u in nums[lb : ub]:
                    complement = two_sum - u
                    if complement in num_freq and u != complement:
                        triplets.append([v, u, complement])
        return triplets
nums = [-20, 0, 20, 40, -20, -40, 80]
s = Solution()
result = s.three_Sum(nums)
print(result)
nums = [1, 2, 3, 4, 5, -6]
result = s.three_Sum(nums)
print(result)

Sample Output:

[[-40, 0, 40], [-20, -20, 40], [-20, 0, 20]]
[[-6, 1, 5], [-6, 2, 4]]

Flowchart:

Flowchart: Find three integers which gives the sum of zero in a given array of integers using Binary Search.

Python Code Editor:

Contribute your code and comments through Disqus.

Previous: Write a Python program to find the index position of the last occurrence of a given number in a sorted list using Binary Search (bisect).

Next: Write a Python program to find a triplet in an array such that the sum is closest to a given number. Return the sum of the three integers.

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.



Follow us on Facebook and Twitter for latest update.