DAY 5-8.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Two Sum \n",
    "Given an array of integers, return indices of the two numbers such that they add up to a specific target.\n",
    "\n",
    "You may assume that each input would have exactly one solution, and you may not use the same element twice.\n",
    "\n",
    "Given nums = [2, 7, 11, 15], target = 9,\n",
    "\n",
    "Because nums[0] + nums[1] = 2 + 7 = 9,\n",
    "return [0, 1]."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def twoSums(nums,target):\n",
    "    seen={}\n",
    "    for i,value in enumerate(nums):\n",
    "        remaining=target-nums[i]\n",
    "            \n",
    "        if remaining in seen:\n",
    "            return[i,seen[remaining]]\n",
    "            \n",
    "        else:\n",
    "            seen[value]=i\n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 0]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums=[2,7,11,15]\n",
    "target=9\n",
    "twoSums(nums,target)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Remove Element\n",
    "Given an array nums and a value val, remove all instances of that value in-place and return the new length.\n",
    "\n",
    "Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.\n",
    "\n",
    "The order of elements can be changed. It doesn't matter what you leave beyond the new length.\n",
    "\n",
    "Given nums = [3,2,2,3], val = 3,\n",
    "\n",
    "Your function should return length = 2, with the first two elements of nums being 2.\n",
    "\n",
    "It doesn't matter what you leave beyond the returned length."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def removeElements(nums,val):\n",
    "    shift=0\n",
    "    for i in range(len(nums)):\n",
    "        if(nums[i]==val):\n",
    "            shift=shift+1\n",
    "            \n",
    "        else:\n",
    "            nums[i-shift]=nums[i]\n",
    "            \n",
    "    return len(nums)-shift"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums=[3,2,2,3]\n",
    "val=3\n",
    "\n",
    "removeElements(nums,val)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3.Search Insert Position \n",
    "Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.\n",
    "\n",
    "You may assume no duplicates in the array.\n",
    "\n",
    "Input: [1,3,5,6], 5\n",
    "Output: 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def searchInsertPosition(nums,target):\n",
    "    for i in range(len(nums)):\n",
    "        if(nums[i]==target):\n",
    "            return i\n",
    "        if(nums[i]>target):\n",
    "            return i\n",
    "    return i+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums=[1,3,5,6]\n",
    "target=5\n",
    "\n",
    "searchInsertPosition(nums,target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums=[1,3,5,6]\n",
    "target=2\n",
    "\n",
    "searchInsertPosition(nums,target)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 4. Maximum Subarray\n",
    "Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.<br>\n",
    "Input: [-2,1,-3,4,-1,2,1,-5,4],<br>\n",
    "Output: 6<br>\n",
    "Explanation: [4,-1,2,1] has the largest sum = 6."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def maximumSubarray(nums):\n",
    "    maxSub=nums[0]\n",
    "    curSum=0\n",
    "    \n",
    "    for i in nums:\n",
    "        if curSum<0:\n",
    "            curSum=0\n",
    "        curSum+=i \n",
    "        \n",
    "        maxSub=max(maxSub,curSum)\n",
    "    return maxSub"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums=[-2,1,-3,4,-1,2,1,-5,4]\n",
    "maximumSubarray(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5. Plus One\n",
    "Given a non-empty array of digits representing a non-negative integer, increment one to the integer.\n",
    "\n",
    "The digits are stored such that the most significant digit is at the head of the list, and each element in the array contains a single digit.\n",
    "\n",
    "You may assume the integer does not contain any leading zero, except the number 0 itself.\n",
    "\n",
    "Input: [1,2,3]<br>\n",
    "Output: [1,2,4]<br>\n",
    "Explanation: The array represents the integer 123"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def plusOne(digits):\n",
    "    n=len(digits)\n",
    "    \n",
    "    for i in range(n-1,-1,-1):\n",
    "        if digits[i]==9:\n",
    "            digits[i]=0\n",
    "            \n",
    "            if(i==0):\n",
    "                digits.insert(0,1)\n",
    "                \n",
    "        else:\n",
    "            digits[i]+=1\n",
    "            break\n",
    "    return digits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 4]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "digits=[1,2,3]\n",
    "plusOne(digits)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 0, 0, 0]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "digits=[9,9,9]\n",
    "plusOne(digits)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6.Remove Duplicates from Sorted Array\n",
    "Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.\n",
    "\n",
    "Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.\n",
    "\n",
    "Given nums = [1,1,2],\n",
    "\n",
    "Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.\n",
    "\n",
    "It doesn't matter what you leave beyond the returned length."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def removeDuplicates(nums):\n",
    "    i=1\n",
    "    while(i<len(nums)):\n",
    "        if nums[i]==nums[i-1]:\n",
    "            nums.pop(i)\n",
    "            \n",
    "        else:\n",
    "            i+=1\n",
    "    return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums=[1,1,2]\n",
    "removeDuplicates(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3, 4]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [0,0,1,1,1,2,2,3,3,4]\n",
    "removeDuplicates(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 7.Merge Sorted Array\n",
    "Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.\n",
    "\n",
    "__Note:___\n",
    "\n",
    "The number of elements initialized in nums1 and nums2 are m and n respectively.\n",
    "You may assume that nums1 has enough space (size that is equal to m + n) to hold additional elements from nums2.\n",
    "\n",
    "Input:\n",
    "nums1 = [1,2,3,0,0,0], m = 3<br>\n",
    "nums2 = [2,5,6],       n = 3<br>\n",
    "\n",
    "Output: [1,2,2,3,5,6]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mergeSortedArray(num1,m,nums2,n):\n",
    "    i=m-1\n",
    "    j=n-1\n",
    "    k=m+n-1\n",
    "    \n",
    "    while(i>=0 and j>=0):\n",
    "        if nums1[i]>nums2[j]:\n",
    "            nums1[k]=nums1[i]\n",
    "            i-=1\n",
    "            k-=1\n",
    "            \n",
    "        else:\n",
    "            nums1[k]=nums2[j]\n",
    "            j-=1\n",
    "            k-=1\n",
    "            \n",
    "    while(j>=0):\n",
    "        nums1[k]=nums2[j]\n",
    "        j-=1\n",
    "        k-=1\n",
    "    return nums1       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 2, 3, 5, 6]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums1 = [1,2,3,0,0,0]\n",
    "m = 3\n",
    "nums2 = [2,5,6]\n",
    "n = 3\n",
    "mergeSortedArray(nums1,m,nums2,n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 8. Pascal's Triangle\n",
    "____Input:____ 5<br>\n",
    "____Output:____<br>\n",
    "[\n",
    "     [1],\n",
    "    [1,1],\n",
    "   [1,2,1],\n",
    "  [1,3,3,1],\n",
    " [1,4,6,4,1]\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate(numRows):\n",
    "    n=numRows\n",
    "    \n",
    "    if n<=0:\n",
    "        return []\n",
    "    \n",
    "    if n==1:\n",
    "        return [[1]]\n",
    "    \n",
    "    if n==2:\n",
    "        return [[1],[1,1]]\n",
    "    \n",
    "    arr=[[1],[1,1]]\n",
    "    k=1\n",
    "    \n",
    "    for i in range(2,n):\n",
    "        arr.append([])\n",
    "        arr[i].append(1)\n",
    "        for j in range(1,k+1):\n",
    "            arr[i].append(arr[i-1][j-1]+arr[i-1][j])\n",
    "        k+=1\n",
    "        arr[i].append(1)\n",
    "    return arr\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "numRows=5\n",
    "generate(numRows)"
   ]
  },
  {
   "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.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}