2dpointers.py

# containerMostWater
def containerMostWater(arr):
    # O(N) runtime
    # O(1) space
    start = 0 
    end = len(arr)-1
    maxDist = 0
    if (len(arr) < 2):
        return -1
    while start < end:
        curr = min(arr[start], arr[end]) * (end - start)
        maxDist = max(curr, maxDist)
        if (arr[start] > arr[end]):
            end -= 1
        else:
            start += 1
    # brute force T : O(N^2) O(1) space
    # max = height (min of 2 pointers) * distance
    # for i in range (0, len(arr)):
    #     for j in range(len(arr)-1, 0, -1):
    #         curr = min(arr[i], arr[j]) * (j - i)
    #         maxDist = max(curr, maxDist)
            
    print(maxDist)    
arr = [1,8,6,2,5,4,8,3,7]
containerMostWater(arr)
# removeDuplicates
def removeDuplicates(nums):
    # Given a sorted array and we need to return the length 
    # of the unique elements instead of the entire array. 
    # There is no need to delete the duplicate elements also.
    # Since, our first element is already present at index 0 (it is a unique element), 
    # we quickly run a for loop for the entire array to scan for unique elements.
    # If the current element and the next element are the same, then we just keep on going till 
    # we find a different element
    # Once we find a different element, it is inserted at index 1, because, index 
    # 0 is taken by the first unique element.
    # Once this is done, the same scanning is done to find out the next unique element 
    # and this element is to be inserted at index 2. This process continues until we are done 
    # with unique elements.
    # We use a variable (x = 1) which is incremented to the next index whenever 
    # we find a unique element and we insert this element at its corresponding index.
    i = 1
    j = 1
    
    while j < len(nums):
        if nums[i-1] != nums[j]:
            nums[i] = nums[j]
            i += 1
        j += 1
    print(i)
    
    # brute force
    # while i < len(nums)-1:
    #     if (nums[i] == nums[i+1]):
    #         del nums[i]
    #         i -= 1
    #     i = i + 1
    # print(len(nums))       
    
nums = [0,0,1,1,1,2,2,3,3,4]
removeDuplicates(nums)
# Two Numbers Sum
def twoNumberSum(array, target):
    # O(N) Time | O(N) Space = N length of array
    array = sorted(array)
    i = 0
    j = len(array) - 1
    if len(array) < 2:
        return []
    while (i  < j):
        if array[i] + array [j] == target:
            return ([array[i], array [j]])
        elif array[i] + array [j] > target:
            j -= 1
        else:
            i += 1
    return []
    
array = [3,5,-4,8,11,1,-1,6]
target = 10
print(twoNumberSum(array, target))

# Three Number Sum
def threeNumberSum(array, target):
    # O(N^2) Time | O(N) Space = N length of array
    array = sorted(array)
    result = []
    if len(array) < 3:
        return []
    for i in range (0, len(array)-2): 
        # dont overlap with k so (0, len(array) -2 ) instead (0, len(array))
        j = i +1 # need to update j along with i
        k = len(array) - 1
        while j < k:
            if array[i] + array[j] + array[k] == target:
                result.append([array[i] , array[j] , array[k]])
                k -= 1
            elif array[i] + array[j] + array[k] > target:
                k -= 1
            else:
                j += 1
    return result

arr = [12,3,1,2,-6,5,-8,6]
targetSum = 0
print(threeNumberSum(arr, targetSum))

# Smallest Difference
def smallestDifference(arrayOne, arrayTwo):
    arrayOne = sorted(arrayOne)
    arrayTwo = sorted(arrayTwo)
    i = 0
    j = 0
    small = float("inf")
    curr = float("inf")
    smallest = []
    while i < len(arrayOne) and j < len(arrayTwo):
        first = arrayOne[i]
        second = arrayTwo[j]
        if first > second:
            curr = first - second
            i += 1
        elif second > first:
            curr = second - first
            j += 1
        else:
            return [first, second]
        if small > curr:
            small = curr
            smallest = [first, second]
    return smallest

arrayOne = [-1, 3, 5, 10, 20 ,28]
arrayTwo = [15, 17, 26, 134, 135]
print(smallestDifference(arrayOne, arrayTwo))