This is a directory of algorithm problems in regards of array that I did in AlgoExpert

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))

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

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))

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

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])