I tried a binary solution to 3Sum problem in LeetCode:

Given an array nums of \$n\$ integers, are there elements \$a\$, \$b\$, \$c\$ in nums such that \$a + b + c = 0\$? Find all unique triplets in the array which gives the sum of zero.


The solution set must not contain duplicate triplets.


Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
  [-1, 0, 1],
  [-1, -1, 2]

My plan: divide and conquer threeSum to

  1. an iteration
  2. and a two_Sum problem.
  3. break two_Sum problem to
    1. a loop
    2. binary search

The complexity is: \$O(n^2\log{n})\$.

 class Solution:
    Solve the problem by three module funtion
    def __init__(self):
        self.triplets: List[List[int]] = []

    def threeSum(self, nums, target=0) -> List[List[int]]:
        :type nums: List[int]
        :type target: int 
        nums.sort() #sort for skip duplicate and binary search 

        if len(nums) < 3:
            return []

        i = 0
        while i < len(nums) - 2:
            complement = target - nums[i]

            self.two_sum(nums[i+1:], complement)
            i += 1 #increment the index 
            while i < len(nums) -2 and nums[i] == nums[i-1]: #skip the duplicates, pass unique complement to next level.
                i += 1 

        return self.triplets

    def two_sum(self, nums, target):
        :type nums: List[int]
        :tppe target: int
        :rtype: List[List[int]]
        # nums = sorted(nums) #temporarily for testing.
        if len(nums) < 2:
            return [] 

        i = 0
        while i < len(nums) -1:
            complement = target - nums[i]

            if self.bi_search(nums[i+1:], complement) != None:

                # 0 - target = threeSum's fixer 
                self.triplets.append([0-target, nums[i], complement]) 
            i += 1

            while i < len(nums) and nums[i] == nums[i-1]:
                i += 1 

    def bi_search(self, L, find) -> int:
        :type L: List[int]
        :type find: int 
        if len(L) < 1: #terninating case 
            return None 
            mid = len(L) // 2
            if find == L[mid]:
                return find 

            if find > L[mid]:
                upper_half = L[mid+1:]
                return self.bi_search(upper_half, find)
            if find < L[mid]:
                lower_half = L[:mid] #mid not mid-1
                return self.bi_search(lower_half, find)

I ran it but get the report

Status: Time Limit Exceeded

Could you please give any hints to refactor?

Is binary search is an appropriate strategy?

  • \$\begingroup\$ Binary search is good at O(log n), but hash search is better at O(1). \$\endgroup\$ Commented Mar 23, 2019 at 0:40

1 Answer 1


Your bi_search() method is recursive. It doesn’t have to be. Python does not do tail-call-optimization: it won’t automatically turn the recursion into a loop. Instead of if len(L) < 1:, use a while len(L) > 0: loop, and assign to (eg, L = L[:mid]) instead of doing a recursive call.

Better: don’t modify L at all, which involves copying a list of many numbers multiple times, a time consuming operation. Instead, maintain a lo and hi index, and just update the indexes as you search.

Even better: use a built in binary search from import bisect.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.