Array_implimentations.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Array implimentations for coders"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[-2, -20, 10]"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Find subarray with given sum with O(n) \n",
    "# Ex: [-10, 0, 2, -2, -20, 10] find the sub-array with a sum = -12, (recursion would be O(n!))\n",
    "\n",
    "def sub_array_sum(flow_arr, target):\n",
    "    s = [] \n",
    "    sum_of_items = 0\n",
    "    n = len(flow_arr) \n",
    "    for i in range(n): \n",
    "        sum_of_items += flow_arr[i] \n",
    "        s.append(sum_of_items) \n",
    "        if sum_of_items == target:\n",
    "            return flow_arr[:i+1]\n",
    "\n",
    "    for each_sum in range(len(s)):\n",
    "        item = s[each_sum]\n",
    "        if item-target in s:\n",
    "            mark_the_last_index = s.index(item) # last seen repetition's index is marked \n",
    "            mark_the_first_index = s.index(item-target)\n",
    "        \n",
    "            # print(s, mark_the_first_index, mark_the_last_index) # to view the indices if needed\n",
    "            return flow_arr[mark_the_first_index+1: mark_the_last_index+1]   \n",
    "    \n",
    "    return None\n",
    "    \n",
    "test = [-9, 0, 2, -2, -20, 10] \n",
    "\n",
    "sub_array_sum(test, -12)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4, 2, -5, -1]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Find zero sum sub-array \n",
    "# If sum of all items list have two numbers repeating each other, it means there is a zero sum sub array in between \n",
    "# the repeating numbers\n",
    "\n",
    "def find_zero_sum_subarray(flow_arr):\n",
    "    \n",
    "    s = [] \n",
    "    sum_of_items = 0\n",
    "    n = len(flow_arr) \n",
    "    for i in range(n): \n",
    "        sum_of_items += flow_arr[i] \n",
    "        s.append(sum_of_items) \n",
    "        if sum_of_items == 0:\n",
    "            return flow_arr[:i+1]\n",
    "\n",
    "    # if nothing summed up to 0 but all items are summed to some several other values, \n",
    "    # add all items in a dictionary to see if there are any double values\n",
    "    a_dict = {}\n",
    "    for each_sum in range(len(s)):\n",
    "        item = s[each_sum]\n",
    "        if item in a_dict:\n",
    "            a_dict[item] += 1\n",
    "            mark_the_index = each_sum # last seen repetition's index is marked \n",
    "        else:\n",
    "            a_dict[item] = 1\n",
    "    print(s, a_dict) # to view the duplicates if needed\n",
    "   \n",
    "    # mark the values of the dictinary if there are two items that has the same sum value\n",
    "    for k in a_dict.keys():\n",
    "        v = a_dict[k]\n",
    "        if v > 1: # if the item is seen more than once \n",
    "            start_index = s.index(mark_the_index) # python built-in method only shows the first index that item is seen\n",
    "            end_index = mark_the_index \n",
    "            # start index is not included but mark index is included since sub-array summing 0 starts after \n",
    "            return flow_arr[start_index+1 : mark_the_index+1] # sum array : [4, 6, 3, 4, 10] \n",
    "    \n",
    "    return None\n",
    "\n",
    "test_2 = [4, 2, -5, -1, 6, -2]\n",
    "\n",
    "find_zero_sum_subarray(test_2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(9, 3, 6)"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Find Triplets Algorithm O(N^2)\n",
    "# Find if sum of two elements in an array is equal to one of the elements in the same array\n",
    "\n",
    "def find_triplets(arr): \n",
    "    n = len(arr)\n",
    "    # sort the array \n",
    "    arr.sort() \n",
    "    # start from both sides of a sorted array and see if the sum is matching the largest item\n",
    "    # continue to look for the latter largest elements percolating from the end index to the start index\n",
    "    i = n - 1\n",
    "    while(i >= 0): \n",
    "        j = 0\n",
    "        k = i-1\n",
    "        while (j < k): \n",
    "            if (arr[i] == arr[j] + arr[k]): \n",
    "                return arr[i], arr[j], arr[k] \n",
    "            elif (arr[i] > arr[j] + arr[k]): \n",
    "                j += 1\n",
    "            elif (arr[i] < arr[j] + arr[k]): \n",
    "                k -= 1\n",
    "        i -= 1\n",
    "          \n",
    "    return None\n",
    "\n",
    "arr = [2, 6, -1, 9, 4, 3] \n",
    "find_triplets(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "13"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Answer to the \"max sub-array sum problem\" that is widely available at several online sources\n",
    "\n",
    "def maxSubArraySum(a): \n",
    "    n = len(a)\n",
    "    max_so_far = a[0] \n",
    "    curr_max = a[0] \n",
    "    for i in range(1,n): \n",
    "        curr_max = max(a[i], curr_max + a[i]) \n",
    "        max_so_far = max(max_so_far, curr_max) \n",
    "          \n",
    "    return max_so_far \n",
    "  \n",
    "a = [-2, -3, 4, -1, 6 -2, 1, 5, -3, 1] \n",
    "maxSubArraySum(a) \n",
    " \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4, -1, 4, 1, 5]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Max sub-array sum problem extracting the items from the array \n",
    "# Print the MOST PROFITABLE subarray, just a more comprehensive solution than the one above \n",
    "\n",
    "import numpy as np\n",
    "def maxSubArraySum(a): \n",
    "    sum_of_items = []\n",
    "    sum = 0\n",
    "    for i in range(len(a)): \n",
    "        sum += a[i]\n",
    "        sum_of_items.append(sum)\n",
    "    max_item = max(sum_of_items)\n",
    "    max_at_ind = sum_of_items.index(max_item)\n",
    "    # print(a, sum_of_items, max_item, max_at_ind) # to view\n",
    "    \n",
    "    # start from the max item and go backwards by summing up the total\n",
    "    # find the second largest number until the max_at_ind\n",
    "    sum_of_items2 = [] \n",
    "    total = 0\n",
    "    max_sum = 0\n",
    "    for j in reversed(range(0, max_at_ind)):\n",
    "        item = a[j]\n",
    "        total += item\n",
    "        sum_of_items2.append(total)\n",
    "        if max_sum < total:\n",
    "            max_sum = total\n",
    "            # count how many steps taken to reach the maximum \n",
    "            diff = max_at_ind - j\n",
    "    \n",
    "    # print('sum of items', sum_of_items2, diff) # to view the second sum intes\n",
    "    return a[max_at_ind - diff: max_at_ind+1]\n",
    "   \n",
    "    \n",
    "a = [-2, -3, 4, -1, 6 -2, 1, 5, -3, 1] \n",
    "maxSubArraySum(a) \n",
    " \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3.0"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Get the missing number of an arithmetic sequence starting from 1.\n",
    "# Formula: sum of numbers is total = n*(n+1)/2\n",
    "# Subtract all the numbers from sum and you will get the missing number\n",
    "\n",
    "def find_missing_numb_of_arithmetic_series(a): \n",
    "    n = len(a) \n",
    "    total = (n + 1)*(n + 2)/2\n",
    "    sum_of_A = sum(a) \n",
    "    return total - sum_of_A \n",
    "  \n",
    "\n",
    "test = [1, 2, 4, 5, 6] \n",
    "find_missing_numb_of_arithmetic_series(test)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[-2, 0, 1, 2, 3, 6, 6, 13]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# merge unsorted arrays and merge sorted arrays\n",
    "\n",
    "def split(n):\n",
    "    if len(n) <= 1: return n\n",
    "    mid = len(n)//2\n",
    "    left = n[:mid]\n",
    "    right = n[mid:]\n",
    "    return left, right\n",
    "\n",
    "\n",
    "def merge_sorted_two_arrays(a, b):\n",
    "    if len(a) == 0: return b\n",
    "    if len(b) == 0: return a\n",
    "    i = 0\n",
    "    j = 0\n",
    "    list_of_merged = []\n",
    "    while i < len(a) and j < len(b):\n",
    "        if a[i] < b[j]:\n",
    "            list_of_merged.append(a[i])\n",
    "            i += 1\n",
    "        elif a[i] > b[j]:\n",
    "            list_of_merged.append(b[j])\n",
    "            j += 1\n",
    "        else: # if a[i] == b[j]\n",
    "            list_of_merged.append(a[i])\n",
    "            list_of_merged.append(b[j])\n",
    "            i += 1\n",
    "            j += 1\n",
    "        if i == len(a):\n",
    "            for k in range(j, len(b)):\n",
    "                list_of_merged.append(b[j])\n",
    "        if j == len(b):\n",
    "            for k in range(i, len(a)):\n",
    "                list_of_merged.append(a[i])\n",
    "    return list_of_merged\n",
    "\n",
    "\n",
    "def merge_sort(n):\n",
    "    if len(n) <= 1: return n\n",
    "    left, right = split(n)\n",
    "    left_splits = merge_sort(left)\n",
    "    right_splits = merge_sort(right)\n",
    "    combine_splits = merge_sorted_two_arrays(left_splits, right_splits)\n",
    "    return combine_splits\n",
    "    \n",
    "test_array = [2,3,6,6,1,-2,13,0]\n",
    "    \n",
    "merge_sort(test_array)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7 0\n",
      "6 1\n",
      "5 2\n",
      "4 3\n",
      "3 4\n",
      "[13, -2, 6, 0, 6, 1, 3, 2]\n"
     ]
    }
   ],
   "source": [
    "# Rearrange an array alternatively in a way that the max, min, secondmax, secondmin.... all elements are reordered\n",
    "\n",
    "test_array = [2,3,6,6,1,-2,13,0]\n",
    "sorted_array = np.sort(test_array)\n",
    "rearranged_array = []\n",
    "assert(len(sorted_array) > 1)\n",
    "for i in range(len(sorted_array)):\n",
    "    high_index = len(sorted_array)-1-i\n",
    "    low_index = i\n",
    "    print(high_index, low_index)\n",
    "    if high_index <= low_index: break \n",
    "    # VERY important: if len(array) is odd: this never happens: high index == low index so <= sign is crucial\n",
    "    # Example: 7-0 , 6-1, 5-2, 4-3, 3-4, stop here. So 3==3 or 4==4 didn't happen.\n",
    "    rearranged_array.append(sorted_array[high_index])\n",
    "    rearranged_array.append(sorted_array[low_index])\n",
    "\n",
    "print(rearranged_array)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "([1, 2, 3, 8], 3)\n"
     ]
    }
   ],
   "source": [
    "# The number of inversions of an array shows how far this array is away from being sorted. if it is 0 it is sorted.\n",
    "# Find the inversions of an array using merge sort\n",
    "\n",
    "def merge_sort_w_inversion_count(arr):\n",
    "    inversions = 0\n",
    "    if len(arr) == 1: return arr, inversions\n",
    "    left = arr[:len(arr)//2]\n",
    "    right = arr[len(arr)//2:]\n",
    "    a, ai = merge_sort_w_inversion_count(left)\n",
    "    b, bi = merge_sort_w_inversion_count(right)\n",
    "    inversions = ai + bi\n",
    "    # merge two sorted arrays a and b\n",
    "    combine = [] \n",
    "    i = 0\n",
    "    j = 0\n",
    "    while i < len(a) and j < len(b):\n",
    "        if a[i] < b[j]:\n",
    "            combine.append(a[i])\n",
    "            i += 1\n",
    "        elif a[i] > b[j]:\n",
    "            combine.append(b[j])\n",
    "            j += 1\n",
    "            inversions += 1     \n",
    "        else:\n",
    "            combine.append(a[i])\n",
    "            combine.append(b[j])\n",
    "            i += 1\n",
    "            j += 1\n",
    "            \n",
    "        if i == len(a):\n",
    "            for k in range(j, len(b)):\n",
    "                combine.append(b[k])\n",
    "        if j == len(b):\n",
    "            for k in range(i, len(a)):\n",
    "                combine.append(a[k])\n",
    "                inversions += 1\n",
    "    \n",
    "    # print(arr, a, b, inversions)                   \n",
    "    return combine, inversions\n",
    "    \n",
    "\n",
    "test_array2 = [3,2,1,8]\n",
    "print(merge_sort_w_inversion_count(test_array2))\n",
    "\n",
    "# test_array = [2,3,6,6,1,-2,13,0]\n",
    "# merge_sort_w_inversion_count(test_array)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[2, 1], [2, 5], [6, 1]]\n"
     ]
    }
   ],
   "source": [
    "# Find number of pairs (x, y) in an array such that x^y > y^x    Ex: X = {2, 1, 6}, Y = {1, 5} # Output: 3\n",
    "# Explanation: There are total 3 pairs where pow(x, y) is greater than pow(y, x) Pairs are (2, 1), (2, 5) and (6, 1)\n",
    "\n",
    "# Brute force O(n**2) embarrasingly bad solution\n",
    "X = [2,1,6]\n",
    "Y = [1,5]\n",
    "items = []\n",
    "for i in range(len(X)):\n",
    "    for j in range(len(Y)):\n",
    "        if X[i]**Y[j] > Y[j]**X[i]:\n",
    "            items.append([X[i], Y[j]])\n",
    "print(items)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Sort an array of 0s, 1s and 2s in O(n) time\n",
    "# Input: {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1}  Output: {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2} in one pass\n",
    "\n",
    "# Function to sort array \n",
    "def sort012array(a):\n",
    "    n = len(a)\n",
    "    lo = 0\n",
    "    hi = n - 1\n",
    "    mid = 0\n",
    "    while mid <= hi: \n",
    "        if a[mid] == 0: \n",
    "            a[lo], a[mid] = a[mid], a[lo] \n",
    "            lo = lo + 1\n",
    "            mid = mid + 1\n",
    "        elif a[mid] == 1: \n",
    "            mid = mid + 1\n",
    "        else: \n",
    "            a[mid], a[hi] = a[hi], a[mid]  \n",
    "            hi = hi - 1\n",
    "    return a \n",
    "       \n",
    "test_array = [0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1] \n",
    "sort012array(test_array)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Without changing the location of items, find the equilibrium index of an array where left side sum == right side sum\n",
    "\n",
    "def equilibrium(arr): \n",
    "    leftsum = 0\n",
    "    rightsum = 0\n",
    "    n = len(arr) \n",
    "  \n",
    "    for i in range(n): \n",
    "        leftsum = 0\n",
    "        rightsum = 0\n",
    "\n",
    "        for j in range(i): \n",
    "            leftsum += arr[j] \n",
    "\n",
    "        for j in range(i + 1, n): \n",
    "            rightsum += arr[j] \n",
    "\n",
    "        if leftsum == rightsum: \n",
    "            return i \n",
    "      \n",
    "    # return -1 if no equilibrium index is found \n",
    "    return -1\n",
    "              \n",
    "# driver code \n",
    "arr = [-7, -1, 5, -2, -4, -2, 0] \n",
    "equilibrium(arr) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[17, 5, 2]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Find the \"leaders in an array\". An element is leader if it is greater than all the elements to its right side\n",
    "# Note: last element is always in this list\n",
    "\n",
    "def printLeaders(a): \n",
    "    n = len(a)\n",
    "    items = []\n",
    "    max_from_right = a[n-1]         \n",
    "    for i in reversed(range(0, n)):         \n",
    "        if max_from_right <= a[i]:             \n",
    "            max_from_right = a[i] \n",
    "            items.insert(0, a[i])\n",
    "    return items\n",
    "\n",
    "arr = [16, 17, 4, 3, 5, 2]\n",
    "printLeaders(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Find the Minimum Number of Platforms Required for a Railway / Bus Station\n",
    "# Inbound = {9:00, 9:40, 9:50, 11:00, 15:00, 18:00}    \n",
    "# Outbound = {9:10, 12:00, 11:20, 11:30, 19:00, 20:00}\n",
    "# Output: 3.There are at-most three trains at a time (time between 11:00 to 11:20)  \n",
    "# 9:40 train is there until 12 , 9:50 train is there until 11:20, 11:00 train is the third train entering\n",
    "\n",
    "def findPlatform(arr,dep): \n",
    "    assert(len(arr)== len(dep))\n",
    "    n = len(arr)\n",
    "    arr.sort() \n",
    "    dep.sort() \n",
    "    plat_needed = 0  # current number of platforms needed through first train to last train \n",
    "    max_platforms_needed = 0\n",
    "    i = 0\n",
    "    j = 0\n",
    "   \n",
    "    while (i < n and j < n): \n",
    "        if (arr[i] < dep[j]): \n",
    "            plat_needed+=1\n",
    "            i+=1 \n",
    "            if (plat_needed > max_platforms_needed):  \n",
    "                 max_platforms_needed = plat_needed   \n",
    "        else: \n",
    "            plat_needed-=1\n",
    "            j+=1\n",
    "          \n",
    "    return max_platforms_needed \n",
    "  \n",
    "# driver code \n",
    "  \n",
    "arr = [900, 940, 950, 1100, 1500, 1800] \n",
    "dep = [910, 1200, 1120, 1130, 1900, 2000] \n",
    "findPlatform(arr, dep) \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 1  2  3  4  5  6  7  8  9 10]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[3, 2, 1, 6, 5, 4, 9, 8, 7, 10]"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Reverse array in k groups \n",
    "# Ex: arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]  k = 3 output: [3, 2, 1, 6, 5, 4, 9, 8, 7, 11]\n",
    "\n",
    "import numpy as np\n",
    "input_array = np.arange(1, 11, dtype = int)\n",
    "print(input_array)\n",
    "def reverse_array_each_k(array, k):\n",
    "    rev_k = []\n",
    "    n = len(array)\n",
    "    array_with_k = []\n",
    "    for i in range(n):\n",
    "        array_with_k.insert(0,array[i])\n",
    "        if len(array_with_k) == 3:\n",
    "            rev_k += array_with_k\n",
    "            array_with_k = []\n",
    "    return rev_k + array_with_k\n",
    "        \n",
    "reverse_array_each_k(input_array, 3)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[-5, -1, 6, 7, 8, 9, 10, 12, 13, 14]\n",
      "6\n"
     ]
    }
   ],
   "source": [
    "# find kth smallest element of an unsorted array\n",
    "\n",
    "unsorted_array = [13, 12, -1, 6, -5, 14, 9, 8, 7, 10]\n",
    "\n",
    "def sort_array(unsorted_array):\n",
    "    if len(unsorted_array) <= 1: return unsorted_array\n",
    "    mid = len(unsorted_array) // 2\n",
    "    pivot = unsorted_array[mid]\n",
    "    left = [unsorted_array[i] for i in range(len(unsorted_array)) if unsorted_array[i] < pivot]\n",
    "    mid = [unsorted_array[i] for i in range(len(unsorted_array)) if unsorted_array[i] == pivot]\n",
    "    right = [unsorted_array[i] for i in range(len(unsorted_array)) if unsorted_array[i] > pivot]\n",
    "    sort_all = sort_array(left) + mid + sort_array(right)\n",
    "    return sort_all\n",
    "    \n",
    "sorted_array = sort_array(unsorted_array)\n",
    "print(sorted_array)\n",
    "# if k = 3 for third smallest element the item is at index 2 Ex: The smallest element would be at index 0\n",
    "print(sorted_array[2])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "Fizz\n",
      "4\n",
      "Buzz\n",
      "Fizz\n",
      "7\n",
      "8\n",
      "Fizz\n",
      "Buzz\n",
      "11\n",
      "Fizz\n",
      "13\n",
      "14\n",
      "FizzBuzz\n",
      "16\n"
     ]
    }
   ],
   "source": [
    "# Famous fizzbuzz question where order matters to print the solution\n",
    "\n",
    "for num in range(1, 17):\n",
    "    if num % 15 is 0:\n",
    "        print(\"FizzBuzz\")\n",
    "    elif num % 3 is 0:\n",
    "        print(\"Fizz\")\n",
    "    elif num % 5 is 0:\n",
    "        print(\"Buzz\")\n",
    "    else:\n",
    "        print(num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Maximum water that can be accumulated is 6\n"
     ]
    }
   ],
   "source": [
    "def findWater(arr, n): \n",
    "  \n",
    "    # left[i] contains height of tallest bar to the \n",
    "    # left of i'th bar including itself \n",
    "    left = [0]*n \n",
    "  \n",
    "    # Right [i] contains height of tallest bar to \n",
    "    # the right of ith bar including itself \n",
    "    right = [0]*n \n",
    "  \n",
    "    # Initialize result \n",
    "    water = 0\n",
    "  \n",
    "    # Fill left array \n",
    "    left[0] = arr[0] \n",
    "    for i in range( 1, n): \n",
    "        left[i] = max(left[i-1], arr[i]) \n",
    "  \n",
    "    # Fill right array \n",
    "    right[n-1] = arr[n-1] \n",
    "    for i in range(n-2, -1, -1): \n",
    "        right[i] = max(right[i + 1], arr[i]); \n",
    "  \n",
    "    # Calculate the accumulated water element by element \n",
    "    # consider the amount of water on i'th bar, the \n",
    "    # amount of water accumulated on this particular \n",
    "    # bar will be equal to min(left[i], right[i]) - arr[i] . \n",
    "    for i in range(0, n): \n",
    "        water += min(left[i], right[i]) - arr[i] \n",
    "  \n",
    "    return water \n",
    "\n",
    "arr = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] \n",
    "n = len(arr) \n",
    "print(\"Maximum water that can be accumulated is\", findWater(arr, n)) \n",
    "\n",
    "#         | \n",
    "#     |xxx||x|\n",
    "# _|x|||x|||||\n",
    "# Trap \"1 unit\" between first 1 and 2, \"4 units\" between\n",
    "# first 2 and 3 and \"1 unit\" between second last 1 and last 2 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Yes\n"
     ]
    }
   ],
   "source": [
    "# Finding pythogorian triplets in array Using Hashing. The time complexity will be O(max, max) max element of the array\n",
    "# Find if a2 + b2 = c2 in an array  Example:  Input: arr[] = {3, 1, 4, 6, 5} Output: True (3, 4, 5)\n",
    "\n",
    "import math \n",
    "  \n",
    "def checkTriplet(arr, n): \n",
    "    maximum = 0\n",
    "  \n",
    "    # Find the maximum element \n",
    "    for i in range(n): \n",
    "        maximum = max(maximum, arr[i]) \n",
    "  \n",
    "        # Hashing array \n",
    "    hash = [0]*(maximum+1) \n",
    "  \n",
    "    # Increase the count of array elements \n",
    "    # in hash table \n",
    "    for i in range(n): \n",
    "        hash[arr[i]] += 1\n",
    "  \n",
    "        # Iterate for all possible a \n",
    "    for i in range(1, maximum+1): \n",
    "        # If a is not there \n",
    "        if (hash[i] == 0): \n",
    "            continue\n",
    "  \n",
    "        # Iterate for all possible b \n",
    "        for j in range(1, maximum+1): \n",
    "            # If a and b are same and there is only one a \n",
    "            # or if there is no b in original array \n",
    "            if ((i == j and hash[i] == 1) or hash[j] == 0): \n",
    "                continue\n",
    "  \n",
    "            # Find c \n",
    "            val = int(math.sqrt(i * i + j * j)) \n",
    "  \n",
    "            # If c^2 is not a perfect square \n",
    "            if ((val * val) != (i * i + j * j)): \n",
    "                continue\n",
    "  \n",
    "            # If c exceeds the maximum value \n",
    "            if (val > maximum): \n",
    "                continue\n",
    "  \n",
    "            # If there exists c in the original array, \n",
    "            # we have the triplet \n",
    "            if (hash[val]): \n",
    "                return True\n",
    "    return False\n",
    "  \n",
    "arr = [3, 2, 4, 6, 5] \n",
    "n = len(arr) \n",
    "if (checkTriplet(arr, n)): \n",
    "    print(\"Yes\") \n",
    "else: \n",
    "    print(\"No\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([40, 41, 42, 43, 44, 48, 50])"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Find m number of points in an array where min-max diff would be minimum of a subarray with size m\n",
    "# Answer to minimize difference between maximum and minimum. The well-known \"Chocolate Distribution Question\" \n",
    "\n",
    "# Ex: Array = [12, 4, 7, 9, 2, 23, 25, 41, 30, 40, 28, 42, 30, 44, 48, 43, 50]\n",
    "# m = 7 packages will be distributed, which packages should be distributed?\n",
    "# Output: Minimum Difference is 10 if we need to pick 7 packets: 40, 41, 42, 44, 48, 43 and 50 \n",
    "\n",
    "def find_smallest_min_max_sub_array(array, m):\n",
    "    array = np.sort(array)\n",
    "    n = len(array)\n",
    "    if m > n: return\n",
    "    diff = np.inf\n",
    "    for i in range(0, len(array)-m):\n",
    "        sub_array = array[i: i+m]\n",
    "        minimum = min(sub_array)\n",
    "        maximum = max(sub_array)\n",
    "        if maximum - minimum < diff:\n",
    "            diff = maximum - minimum\n",
    "            mark_the_starting_ind = i\n",
    "    return array[i: i+ m+1]\n",
    "            \n",
    "test_array = [12, 4, 7, 9, 2, 23, 25, 41, 30, 40, 28, 42, 30, 44, 48, 43, 50]    \n",
    "find_smallest_min_max_sub_array(test_array, 6)\n",
    "\n",
    "\n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 0.  0.  0.  0.]\n",
      " [ 0. 12. 12. 12.]\n",
      " [ 0. 12. 12. 12.]\n",
      " [ 0. 70. 82. 82.]\n",
      " [ 0. 70. 82. 82.]\n",
      " [ 0. 75. 87. 97.]]\n",
      "Maximum profit is: 97.0\n"
     ]
    }
   ],
   "source": [
    "# Python program to maximize the profit by doing at most k transactions given stock prices for n days \n",
    "# Function to find out maximum profit by buying & selling a share atmost k times  given stock price of n days \n",
    "\n",
    "def maxProfit(prices, k): \n",
    "    n = len(prices)\n",
    "    if k > n: return\n",
    "    # Bottom-up DP approach \n",
    "    profit = np.zeros([n, k+1]) \n",
    "    # Profit is zero for the first \n",
    "    # day and for zero transactions \n",
    "    for i in range(1, n): # for each day's stock value\n",
    "        for j in range(1, k+1): # for each transaction \n",
    "            max_so_far = 0\n",
    "            for l in range(i): # for all past transactions\n",
    "                max_so_far = max(max_so_far, prices[i] - prices[l] + profit[l][j-1])               \n",
    "            profit[i][j] = max(profit[i - 1][j], max_so_far) \n",
    "    \n",
    "    print(profit) # to view the table\n",
    "    return profit[n - 1][k] \n",
    "  \n",
    "# Driver code \n",
    "k = 3\n",
    "prices = [10, 22, 5, 75, 65, 80] \n",
    "n = len(prices) \n",
    "  \n",
    "print(\"Maximum profit is:\", maxProfit(prices, k)) \n",
    "  \n",
    "# if k = 2, trader earns 87 as sum of 12 and 75 Buy at price 10, sell at 22, buy at 5 and sell at 80,"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 0  0  0  0  0  0]\n",
      " [ 0 12 12 70 70 75]\n",
      " [ 0 12 12 82 82 87]\n",
      " [ 0 12 12 82 82 97]]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "97"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Alternative aolution to maximize the profit by doing at most k transactions given stock prices for n days \n",
    "\n",
    "import numpy as np\n",
    "def maximize_profit_with_k_trsc(price_list, k):\n",
    "    n = len(price_list)\n",
    "    if n <= 1 or k > len(price_list): return 0\n",
    "    memo_table = np.zeros([k+1, n] , dtype = int)  # number of transactions in rows\n",
    "    for i in range(1, k+1): # for each buy and sell transaction, i\n",
    "        max_profit = -np.inf\n",
    "        for j in range(1, len(price_list)): # for each day, j\n",
    "            prev_day_prev_transact = memo_table[i-1][j-1] # max profit until prev day and prev transact\n",
    "            prev_day_price = price_list[j-1]\n",
    "            max_transaction_until_prev_day = memo_table[i][j-1] \n",
    "            price_today = price_list[j]\n",
    "            max_profit = max(max_profit, prev_day_prev_transact - prev_day_price)\n",
    "            memo_table[i][j] = max(max_transaction_until_prev_day, max_profit + price_today)\n",
    "    \n",
    "    print(memo_table)\n",
    "    return memo_table[k][n-1]      \n",
    "            \n",
    "prices = [10, 22, 5, 75, 65, 80] \n",
    "maximize_profit_with_k_trsc(prices, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Find the element before which all the elements are smaller than it, and after which all elements are greater\n",
    "\n",
    "def find_the_element_at_pivot(array):\n",
    "    if len(array) <= 1: return None\n",
    "    for i in range(len(array)): # for all the elements in the array\n",
    "        all_elements_before = array[:i+1]\n",
    "        assert(len(all_elements_before) != 0)\n",
    "        all_elements_after = array[i:]\n",
    "        assert(len(all_elements_after) != 0)\n",
    "        if array[i] == max(all_elements_before) and array[i] == min(all_elements_after):\n",
    "            return array[i]\n",
    "\n",
    "find_the_element_at_pivot([5, 1, 4, 3, 6, 8, 10, 7, 9]) # The answer should be 6\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0, 2, 1, 6, 4, 7, 6, 8, 7, 9, 8])"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# make a zigzag pattern where A < B > C < D > E... the element in odd index is bigger than the elements at both sides\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "def zigzag(array):\n",
    "    n = len(array)\n",
    "    sorted_array = np.sort(array)\n",
    "    for i in range(1, n-1):\n",
    "        if i % 2 == 1:\n",
    "            sorted_array[i], sorted_array[i+1] = sorted_array[i+1], sorted_array[i]\n",
    "    zigzaged_array = sorted_array\n",
    "    return zigzaged_array\n",
    "\n",
    "test_array = [1,6,8,9,2,6,4,7,0,7,8]\n",
    "\n",
    "zigzag(test_array)\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Find the index of first 1 in a sorted array of 0’s and 1’s\n",
    "# Given a sorted array consisting 0’s and 1’s. The problem is to find the index of first ‘1’ in the sorted array. \n",
    "# It could be possible that the array consists of only 0’s or only 1’s. \n",
    "# If 1’s are not present in the array then print “-1”.\n",
    "\n",
    "def find_index_of_first_1(sorted_array): # sorted array is of 0 and 1\n",
    "    if len(sorted_array) == 0: \n",
    "        return \n",
    "    n = len(sorted_array)\n",
    "    # if last element is 0 it will return -1\n",
    "    if sorted_array[n-1] == 0: return -1\n",
    "    for i in range(len(sorted_array)):\n",
    "        if sorted_array[i] == 1:\n",
    "            return i\n",
    "        \n",
    "find_index_of_first_1([0, 0, 1, 1])\n",
    "        \n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 9, 8, 3, 5, 7]"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Python3 program to print given matrix in spiral form \n",
    "\n",
    "def spiralPrint(a) :\n",
    "    \n",
    "    k = 0 # k - starting row index             k,l      n\n",
    "    l = 0 # l - starting column index \n",
    "    m = len(a) # m - ending row index           m\n",
    "    n = len(a[0]) # n - ending column index \n",
    "    spiral_read = []\n",
    "\n",
    "    while (k < m and l < n) : \n",
    "          \n",
    "        # Print the first row then increase the row number by one \n",
    "        for i in range(l, n) : \n",
    "            spiral_read.append(a[k][i]) \n",
    "              \n",
    "        k += 1\n",
    "  \n",
    "        # Print the last column from the remaining columns  \n",
    "        for i in range(k, m) : \n",
    "            spiral_read.append(a[i][n - 1]) \n",
    "              \n",
    "        n -= 1\n",
    "  \n",
    "        # Print the last row from \n",
    "        # the remaining rows  \n",
    "        if (k < m) : \n",
    "              \n",
    "            for i in range(n - 1, (l - 1), -1) : \n",
    "                spiral_read.append(a[m - 1][i]) \n",
    "              \n",
    "            m -= 1\n",
    "          \n",
    "        # Print the first column from the remaining columns  \n",
    "        if (l < n) : \n",
    "            for i in range(m - 1, k - 1, -1) : \n",
    "                spiral_read.append(a[i][l]) \n",
    "              \n",
    "            l += 1\n",
    "        return spiral_read\n",
    "\n",
    "a = [[1, 2, 3], \n",
    "     [7, 4, 9], \n",
    "     [5 ,3, 8]] \n",
    "        \n",
    "\n",
    "spiralPrint(a) \n",
    "  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "90 degrees rotated matrix in counter clock wise [[4, 8, 12], [3, 7, 11], [2, 6, 10], [1, 5, 9]]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# turn matrix counter clock direction and solve the above problem with a horrible space complexity\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "test_m = [[1,2,3,4],\n",
    "          [5,6,7,8],\n",
    "          [9,10,11,12]]\n",
    "\n",
    "def turn_matrix_counter_clock(m):\n",
    "    if len(m) == 0: return\n",
    "    row_length = len(m)\n",
    "    column_length = len(m[0])\n",
    "    turned_m = []\n",
    "    for j in reversed(range(column_length)):\n",
    "        inner_list = []\n",
    "        for i in range(row_length):\n",
    "            inner_list.append(m[i][j])\n",
    "        turned_m.append(inner_list)\n",
    "    return turned_m\n",
    "\n",
    "new_m = turn_matrix_counter_clock(test_m)\n",
    "print('90 degrees rotated matrix in counter clock wise', new_m)\n",
    "\n",
    "# print a matrix in spiral form \n",
    "\n",
    "def print_m_spiral(m):\n",
    "    if len(m) == 0: return\n",
    "    spiral_m = []\n",
    "    while m != None:\n",
    "        spiral_m.extend(m[0])\n",
    "        m_new = m[1:][:]\n",
    "        m = turn_matrix_counter_clock(m_new)    \n",
    "    return spiral_m\n",
    "    \n",
    "                                 \n",
    "print_m_spiral(test_m)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "998764543431"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Arrange given numbers to form the biggest number \n",
    "# Given an array of numbers, arrange them in a way that yields the largest value. \n",
    "# For example, if the given numbers are {54, 546, 548, 60}, \n",
    "# the arrangement 6054854654 gives the largest value. \n",
    "# And if the given numbers are {1, 34, 3, 98, 9, 76, 45, 4}, then the arrangement 998764543431 gives the largest value\n",
    "\n",
    " \n",
    "def permutate(number_set, results = None, solutions = None): # to not to store the mutable default arguments in memory\n",
    "    if results == None: results = []\n",
    "    if solutions == None: solutions = []\n",
    "    if len(number_set) == 0: \n",
    "        results.append(solutions)\n",
    "        return\n",
    "    for i, n in enumerate(number_set):\n",
    "        remaining = number_set[:i] + number_set[i+1:]\n",
    "        if remaining != None:\n",
    "            permutate(remaining, results, solutions + [n])\n",
    "    return results\n",
    "\n",
    "    \n",
    "def return_highest_val(array):\n",
    "    items = []\n",
    "    for item in array:\n",
    "        str_a = [str(i) for i in item]\n",
    "        comb = \"\".join(str_a)\n",
    "        int_comb = int(comb)\n",
    "        items.append(int_comb)\n",
    "    return max(items)\n",
    "\n",
    "\n",
    "\n",
    "set_of_items = [1, 34, 3, 98, 9, 76, 45, 4]\n",
    "perm_of_set_of_items = permutate(set_of_items)\n",
    "return_highest_val(perm_of_set_of_items)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}