Asssignment 3.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "de4abcf5",
   "metadata": {},
   "source": [
    "## Assignment Questions 3 "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "798a14f2-fc71-4ee2-8516-1492efa202ff",
   "metadata": {},
   "source": [
    "**Question 1**\n",
    "Given an integer array nums of length n and an integer target, find three integers\n",
    "in nums such that the sum is closest to the target.\n",
    "Return the sum of the three integers.\n",
    "\n",
    "You may assume that each input would have exactly one solution.\n",
    "\n",
    "Example 1:\n",
    "Input: nums = [-1,2,1,-4], target = 1\n",
    "Output: 2\n",
    "\n",
    "Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "e882d415-53fa-4db1-a9e0-3e4dbded09d9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def threeSumClosest(nums, target):\n",
    "    nums.sort()\n",
    "    n = len(nums)\n",
    "    closestSum = float('inf')\n",
    "\n",
    "    for i in range(n - 2):\n",
    "        left = i + 1\n",
    "        right = n - 1\n",
    "\n",
    "        while left < right:\n",
    "            currentSum = nums[i] + nums[left] + nums[right]\n",
    "\n",
    "            if abs(currentSum - target) < abs(closestSum - target):\n",
    "                closestSum = currentSum\n",
    "\n",
    "            if currentSum > target:\n",
    "                right -= 1\n",
    "            elif currentSum < target:\n",
    "                left += 1\n",
    "            else:\n",
    "                return target\n",
    "\n",
    "    return closestSum\n",
    "\n",
    "\n",
    "nums = [-1, 2, 1, -4]\n",
    "target = 1\n",
    "threeSumClosest(nums, target)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0c3e5c08-6711-4b54-9e0d-9c4d4f7c8929",
   "metadata": {},
   "source": [
    "**Question 2**\n",
    "Given an array nums of n integers, return an array of all the unique quadruplets\n",
    "[nums[a], nums[b], nums[c], nums[d]] such that:\n",
    "           ● 0 <= a, b, c, d < n\n",
    "           ● a, b, c, and d are distinct.\n",
    "           ● nums[a] + nums[b] + nums[c] + nums[d] == target\n",
    "\n",
    "You may return the answer in any order.\n",
    "\n",
    "Example 1:\n",
    "Input: nums = [1,0,-1,0,-2,2], target = 0\n",
    "Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "49126320-ddef-49fb-8524-8449323f95ae",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def fourSum(nums, target):\n",
    "    nums.sort()\n",
    "    n = len(nums)\n",
    "    quadruplets = []\n",
    "\n",
    "    for a in range(n - 3):\n",
    "        if a > 0 and nums[a] == nums[a - 1]:\n",
    "            continue\n",
    "\n",
    "        for b in range(a + 1, n - 2):\n",
    "            if b > a + 1 and nums[b] == nums[b - 1]:\n",
    "                continue\n",
    "\n",
    "            left = b + 1\n",
    "            right = n - 1\n",
    "\n",
    "            while left < right:\n",
    "                currentSum = nums[a] + nums[b] + nums[left] + nums[right]\n",
    "\n",
    "                if currentSum == target:\n",
    "                    quadruplets.append([nums[a], nums[b], nums[left], nums[right]])\n",
    "\n",
    "                    while left < right and nums[left] == nums[left + 1]:\n",
    "                        left += 1\n",
    "                    while left < right and nums[right] == nums[right - 1]:\n",
    "                        right -= 1\n",
    "\n",
    "                    left += 1\n",
    "                    right -= 1\n",
    "                elif currentSum < target:\n",
    "                    left += 1\n",
    "                else:\n",
    "                    right -= 1\n",
    "\n",
    "    return quadruplets\n",
    "\n",
    "\n",
    "nums = [1, 0, -1, 0, -2, 2]\n",
    "target = 0\n",
    "fourSum(nums, target)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4884e983-1f7b-4c61-a7e1-401e3944df27",
   "metadata": {},
   "source": [
    "**Q.3** A permutation of an array of integers is an arrangement of its members into a\n",
    "sequence or linear order.\n",
    "\n",
    "For example, for arr = [1,2,3], the following are all the permutations of arr:\n",
    "[1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].\n",
    "\n",
    "The next permutation of an array of integers is the next lexicographically greater\n",
    "permutation of its integer. More formally, if all the permutations of the array are\n",
    "sorted in one container according to their lexicographical order, then the next\n",
    "permutation of that array is the permutation that follows it in the sorted container.\n",
    "\n",
    "If such an arrangement is not possible, the array must be rearranged as the\n",
    "lowest possible order (i.e., sorted in ascending order).\n",
    "\n",
    "● For example, the next permutation of arr = [1,2,3] is [1,3,2].\n",
    "● Similarly, the next permutation of arr = [2,3,1] is [3,1,2].\n",
    "● While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not\n",
    "have a lexicographical larger rearrangement.\n",
    "\n",
    "Given an array of integers nums, find the next permutation of nums.\n",
    "The replacement must be in place and use only constant extra memory.\n",
    "\n",
    "**Example 1:**\n",
    "Input: nums = [1,2,3]\n",
    "Output: [1,3,2]\n",
    "\n",
    "</aside>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "c3c8c3b5-9e40-413e-a578-8e5b65d52b46",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 3, 2]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def nextPermutation(nums):\n",
    "    n = len(nums)\n",
    "    i = n - 2\n",
    "\n",
    "    while i >= 0 and nums[i] >= nums[i + 1]:\n",
    "        i -= 1\n",
    "\n",
    "    if i >= 0:\n",
    "        j = n - 1\n",
    "        while j >= 0 and nums[j] <= nums[i]:\n",
    "            j -= 1\n",
    "        nums[i], nums[j] = nums[j], nums[i]\n",
    "\n",
    "    left = i + 1\n",
    "    right = n - 1\n",
    "    while left < right:\n",
    "        nums[left], nums[right] = nums[right], nums[left]\n",
    "        left += 1\n",
    "        right -= 1\n",
    "\n",
    "    return nums\n",
    "\n",
    "\n",
    "nums = [1, 2, 3]\n",
    "nextPermutation(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "82ff1a82-21fe-4005-89ef-07ec8d32be62",
   "metadata": {},
   "source": [
    "**Question 4**\n",
    "Given a sorted array of distinct integers and a target value, return the index if the\n",
    "target is found. If not, return the index where it would be if it were inserted in\n",
    "order.\n",
    "\n",
    "You must write an algorithm with O(log n) runtime complexity.\n",
    "\n",
    "Example 1:\n",
    "Input: nums = [1,3,5,6], target = 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "bfd1f055-c56a-4c2a-b4fe-51400ebc29cb",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def searchInsert(nums, target):\n",
    "    left = 0\n",
    "    right = len(nums) - 1\n",
    "\n",
    "    while left <= right:\n",
    "        mid = (left + right) // 2\n",
    "\n",
    "        if nums[mid] == target:\n",
    "            return mid\n",
    "        elif nums[mid] < target:\n",
    "            left = mid + 1\n",
    "        else:\n",
    "            right = mid - 1\n",
    "\n",
    "    return left\n",
    "\n",
    "\n",
    "nums = [1, 3, 5, 6]\n",
    "target = 5\n",
    "searchInsert(nums, target)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "81a151fc-2624-43d4-b3dc-bfa9a7cbb9df",
   "metadata": {},
   "source": [
    "**Q.5** You are given a large integer represented as an integer array digits, where each\n",
    "digits[i] is the ith digit of the integer. The digits are ordered from most significant\n",
    "to least significant in left-to-right order. The large integer does not contain any\n",
    "leading 0's.\n",
    "\n",
    "Increment the large integer by one and return the resulting array of digits.\n",
    "\n",
    "**Example 1:**\n",
    "Input: digits = [1,2,3]\n",
    "Output: [1,2,4]\n",
    "\n",
    "**Explanation:** The array represents the integer 123.\n",
    "Incrementing by one gives 123 + 1 = 124.\n",
    "Thus, the result should be [1,2,4].\n",
    "\n",
    "</aside>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "75da8477-3dd8-4a87-9e66-5613e2b04f34",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 4]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def plusOne(digits):\n",
    "    n = len(digits)\n",
    "\n",
    "    # Start from the rightmost digit\n",
    "    for i in range(n - 1, -1, -1):\n",
    "        digits[i] += 1\n",
    "\n",
    "        if digits[i] == 10:\n",
    "            digits[i] = 0\n",
    "        else:\n",
    "            # No carry left, return the digits array\n",
    "            return digits\n",
    "\n",
    "    # If there is a carry left, insert it at the beginning of the array\n",
    "    digits.insert(0, 1)\n",
    "    return digits\n",
    "\n",
    "\n",
    "digits = [1, 2, 3]\n",
    "plusOne(digits)  # Output: [1, 2, 4]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7e58d455-9e17-4c8c-8376-2aae52768824",
   "metadata": {},
   "source": [
    "**Question 6**\n",
    "Given a non-empty array of integers nums, every element appears twice except\n",
    "for one. Find that single one.\n",
    "\n",
    "You must implement a solution with a linear runtime complexity and use only\n",
    "constant extra space.\n",
    "\n",
    "Example 1:\n",
    "Input: nums = [2,2,1]\n",
    "Output: 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "ae6870ed-aab8-4f0d-9035-50c9cc943cf5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def singleNumber(nums):\n",
    "    result = 0\n",
    "\n",
    "    for num in nums:\n",
    "        result ^= num\n",
    "\n",
    "    return result\n",
    "\n",
    "\n",
    "nums = [2, 2, 1]\n",
    "singleNumber(nums) # Output: 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4494712d-7e7b-46d4-831e-30e646cf1368",
   "metadata": {},
   "source": [
    "**Question 7**\n",
    "You are given an inclusive range [lower, upper] and a sorted unique integer array\n",
    "nums, where all elements are within the inclusive range.\n",
    "\n",
    "A number x is considered missing if x is in the range [lower, upper] and x is not in\n",
    "nums.\n",
    "\n",
    "Return the shortest sorted list of ranges that exactly covers all the missing\n",
    "numbers. That is, no element of nums is included in any of the ranges, and each\n",
    "missing number is covered by one of the ranges.\n",
    "\n",
    "Example 1:\n",
    "Input: nums = [0,1,3,50,75], lower = 0, upper = 99\n",
    "Output: [[2,2],[4,49],[51,74],[76,99]]\n",
    "\n",
    "Explanation: The ranges are:\n",
    "[2,2]\n",
    "[4,49]\n",
    "[51,74]\n",
    "[76,99]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "4b421181-dba9-43d1-9779-a0b1c021da98",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['2', '4->49', '51->74', '76->99']"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def findMissingRanges(nums, lower, upper):\n",
    "    result = []\n",
    "    start = lower\n",
    "\n",
    "    for num in nums:\n",
    "        if num > start:\n",
    "            result.append(getRange(start, num - 1))\n",
    "        start = num + 1\n",
    "\n",
    "    if start <= upper:\n",
    "        result.append(getRange(start, upper))\n",
    "\n",
    "    return result\n",
    "\n",
    "\n",
    "def getRange(start, end):\n",
    "    if start == end:\n",
    "        return str(start)\n",
    "    else:\n",
    "        return str(start) + \"->\" + str(end)\n",
    "\n",
    "\n",
    "    \n",
    "    \n",
    "    \n",
    "nums = [0, 1, 3, 50, 75]\n",
    "lower = 0\n",
    "upper = 99\n",
    "findMissingRanges(nums, lower, upper)  # Output: [[2,2],[4,49],[51,74],[76,99]]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8ae9d179-c5d5-4b8c-b6d9-dff408e02f3d",
   "metadata": {},
   "source": [
    "**Question 8**\n",
    "Given an array of meeting time intervals where intervals[i] = [starti, endi],\n",
    "determine if a person could attend all meetings.\n",
    "\n",
    "Example 1:\n",
    "Input: intervals = [[0,30],[5,10],[15,20]]\n",
    "Output: false"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "120c68f6-8386-46fd-93e1-3d3b6d0248b8",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def canAttendMeetings(intervals):\n",
    "    intervals.sort(key=lambda x: x[0])\n",
    "\n",
    "    for i in range(1, len(intervals)):\n",
    "        if intervals[i][0] < intervals[i-1][1]:\n",
    "            return False\n",
    "\n",
    "    return True\n",
    "\n",
    "\n",
    "intervals = [[0, 30], [5, 10], [15, 20]]\n",
    "canAttendMeetings(intervals)  # Output: False"
   ]
  }
 ],
 "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.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}