Arrays Q1: Two Numbers Sum (Not sum = a+b question), Data Structure Problems Series, Part 1 (Python)

Software Development
#1

Arrays Q1: Two Numbers Sum (Not sum=a+b question), Data Structure Problems Series, Part 1 (Python)

Problem Statement:

Write a function that takes in a non-empty array of distinct integers and an
integer representing a target sum. If any two numbers in the input array sum
up to the target sum, the function should return them in an array, in any
order. If no two numbers sum up to the target sum, the function should return
an empty array.


Note that the target sum has to be obtained by summing two different integers
in the array; you can't add a single integer to itself in order to obtain the
target sum.

You can assume that there will be at most one pair of numbers summing up to
the target sum.

Sample Input
    array = [3, 5, -4, 8, 11, 1, -1, 6]
    targetSum = 10

Sample Output:
    [-1, 11] // the numbers could be in reverse order

Try solving it

Hints are in the first reply

Solutions will be posted in 12 hours

Arrays Q2: Validate Subsequence, Data Structure Problems Series, Part 1 (Python)
#3

Here are the two hints to solve the above problem:

Note: See hints only if you are unable to solve the problem at least twice. Be astute.

Hint 1:

Try using two for loops to sum all possible pairs of numbers in the input array.
What are the time and space implications of this approach?

Hint 2:

Realize that for every number X in the input array, you are essentially trying to
find a corresponding number Y such that X + Y = targetSum. With two variables in
this equation known to you, it shouldn’t be hard to solve for Y.

Optimal Time and Space Complexity:

O(n) time complexity| O(n) space complexity - where n is the length of the input array

Solutions will be posted in 12 hours of posting the above question.

#4
#5
#6
#7

@Author: Anish Arya

Date 2nd July, 2022

#2 approaches used

def twoNumbersSum(array, targetSum):

    # Approach 1: using HashTable
    # TC = O(n) 
    # SC = O(n)
    # Note: Approach 2 code is post this method

    visited = {} # Dictionary for O(1) time access

    for val in array: # O(n)
        diff = targetSum - val
        if visited.get(diff): # if difference is in visited then match found
            return [val, diff]
        visited.update({val: True}) # else, add a new entry into visited 
    # if no pair is found then return empty array
    return []

Approach 2

TC = O(nlogn)

SC = O(1)

def twoNumbersSum2(array, targetSum):
    array.sort()
    left  = 0 # Initialized to lowest value idx
    right = len(array) - 1 # Initialized to highest value idx
    
    while left < right: # worst case only one element remains i.e. left = right
        left_val, right_val = array[left], array[right]
        currentSum =  left_val + right_val
        if currentSum == targetSum:
            return [left_val, right_val]
        elif currentSum < targetSum:
            left  += 1
        else:
            right -= 1
    return []
#8

UnitTest.py

import TwoNumbersSum as program
import unittest

class TestTwoNumbersSum(unittest.TestCase):
    
    def test_case_1(self):
        output = program.twoNumbersSum([3, 5, -4, 8, 11, 1, -1, 6], 10)
        self.assertTrue(len(output) == 2)
        self.assertTrue(11 in output)
        self.assertTrue(-1 in output)

    def test_case_2(self):
        output = program.twoNumbersSum([3, 5, -4, 8, 11, 1, -1, 6], 20)
        self.assertTrue(len(output) == 0)

    def test_case_3(self):
        output = program.twoNumbersSum2([3, 5, -4, 8, 11, 1, -1, 6], -5)
        self.assertTrue(len(output) == 2)
        self.assertTrue(-4 in output)
        self.assertTrue(-1 in output)

if __name__ == '__main__':
	unittest.main()