- Sorted array.
- Find three number which sum 0.
- https://www.geeksforgeeks.org/find-triplets-array-whose-sum-equal-zero/
Break it down
- sort_array
- Initializeleft_pointer andright_pointer inside for loop,left_pointer keeps increasing andright_pointer keeps decreasing as loop progresses
- Anothernested_loop which runs tillleft_pointer is smaller thanright_pointer
- if the sum of element inleft_pointer ,right_pointer and current element is 0, increase theleft_pointer and decrease theright pointer, print the triplet
- else if the sum of three elements is less than 0, just increase theleft_pointer
- else decrease theright_pointer
- Don’t try to attempt by using Hashmap, there are corner cases that got you stuck.
Code (Different than solution)
def findTriplets(arr, n):
found = False
# sort array elements
arr.sort()
ans = []
for i in range(0, n-1):
# initialize left and right
l = i + 1 # Q. Why will left increase with every loop but not r?
r = n - 1
x = arr[i]
while (l < r):
if (x + arr[l] + arr[r] == 0):
# print elements if it's sum is zero
print(x, arr[l], arr[r])
l += 1
r -= 1
found = True
ans.append([x, arr[l], arr[r]])
while l < r and arr[l] == arr[l-1]: l += 1 # Skip duplicate values for arr[l]
while l < r and arr[r] == arr[r+1]: r -= 1 # Skip duplicate values for arr[r]
# If sum of three elements is less
# than zero then increment in left
elif (x + arr[l] + arr[r] < 0):
l += 1
# if sum is greater than zero then
# decrement in right side
else:
r -= 1
if (found == False):
print(" No Triplet Found")
# Driven source
arr = [0, -1, 2, -3, 1]
n = len(arr)
findTriplets(arr, n)
Approach 1 ❎
'''
problem:
there are two conditions:
- the elements should not be same and the sum of elements should be 0
intuition:
- We can have pointers, three pointers,
- How to solve issue of duplicate triplets?
- is it possible to maintain three pointers?
- lets say there is i, j and k pointers
- should I sort the array, sorting helps with binary search
- map can be used as well with two pointers, that will be much feasible
- Can I sort the array, then complexity will be n log n and then a loop so n, total n log n? Don't think that will work since tc is n^2 for all solution in gfg
- Q. Without sorting how will two pointers work?
- Ans. It won't you have to sort the array first so n log n and then two nested loops
- Q. Is sorting required for hashing approach as well?
- Ans. No.
psuedo code:
another function to check if sum is matching
break it down, optimize later
tc: should be n, no can't be done in less than n^2
'''
class Solution(object):
def checkSum(self, num1, num2, num3, expected_sum = 0):
sum = num1 + num2 + num3
retrun sum == expected_sum
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
num_dict = {}
for num in nums:
if num_dict[num]:
num_dict += 1
else:
num_dict = 1
array_size = len(nums)
left_pointer = 0
right_pointer = array_size
nums.sort()
while left_pointer < array_size:
left_num = nums[left_pointer]
right_num = nums[right_pointer]
Approach 2 ❎
Modified Binary Search will be used here.
'''
#gyan_pelo
have 3 pointers and calculate their sum
Have the array sorted
Left pointer should be increased if the target is smaller than 0 in this case
Right pointer should be increased if the target is greater than 0
At one point only one pointer should be increased
The pointers left and right should be reset when next element is selected
Any #python_trick required here?
'''
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort()
l = 0
r = len(nums)
ans = []
for curr in nums:
l = 0 # reset them
r = len(nums)
while l < r:
sum = nums[l] + nums[r] + curr
if sum == 0:
ans.append([l, r, curr])
if sum < 0:
l++
elif sum > 0:
r++
else:
ans.append([l, r, curr])
return ansApproach 3 (partially works)
class Solution(object):
def threeSum(self, arr):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
found = False
# sort array elements
arr.sort()
n = len(arr)
ans = set()
for i in range(0, n-1):
# initialize left and right
l = i + 1 # Q. Why will left increase with every loop but not r?
r = n - 1
x = arr[i]
while (l < r):
if (x + arr[l] + arr[r] == 0):
# print elements if it's sum is zero
print(x, arr[l], arr[r])
ans.add((arr[i], arr[l], arr[r]))
l += 1
r -= 1
found = True
# If sum of three elements is less
# than zero then increment in left
elif (x + arr[l] + arr[r] < 0):
l += 1
# if sum is greater than zero then
# decrement in right side
else:
r -= 1
if (found == False):
print(" No Triplet Found")
return list(ans)
Approach 4 ✅
- Q. Why is theruntime of this more than other programs?
- Q. Why is thememory_usuage more than other programs? What variables are staying inheap for longest time?
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort()
N, result = len(nums), []
for i in range(N):
if i > 0 and nums[i] == nums[i-1]:
continue
target = nums[i]*-1
s,e = i+1, N-1
while s<e:
if nums[s]+nums[e] == target:
result.append([nums[i], nums[s], nums[e]])
s = s+1
while s<e and nums[s] == nums[s-1]:
s = s+1
elif nums[s] + nums[e] < target:
s = s+1
else:
e = e-1
return resultgyan_pelo
Sort based algorithm
- a+b = -c. 3SUM reduces to 2SUM problem.
Handling Duplicates in 2SUM
- Say index s and e are forming a solution in a sorted array. Now givens nums[s], there is a unique nums[e] such that nums[s]+nums[e]=Target. Therefore, if nums[s+1] is the same as nums[s], then searching in range s+1 to e will give us a duplicate solution. Thus we must move s till nums[s] != nums[s-1] to avoid getting duplicates.
while s<e and nums[s] == nums[s-1]:
s = s+1
Handling Duplicates in 3SUM
- Imagine we are at index i and we have invoked the 2SUM problem from index i+1 to end of the array. Now once the 2SUM terminates, we will have a list of all triplets which include nums[i]. To avoid duplicates, we must skip all nums[i] where nums[i] == nums[i-1].
if i > 0 and nums[i] == nums[i-1]:
continue