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
$begingroup$
I tried a binary solution to 3Sum problem in LeetCode:
Given an array
nums
of $n$ integers, are there elements $a$, $b$, $c$ innums
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
- an iteration
- and a
two_Sum
problem. - break
two_Sum
problem to- a loop
- 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
New contributor
$endgroup$
add a comment |
$begingroup$
I tried a binary solution to 3Sum problem in LeetCode:
Given an array
nums
of $n$ integers, are there elements $a$, $b$, $c$ innums
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
- an iteration
- and a
two_Sum
problem. - break
two_Sum
problem to- a loop
- 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
New contributor
$endgroup$
$begingroup$
Binary search is good at O(log n), but hash search is better at O(1).
$endgroup$
– Lawnmower Man
yesterday
add a comment |
$begingroup$
I tried a binary solution to 3Sum problem in LeetCode:
Given an array
nums
of $n$ integers, are there elements $a$, $b$, $c$ innums
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
- an iteration
- and a
two_Sum
problem. - break
two_Sum
problem to- a loop
- 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
New contributor
$endgroup$
I tried a binary solution to 3Sum problem in LeetCode:
Given an array
nums
of $n$ integers, are there elements $a$, $b$, $c$ innums
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
- an iteration
- and a
two_Sum
problem. - break
two_Sum
problem to- a loop
- 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
python python-3.x programming-challenge time-limit-exceeded k-sum
New contributor
New contributor
edited yesterday
esote
2,83111038
2,83111038
New contributor
asked yesterday
AliceAlice
1774
1774
New contributor
New contributor
$begingroup$
Binary search is good at O(log n), but hash search is better at O(1).
$endgroup$
– Lawnmower Man
yesterday
add a comment |
$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
add a comment |
1 Answer
1
active
oldest
votes
$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
.
$endgroup$
add a comment |
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.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
$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
.
$endgroup$
add a comment |
$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
.
$endgroup$
add a comment |
$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
.
$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
.
answered yesterday
AJNeufeldAJNeufeld
6,4001621
6,4001621
add a comment |
add a comment |
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.
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.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
$begingroup$
Binary search is good at O(log n), but hash search is better at O(1).
$endgroup$
– Lawnmower Man
yesterday