Skip to content

Instantly share code, notes, and snippets.

@jcdiv47

jcdiv47/Array_FourSum.py

Created January 7, 2020 01:25
Show Gist options
  • Save jcdiv47/bf80c1002a0b2ed8438ce5a7c6deabb4 to your computer and use it in GitHub Desktop.
Save jcdiv47/bf80c1002a0b2ed8438ce5a7c6deabb4 to your computer and use it in GitHub Desktop.
Download ZIP
This is a directory of algorithm problems in regards of array that I did in AlgoExpert
Raw
Array_FourSum.py
#!/usr/bin/env python3
# Write a function that takes in a non-empty array of distinct integers and an integer representing a target sum.
# The function should find all quadruplets in the array that sum up to the target sum and return a two-dimensional
# array of all these quadruplets in no particular order. If no four numbers sum up to the target sum, the function
# should return an empty array.
# Sample input: [7, 6, 4, -1, 1, 2], 16
# Sample output: [[7, 6, 4, -1], [7, 6, 1, 2]]
def four_number_sum(array, target_sum):
four_num_sum_list = [] # store all outcomes
two_num_sum_dict = {} # keys: difference to two-num sum, values: set of corr. indexes
for i in range(len(array)):
for j in range(i + 1, len(array)):
cur_two_sum = array[i] + array[j]
potential_two_sum = target_sum - cur_two_sum
two_num_sum_dict[cur_two_sum] = {i, j}
if potential_two_sum in two_num_sum_dict.keys():
if {i, j}.intersection(two_num_sum_dict[potential_two_sum]) == set([]):
idx_list = [i, j] + list(two_num_sum_dict[potential_two_sum])
four_num_sum_list.append(array_item(array, idx_list))
return remove_duplicate(four_num_sum_list)
def array_item(array, idx_list):
"""
Return parts of the array with designated indexes
:param array: array
:param idx_list: list of indexes
:return:
"""
return [array[i] for i in idx_list]
def remove_duplicate(array):
"""
Remove duplicate lists elements
:param array: a two dimensional array with elements as lists
:return: modified array without duplicate list element
"""
for i in range(len(array)):
for j in range(i + 1, len(array)):
if set(array[i]) == set(array[j]):
array[j] = []
return [item for item in array if item != []]
# # Copyright © 2020 AlgoExpert, LLC. All rights reserved.
#
# # Average: O(n^2) time | O(n^2) space
# # Worst: O(n^3) time | O(n^2) space
# def fourNumberSum(array, targetSum):
# allPairSums = {}
# quadruplets = []
# for i in range(1, len(array) - 1):
# for j in range(i + 1, len(array)):
# currentSum = array[i] + array[j]
# difference = targetSum - currentSum
# if difference in allPairSums:
# for pair in allPairSums[difference]:
# quadruplets.append(pair + [array[i], array[j]])
# for k in range(0, i):
# currentSum = array[i] + array[k]
# if currentSum not in allPairSums:
# allPairSums[currentSum] = [[array[k], array[i]]]
# else:
# allPairSums[currentSum].append([array[k], array[i]])
# return quadruplets
if __name__ == "__main__":
a1 = [7, 6, 4, -1, 1, 2]
s1 = 16
print(four_number_sum(a1, s1))
Raw
Array_MoveElementToEnd.py
#!/usr/bin/env python3
# Given an array and an integer. Write a function that moves all instances of that integer to the end of the array.
# This function should perform in place and does not need to maintain the order of the other integers.
# def move_element_to_end(array, to_move):
# """
# :param array:
# :param to_move:
# :return:
# """
# n = len(array)
# while n > 1:
# new_n = 0
# for i in range(1, n):
# if array[i - 1] == to_move:
# array[i - 1], array[i] = array[i], array[i - 1]
# new_n = i
# n = new_n
# return array
def move_element_to_end(array, to_move):
left = 0
right = len(array) - 1
while left < right:
while left < right and array[right] == to_move:
right -= 1
if array[left] == to_move:
array[left], array[right] = array[right], array[left]
left += 1
return array
Raw
Array_SmallestDifference.py
#!/usr/bin/env python3
# Write a function that takes in two non-empty arrays of integers.
# The function should find the pair of numbers (one from the first array, one from the second array)
# whose absolute difference is closest to zero. The function should return an array containing these two numbers,
# with the number from the first array in the first position. Assume that there will only be one pair of numbers
# with the smallest difference.
# O(n*log(n)+m*log(m)) time | O(1) space
def smallest_difference(array_one, array_two):
array_one.sort()
array_two.sort()
pointer1 = 0
pointer2 = 0
smallest_diff = float("inf")
cur_diff = float("inf")
result = []
while pointer1 < len(array_one) and pointer2 < len(array_two):
first_num = array_one[pointer1]
second_num = array_two[pointer2]
if first_num < second_num:
cur_diff = second_num - first_num
pointer1 += 1
elif second_num < first_num:
cur_diff = first_num - second_num
pointer2 += 1
else:
return [first_num, second_num]
if cur_diff < smallest_diff:
smallest_diff = cur_diff
result = [first_num, second_num]
return result
if __name__ == "__main__":
a1 = [-1, 5, 10, 20, 3]
a2 = [26, 134, 135, 15, 17]
print(smallest_difference(a1, a2))
Raw
Array_threeSum.py
#!/usr/bin/env python3
# Write a function that takes in a non-empty array of distinct integers and an integer representing a target sum.
# The function should find all triplets in the array that sum up to the target sum and return a two-dimensional array
# of all these triplets. The numbers in each triplet should be ordered in ascending order, and the triplets themselves
# should be ordered in ascending order with respect to the numbers they hold. If no three numbers sum up to the
# target sum, the function should return an empty array.
# O(n^2) time | O(n) space
def three_sum(arr, target_sum):
three_sum_list = []
arr.sort() # sort the array
for i in range(len(arr) - 2):
left = i + 1 # left pointer on the number immediately to the right of the current number
right = len(arr) - 1 # right pointer starting on the right most number of the array
while left < right:
cur_sum = arr[i] + arr[left] + arr[right]
if cur_sum == target_sum:
three_sum_list.append(arr[i], arr[left], arr[right])
left += 1
right += 1
elif cur_sum < target_sum:
left += 1 # current sum is too small
else:
right += 1 # current sum is too large
return three_sum_list
Raw
Array_TwoSum.py
#!/usr/bin/env python3
# Write a function that takes a non-empty array of distinct integers
# and an integer representing a target sum.
# If any two numbers in the array sum up to the target sum, return these two numbers as an array
# Else return an empty array
# # O(n^2) time | O(1) space
# def two_sum(arr, target_sum):
# for i in range(len(arr) - 1):
# for j in range(i + 1, len(arr)):
# if arr[i] + arr[j] == target_sum:
# return [arr[i], arr[j]]
# return []
# # O(n) time | O(n) space
# def two_sum(arr, target_sum):
# diff = {}
# for num in arr:
# if num not in diff.keys():
# diff[target_sum - num] = num
# else:
# return [num, diff[num]]
# return []
# O(nlog(n)) time | O(1) space
def two_sum(arr, target_sum):
arr.sort()
head = 0
tail = len(arr) - 1
while head < tail:
temp_sum = arr[head] + arr[tail]
if temp_sum == target_sum:
return [arr[head], arr[tail]]
elif temp_sum < target_sum:
head += 1
else:
tail -= 1
return []
if __name__ == "__main__":
print(two_sum([-7, -5, -3, -1, 0, 1, 3, 5, 7], -5))
print([-5, 0])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment