A binary search solution to 3SumFinding unique triplets adding up to 03Sum implementationCount of Smaller Numbers After Self3sum leetcode problem using 2sum3-Sum Problem in PythonSolving “Quadruple sum” problem using dynamic programmingFind all combinations of 4 elements whose sum equals a target in PythonClosest 3Sum in ScalaLeetcode Three Sum in PythonHash table solution to twoSum

Why do compilers behave differently when static_cast(ing) a function to void*?

Approximating irrational number to rational number

Freedom of speech and where it applies

How do I color the graph in datavisualization?

Removing files under particular conditions (number of files, file age)

Pre-mixing cryogenic fuels and using only one fuel tank

How can we generalize the fact of finite dimensional vector space to an infinte dimensional case?

What prevents the use of a multi-segment ILS for non-straight approaches?

It grows, but water kills it

Can someone explain how this makes sense electrically?

What should you do if you miss a job interview (deliberately)?

How should I respond when I lied about my education and the company finds out through background check?

Why did the EU agree to delay the Brexit deadline?

How to implement a feedback to keep the DC gain at zero for this conceptual passive filter?

Loading commands from file

Multiplicative persistence

Fear of getting stuck on one programming language / technology that is not used in my country

Can I sign legal documents with a smiley face?

250 Floor Tower

Creature in Shazam mid-credits scene?

Create all possible words using a set or letters

Why electric field inside a cavity of a non-conducting sphere not zero?

Does a 'pending' US visa application constitute a denial?

The screen of my macbook suddenly broken down how can I do to recover



A binary search solution to 3Sum


Finding unique triplets adding up to 03Sum implementationCount of Smaller Numbers After Self3sum leetcode problem using 2sum3-Sum Problem in PythonSolving “Quadruple sum” problem using dynamic programmingFind all combinations of 4 elements whose sum equals a target in PythonClosest 3Sum in ScalaLeetcode Three Sum in PythonHash table solution to twoSum













3












$begingroup$


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.



Note:



The solution set must not contain duplicate triplets.



Example:



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^2logn)$.



 class Solution:
"""
Solve the problem by three module funtion
threeSum
two_sum
bi_search
"""
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
else:
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?










share|improve this question









New contributor




Alice is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$











  • $begingroup$
    Binary search is good at O(log n), but hash search is better at O(1).
    $endgroup$
    – Lawnmower Man
    yesterday















3












$begingroup$


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.



Note:



The solution set must not contain duplicate triplets.



Example:



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^2logn)$.



 class Solution:
"""
Solve the problem by three module funtion
threeSum
two_sum
bi_search
"""
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
else:
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?










share|improve this question









New contributor




Alice is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$











  • $begingroup$
    Binary search is good at O(log n), but hash search is better at O(1).
    $endgroup$
    – Lawnmower Man
    yesterday













3












3








3





$begingroup$


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.



Note:



The solution set must not contain duplicate triplets.



Example:



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^2logn)$.



 class Solution:
"""
Solve the problem by three module funtion
threeSum
two_sum
bi_search
"""
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
else:
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?










share|improve this question









New contributor




Alice is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$




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.



Note:



The solution set must not contain duplicate triplets.



Example:



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^2logn)$.



 class Solution:
"""
Solve the problem by three module funtion
threeSum
two_sum
bi_search
"""
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
else:
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?







python python-3.x programming-challenge time-limit-exceeded k-sum






share|improve this question









New contributor




Alice is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.











share|improve this question









New contributor




Alice is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









share|improve this question




share|improve this question








edited yesterday









esote

2,83111038




2,83111038






New contributor




Alice is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









asked yesterday









AliceAlice

1774




1774




New contributor




Alice is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.





New contributor





Alice is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






Alice is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.











  • $begingroup$
    Binary search is good at O(log n), but hash search is better at O(1).
    $endgroup$
    – Lawnmower Man
    yesterday
















  • $begingroup$
    Binary search is good at O(log n), but hash search is better at O(1).
    $endgroup$
    – Lawnmower Man
    yesterday















$begingroup$
Binary search is good at O(log n), but hash search is better at O(1).
$endgroup$
– Lawnmower Man
yesterday




$begingroup$
Binary search is good at O(log n), but hash search is better at O(1).
$endgroup$
– Lawnmower Man
yesterday










1 Answer
1






active

oldest

votes


















7












$begingroup$

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.






share|improve this answer









$endgroup$












    Your Answer





    StackExchange.ifUsing("editor", function ()
    return StackExchange.using("mathjaxEditing", function ()
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
    );
    );
    , "mathjax-editing");

    StackExchange.ifUsing("editor", function ()
    StackExchange.using("externalEditor", function ()
    StackExchange.using("snippets", function ()
    StackExchange.snippets.init();
    );
    );
    , "code-snippets");

    StackExchange.ready(function()
    var channelOptions =
    tags: "".split(" "),
    id: "196"
    ;
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function()
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled)
    StackExchange.using("snippets", function()
    createEditor();
    );

    else
    createEditor();

    );

    function createEditor()
    StackExchange.prepareEditor(
    heartbeatType: 'answer',
    autoActivateHeartbeat: false,
    convertImagesToLinks: false,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: null,
    bindNavPrevention: true,
    postfix: "",
    imageUploader:
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    ,
    onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    );



    );






    Alice is a new contributor. Be nice, and check out our Code of Conduct.









    draft saved

    draft discarded


















    StackExchange.ready(
    function ()
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f215994%2fa-binary-search-solution-to-3sum%23new-answer', 'question_page');

    );

    Post as a guest















    Required, but never shown

























    1 Answer
    1






    active

    oldest

    votes








    1 Answer
    1






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    7












    $begingroup$

    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.






    share|improve this answer









    $endgroup$

















      7












      $begingroup$

      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.






      share|improve this answer









      $endgroup$















        7












        7








        7





        $begingroup$

        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.






        share|improve this answer









        $endgroup$



        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.







        share|improve this answer












        share|improve this answer



        share|improve this answer










        answered yesterday









        AJNeufeldAJNeufeld

        6,4001621




        6,4001621




















            Alice is a new contributor. Be nice, and check out our Code of Conduct.









            draft saved

            draft discarded


















            Alice is a new contributor. Be nice, and check out our Code of Conduct.












            Alice is a new contributor. Be nice, and check out our Code of Conduct.











            Alice is a new contributor. Be nice, and check out our Code of Conduct.














            Thanks for contributing an answer to Code Review Stack Exchange!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid


            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.

            Use MathJax to format equations. MathJax reference.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function ()
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f215994%2fa-binary-search-solution-to-3sum%23new-answer', 'question_page');

            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            Popular posts from this blog

            getting Checkpoint VPN SSL Network Extender working in the command lineHow to connect to CheckPoint VPN on Ubuntu 18.04LTS?Will the Linux ( red-hat ) Open VPNC Client connect to checkpoint or nortel VPN gateways?VPN client for linux machine + support checkpoint gatewayVPN SSL Network Extender in FirefoxLinux Checkpoint SNX tool configuration issuesCheck Point - Connect under Linux - snx + OTPSNX VPN Ububuntu 18.XXUsing Checkpoint VPN SSL Network Extender CLI with certificateVPN with network manager (nm-applet) is not workingWill the Linux ( red-hat ) Open VPNC Client connect to checkpoint or nortel VPN gateways?VPN client for linux machine + support checkpoint gatewayImport VPN config files to NetworkManager from command lineTrouble connecting to VPN using network-manager, while command line worksStart a VPN connection with PPTP protocol on command linestarting a docker service daemon breaks the vpn networkCan't connect to vpn with Network-managerVPN SSL Network Extender in FirefoxUsing Checkpoint VPN SSL Network Extender CLI with certificate

            Cannot Extend partition with GParted The 2019 Stack Overflow Developer Survey Results Are In Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern) 2019 Community Moderator Election ResultsCan't increase partition size with GParted?GParted doesn't recognize the unallocated space after my current partitionWhat is the best way to add unallocated space located before to Ubuntu 12.04 partition with GParted live?I can't figure out how to extend my Arch home partition into free spaceGparted Linux Mint 18.1 issueTrying to extend but swap partition is showing as Unknown in Gparted, shows proper from fdiskRearrange partitions in gparted to extend a partitionUnable to extend partition even though unallocated space is next to it using GPartedAllocate free space to root partitiongparted: how to merge unallocated space with a partition

            Marilyn Monroe Ny fiainany manokana | Jereo koa | Meny fitetezanafanitarana azy.