Arrays 101.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <font color=\"hotpink\">Arrays 101 </font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Find Numbers with Even Number of Digits\n",
    "Given an array nums of integers, return how many of them contain an even number of digits.\n",
    " \n",
    "*Example 1:* <br>\n",
    "Input: nums = [12,345,2,6,7896] <br>\n",
    "Output: 2 <br>\n",
    "Explanation: <br> \n",
    "    12 contains 2 digits (even number of digits). <br> \n",
    "    345 contains 3 digits (odd number of digits).  <br>\n",
    "    2 contains 1 digit (odd number of digits).  <br>\n",
    "    6 contains 1 digit (odd number of digits). <br>\n",
    "    7896 contains 4 digits (even number of digits). <br> \n",
    "    Therefore only 12 and 7896 contain an even number of digits.\n",
    "\n",
    "*Example 2:* <br>\n",
    "Input: nums = [555,901,482,1771] <br>\n",
    "Output: 1 <br>\n",
    "Explanation: <br>\n",
    "Only 1771 contains an even number of digits.\n",
    " \n",
    "*Constraints:*\n",
    "* 1 <= nums.length <= 500\n",
    "* 1 <= nums[i] <= $10^5$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n"
     ]
    }
   ],
   "source": [
    "class Solution(object):\n",
    "    def findNumbers(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        #focusing on list comprehension to solve otherwise res_nums list not necessarily required that much\n",
    "        \n",
    "        #convert every num to str type\n",
    "        str_nums = [str(num) for num in nums]\n",
    "        \n",
    "        #if str_num len is divisible by 2 then add 1 to res_num list and finally sum of the list\n",
    "        res_nums = [1 for sn in str_nums if len(sn)%2 == 0]\n",
    "\n",
    "        return sum(res_nums)\n",
    "\n",
    "\n",
    "# main\n",
    "obj = Solution()\n",
    "lst = [12,345,2,6,7896]\n",
    "print(obj.findNumbers(lst))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Squares of a Sorted Array\n",
    "Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.\n",
    "\n",
    "*Example 1:* <br>\n",
    "Input: nums = [-4,-1,0,3,10] <br>\n",
    "Output: [0,1,9,16,100] <br>\n",
    "Explanation: After squaring, the array becomes [16,1,0,9,100]. <br>\n",
    "After sorting, it becomes [0,1,9,16,100]. <br>\n",
    "\n",
    "*Example 2:* <br>\n",
    "Input: nums = [-7,-3,2,3,11] <br>\n",
    "Output: [4,9,9,49,121] <br>\n",
    " \n",
    "*Constraints:*\n",
    "* $1 <= nums.length <= 10^4$\n",
    "* $-10^4 <= nums[i] <= 10^4$\n",
    "* nums is sorted in non-decreasing order.\n",
    " \n",
    "\n",
    "Follow up: Squaring each element and sorting the new array is very trivial, could you find an O(n) solution using a different approach?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 9, 16, 100]\n"
     ]
    }
   ],
   "source": [
    "class Solution(object):\n",
    "    def sortedSquares(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        # using two-pointer technique, we can solve it in O(n) time complexity\n",
    "        \n",
    "        i = 0\n",
    "        len_ = len(nums)\n",
    "        j = len_ - 1\n",
    "        count = 0\n",
    "        res = []\n",
    "        \n",
    "        # move the pointer i and j, fwd or bwd respectively according to larger of them (ignoring -ve sign)  \n",
    "        while count != len_:\n",
    "            if abs(nums[i]) > abs(nums[j]):\n",
    "                res.insert(0, nums[i]*nums[i])\n",
    "                i += 1\n",
    "                count += 1\n",
    "            else:\n",
    "                res.insert(0, nums[j]*nums[j])\n",
    "                j -= 1\n",
    "                count += 1\n",
    "        \n",
    "        return res\n",
    "    \n",
    "\n",
    "\n",
    "# main\n",
    "lst = [-4,-1,0,3,10]\n",
    "# lst = [-7,-3,2,3,11]\n",
    "# lst = [0, 0]\n",
    "print(Solution.sortedSquares(Solution, lst))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Duplicate Zeros\n",
    "Given a fixed-length integer array arr, duplicate each occurrence of zero, shifting the remaining elements to the right.\n",
    "\n",
    "Note that elements beyond the length of the original array are not written. Do the above modifications to the input array **in-place** and do not return anything.\n",
    "\n",
    "*Example 1:* <br>\n",
    "Input: arr = [1,0,2,3,0,4,5,0] <br>\n",
    "Output: [1,0,0,2,3,0,0,4] <br>\n",
    "Explanation: After calling your function, the input array is modified to: [1,0,0,2,3,0,0,4] <br>\n",
    "\n",
    "*Example 2:*\n",
    "Input: arr = [1,2,3] <br>\n",
    "Output: [1,2,3] <br>\n",
    "Explanation: After calling your function, the input array is modified to: [1,2,3] <br>\n",
    " \n",
    "*Constraints:*\n",
    "* 1 <= arr.length <= $10^4$\n",
    "* 0 <= arr[i] <= 9"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 0, 0, 2, 3, 0, 0, 4]\n"
     ]
    }
   ],
   "source": [
    "class Solution(object):\n",
    "    def duplicateZeros(self, arr):\n",
    "        \"\"\"\n",
    "        :type arr: List[int]\n",
    "        :rtype: None Do not return anything, modify arr in-place instead.\n",
    "        \"\"\"\n",
    "        # corner case ie. if arr[i]=0; 0 <= i < n and all arr[i] are +ve int\n",
    "        if not sum(arr):\n",
    "            return\n",
    "        \n",
    "        i = 0\n",
    "        while i < len(arr):\n",
    "            if not arr[i]:\n",
    "                arr.pop()        # deletes element from last and insert 0 at i-th pos\n",
    "                arr.insert(i, 0)\n",
    "                i += 1\n",
    "            i += 1\n",
    "        \n",
    "        return   \n",
    "\n",
    "        \n",
    "# main\n",
    "lst = [1,0,2,3,0,4,5,0]\n",
    "# lst = [1,2,3]\n",
    "Solution.duplicateZeros(Solution, lst)\n",
    "print(lst)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Merge Sorted Array\n",
    "\n",
    "You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.\n",
    "\n",
    "Merge nums1 and nums2 into a single array sorted in non-decreasing order.\n",
    "\n",
    "The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.\n",
    "\n",
    " \n",
    "*Example 1:* <br>\n",
    "Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 <br>\n",
    "Output: [1,2,2,3,5,6] <br>\n",
    "Explanation: The arrays we are merging are [1,2,3] and [2,5,6]. <br>\n",
    "The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.\n",
    "\n",
    "*Example 2:* <br>\n",
    "Input: nums1 = [1], m = 1, nums2 = [], n = 0 <br>\n",
    "Output: [1] <br>\n",
    "Explanation: The arrays we are merging are [1] and []. <br>\n",
    "The result of the merge is [1]. <br>\n",
    "\n",
    "*Example 3:* <br>\n",
    "Input: nums1 = [0], m = 0, nums2 = [1], n = 1 <br>\n",
    "Output: [1] <br>\n",
    "Explanation: The arrays we are merging are [] and [1]. <br>\n",
    "The result of the merge is [1]. <br>\n",
    "Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.\n",
    " \n",
    "\n",
    "*Constraints:*\n",
    "* nums1.length == m + n\n",
    "* nums2.length == n\n",
    "* 0 <= m, n <= 200\n",
    "* 1 <= m + n <= 200\n",
    "* $-10^9 <= nums1[i], nums2[j] <= 10^9$\n",
    " \n",
    "Follow up: Can you come up with an algorithm that runs in O(m + n) time?\n",
    "\n",
    "**This quite takes me time, and main step is i < len(nums1) in first while loop condition of function**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Times = 2\n",
      "-------------------------------------------------------------------------------------------------------------- \n",
      " --------------------------------------------------------------------------------------------------------------\n",
      "Iter = 0\n",
      "--------------------------------------------------------------------------------------------------------------\n",
      "Iter = 1\n",
      "--------------------------------------------------------------------------------------------------------------\n",
      "All good\n"
     ]
    }
   ],
   "source": [
    "from random import randint\n",
    "\n",
    "class Solution(object):\n",
    "    def merge(self, nums1, m, nums2, n):\n",
    "        \"\"\"\n",
    "        :type nums1: List[int]\n",
    "        :type m: int\n",
    "        :type nums2: List[int]\n",
    "        :type n: int\n",
    "        :rtype: None Do not return anything, modify nums1 in-place instead.\n",
    "        \"\"\"\n",
    "        # using two-pointer technique\n",
    "        \n",
    "        # i and j are pointers for num1 and num2 respectively\n",
    "        i = 0\n",
    "        j = 0\n",
    "        \n",
    "        nums1[m:] = [] # to shrink the list\n",
    "        \n",
    "        while i < len(nums1) and j < n:    \n",
    "            if nums1[i] >= nums2[j]:\n",
    "                nums1.insert(i, nums2[j])\n",
    "                j += 1     \n",
    "            i += 1\n",
    "                \n",
    "        if j != n:\n",
    "            while j < n:\n",
    "                i += 1\n",
    "                nums1.insert(i, nums2[j])\n",
    "                j += 1\n",
    "\n",
    "        return\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "# algo-checker\n",
    "if __name__ == '__main__':\n",
    "    times = randint(1, 10)\n",
    "    _ = \"-\"*110\n",
    "    print(\"Times =\", times)\n",
    "    print(_, '\\n' ,_)\n",
    "\n",
    "    for t in range(0, times):\n",
    "        print(\"Iter =\", t)\n",
    "        print(_)\n",
    "        m = randint(0, 200)\n",
    "        n = randint(0, 200)\n",
    "        nums1 = []\n",
    "        nums2 = []\n",
    "\n",
    "        for i in range(m):\n",
    "            nums1.append(randint(-10e9, 10e9))\n",
    "        nums1.sort()\n",
    "        tmp_nums1 = nums1[:]\n",
    "\n",
    "        for i in range(n):\n",
    "            nums2.append(randint(-10e9, 10e9))\n",
    "            nums1.append(0)\n",
    "        nums2.sort()\n",
    "\n",
    "        merger_chk = tmp_nums1 + nums2\n",
    "        merger_chk.sort()\n",
    "        Solution.merge(Solution, nums1, m, nums2, n)\n",
    "\n",
    "        if merger_chk != nums1:\n",
    "            print(\"nums1 =\", tmp_nums1, \"\\nnums2 =\", nums2)\n",
    "            print(\"Result =\", nums1)\n",
    "            _ = '*' * 108\n",
    "            print(_)\n",
    "            break\n",
    "    else:\n",
    "        print(\"All good\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Check If N and Its Double Exist\n",
    "Given an array arr of integers, check if there exists two integers N and M such that N is the double of M ( i.e. N = 2 * M).\n",
    "\n",
    "More formally check if there exists two indices i and j such that :\n",
    "* i != j\n",
    "* 0 <= i, j < arr.length\n",
    "* arr[i] == 2 * arr[j]\n",
    " \n",
    "\n",
    "*Example 1:* <br>\n",
    "Input: arr = [10,2,5,3] <br>\n",
    "Output: true <br>\n",
    "Explanation: N = 10 is the double of M = 5,that is, 10 = 2 * 5.\n",
    "\n",
    "*Example 2:* <br>\n",
    "Input: arr = [7,1,14,11] <br>\n",
    "Output: true <br>\n",
    "Explanation: N = 14 is the double of M = 7,that is, 14 = 2 * 7.\n",
    "\n",
    "*Example 3:* <br>\n",
    "Input: arr = [3,1,7,11] <br>\n",
    "Output: false <br>\n",
    "Explanation: In this case does not exist N and M, such that N = 2 * M.\n",
    " \n",
    "*Constraints:*\n",
    "* $2 <= arr.length <= 500$\n",
    "* $-10^3 <= arr[i] <= 10^3$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "class Solution(object):\n",
    "    def checkIfExist(self, arr):\n",
    "        \"\"\"\n",
    "        :type arr: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        for i in range(len(arr)):\n",
    "            # to eliminate same indx coincide main case is arr = [0]\n",
    "            if arr[i]*2 in arr[i+1:] or arr[i]*2 in arr[:i]:  \n",
    "                return True\n",
    "        return False\n",
    "\n",
    "    \n",
    "\n",
    "if __name__ == '__main__':\n",
    "    lst = [10,2,5,3]\n",
    "    print(Solution.checkIfExist(Solution, lst))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Valid Mountain Array\n",
    "\n",
    "Given an array of integers arr, return true if and only if it is a valid mountain array.\n",
    "\n",
    "Recall that arr is a mountain array if and only if:\n",
    "* arr.length >= 3\n",
    "* There exists some i with 0 < i < arr.length - 1 such that:\n",
    "    * arr[0] < arr[1] < ... < arr[i - 1] < arr[i]\n",
    "    * arr[i] > arr[i + 1] > ... > arr[arr.length - 1]\n",
    "\n",
    "<img src=\"https://assets.leetcode.com/uploads/2019/10/20/hint_valid_mountain_array.png\" alt=\"expl\" width=500/>\n",
    "\n",
    "*Example 1:* <br>\n",
    "Input: arr = [2,1] <br>\n",
    "Output: false \n",
    "\n",
    "*Example 2:* <br>\n",
    "Input: arr = [3,5,5] <br>\n",
    "Output: false \n",
    "\n",
    "*Example 3:* <br>\n",
    "Input: arr = [0,3,2,1] <br>\n",
    "Output: true\n",
    " \n",
    "*Constraints:*\n",
    "* $1 <= arr.length <= 10^4$\n",
    "* $0 <= arr[i] <= 10^4$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[7, 8, 10, 3]\n",
      "[7, 10, 7, 0]\n",
      "[7, 9, 10, 4, 3]\n",
      "[2, 9, 3]\n",
      "[0, 10, 8]\n"
     ]
    }
   ],
   "source": [
    "from random import randint\n",
    "\n",
    "class Solution(object):\n",
    "    def validMountainArray(self, arr):\n",
    "        \"\"\"\n",
    "        :type arr: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        # corner case\n",
    "        len_ = len(arr)\n",
    "        if len_ < 3:\n",
    "            return False\n",
    "        \n",
    "        # first check for increasing order\n",
    "        i = 0\n",
    "        while i < len_-1:\n",
    "            if arr[i] < arr[i+1]:\n",
    "                i += 1\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        # this i-th index is the peak of mountain if all-goes well\n",
    "        if i >= len_-1 or i == 0:\n",
    "            return False\n",
    "        \n",
    "        # at-last check for decreasing order \n",
    "        while i < len_-1:\n",
    "            if arr[i] > arr[i+1]:\n",
    "                i += 1\n",
    "            else:\n",
    "                return False\n",
    "        \n",
    "        return True\n",
    "\n",
    "\n",
    "# main\n",
    "if __name__ == '__main__':\n",
    "    # random test-case generator\n",
    "    times = randint(1, 100)\n",
    "    \n",
    "    for t in range(times):\n",
    "        n = randint(1, 10)\n",
    "        lst = [randint(0, 10) for i in range(n)]\n",
    "        if Solution.validMountainArray(Solution, lst):\n",
    "            print(lst)\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Replace Elements with Greatest Element on Right Side\n",
    "Given an array arr, replace every element in that array with the greatest element among the elements to its right, and replace the last element with -1.\n",
    "\n",
    "After doing so, return the array.\n",
    "\n",
    "*Example 1:* <br>\n",
    "Input: arr = [17,18,5,4,6,1] <br>\n",
    "Output: [18,6,6,6,1,-1] <br>\n",
    "Explanation:\n",
    "- index 0 --> the greatest element to the right of index 0 is index 1 (18).\n",
    "- index 1 --> the greatest element to the right of index 1 is index 4 (6).\n",
    "- index 2 --> the greatest element to the right of index 2 is index 4 (6).\n",
    "- index 3 --> the greatest element to the right of index 3 is index 4 (6).\n",
    "- index 4 --> the greatest element to the right of index 4 is index 5 (1).\n",
    "- index 5 --> there are no elements to the right of index 5, so we put -1.\n",
    "\n",
    "*Example 2:* <br>\n",
    "Input: arr = [400] <br>\n",
    "Output: [-1] <br>\n",
    "Explanation: There are no elements to the right of index 0.\n",
    " \n",
    "*Constraints:*\n",
    "* $1 <= arr.length <= 10^4$\n",
    "* $1 <= arr[i] <= 10^5$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "----------------------------------------------------------------------------------------------------\n",
      "[4, 4]\n",
      "[4, -1]\n"
     ]
    }
   ],
   "source": [
    "from random import randint\n",
    "\n",
    "class Solution(object):\n",
    "    def replaceElements(self, arr):\n",
    "        \"\"\"\n",
    "        :type arr: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        len_ = len(arr)\n",
    "        i = 0\n",
    "        \n",
    "        while i < len_-1:\n",
    "            mx = max(arr[i+1:])\n",
    "            arr[i] = mx\n",
    "            i += 1\n",
    "        \n",
    "        # at the last index \n",
    "        arr[i] = -1\n",
    "        \n",
    "        return arr\n",
    "    \n",
    "\n",
    "\n",
    "# main\n",
    "if __name__ == '__main__':\n",
    "    times = randint(1, 5)\n",
    "    \n",
    "    for t in range(times):\n",
    "        lst = [randint(1, 10) for ele in range(randint(1, 5))]\n",
    "        print('-'*100)\n",
    "        print(lst)\n",
    "        print(Solution.replaceElements(Solution, lst))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sort Array By Parity\n",
    "Given an integer array nums, move all the even integers at the beginning of the array followed by all the odd integers.\n",
    "Return any array that satisfies this condition.\n",
    "\n",
    " \n",
    "*Example 1:* <br>\n",
    "Input: nums = [3,1,2,4] <br>\n",
    "Output: [2,4,3,1] <br>\n",
    "Explanation: The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.\n",
    "\n",
    "*Example 2:* <br>\n",
    "Input: nums = [0] <br>\n",
    "Output: [0] <br>\n",
    " \n",
    "*Constraints:*\n",
    "* 1 <= nums.length <= 5000\n",
    "* 0 <= nums[i] <= 5000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 6, 3, 1]\n"
     ]
    }
   ],
   "source": [
    "class Solution(object):\n",
    "    def sortArrayByParity(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        # using two-pointer technique\n",
    "        l, h = 0, len(nums) - 1\n",
    "        \n",
    "        while l < h:\n",
    "            # swap elements if num[l] is odd number and decrement high\n",
    "            if nums[l] % 2:\n",
    "                nums[l], nums[h] = nums[h], nums[l]\n",
    "                h -= 1\n",
    "            else:\n",
    "                l += 1\n",
    "        \n",
    "        return nums\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    lst = [2,1,6,3]\n",
    "    obj = Solution()\n",
    "    print(obj.sortArrayByParity(lst))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Height Checker\n",
    "A school is trying to take an annual photo of all the students. The students are asked to stand in a single file line in non-decreasing order by height. Let this ordering be represented by the integer array expected where expected[i] is the expected height of the ith student in line.\n",
    "\n",
    "You are given an integer array heights representing the current order that the students are standing in. Each heights[i] is the height of the ith student in line (0-indexed).\n",
    "\n",
    "Return the number of indices where heights[i] != expected[i].\n",
    "\n",
    " \n",
    "\n",
    "*Example 1:* <br>\n",
    "Input: heights = [1,1,4,2,1,3] <br>\n",
    "Output: 3 <br>\n",
    "Explanation:  <br>\n",
    "heights:  [1,1,4,2,1,3] <br>\n",
    "expected: [1,1,1,2,3,4] <br>\n",
    "Indices 2, 4, and 5 do not match. <br>\n",
    "\n",
    "\n",
    "*Example 2:*\n",
    "Input: heights = [5,1,2,3,4] <br>\n",
    "Output: 5 <br>\n",
    "Explanation: <br>\n",
    "heights:  [5,1,2,3,4] <br>\n",
    "expected: [1,2,3,4,5] <br>\n",
    "All indices do not match. <br>\n",
    "\n",
    "\n",
    "*Example 3:* <br>\n",
    "Input: heights = [1,2,3,4,5] <br>\n",
    "Output: 0 <br>\n",
    "Explanation: <br>\n",
    "heights:  [1,2,3,4,5] <br>\n",
    "expected: [1,2,3,4,5] <br>\n",
    "All indices match. <br>\n",
    " \n",
    "\n",
    "*Constraints:*\n",
    "* 1 <= heights.length <= 100\n",
    "* 1 <= heights[i] <= 100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 1, 1, 2, 3, 4]\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "class Solution(object):\n",
    "    def heightChecker(self, heights):\n",
    "        \"\"\"\n",
    "        :type heights: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # duplicate of original array without reference\n",
    "        another = heights[:]\n",
    "        another.sort()\n",
    "\n",
    "        count = 0\n",
    "        \n",
    "        for i in range(len(heights)):\n",
    "            if another[i] != heights[i]:\n",
    "                count += 1\n",
    "        \n",
    "        return count\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    obj = Solution()\n",
    "    lst = [1,1,4,2,1,3]\n",
    "    print(obj.heightChecker(lst))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Third Maximum Number\n",
    "\n",
    "Given an integer array nums, return the third distinct maximum number in this array. **If the third maximum does not exist, return the maximum number.**\n",
    "\n",
    " \n",
    "\n",
    "*Example 1:* <br>\n",
    "Input: nums = [3,2,1] <br>\n",
    "Output: 1 <br>\n",
    "Explanation: <br>\n",
    "The first distinct maximum is 3. <br>\n",
    "The second distinct maximum is 2. <br>\n",
    "The third distinct maximum is 1. <br>\n",
    "\n",
    "*Example 2:* <br>\n",
    "Input: nums = [1,2] <br>\n",
    "Output: 2 <br>\n",
    "Explanation: <br>\n",
    "The first distinct maximum is 2. <br>\n",
    "The second distinct maximum is 1. <br>\n",
    "The third distinct maximum does not exist, so the maximum (2) is returned instead.\n",
    "\n",
    "*Example 3:* <br>\n",
    "Input: nums = [2,2,3,1] <br>\n",
    "Output: 1 <br>\n",
    "Explanation: <br>\n",
    "The first distinct maximum is 3. <br>\n",
    "The second distinct maximum is 2 (both 2's are counted together since they have the same value). <br>\n",
    "The third distinct maximum is 1. <br>\n",
    " \n",
    "\n",
    "*Constraints:*\n",
    "* $1 <= nums.length <= 10^4$\n",
    "* $-2^{31} <= nums[i] <= 2^{31} - 1$\n",
    " \n",
    "\n",
    "Follow up: Can you find an O(n) solution?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[6, -3]\n",
      "6\n",
      "----------------------------------------------------------------------------------------------------\n",
      "[-6]\n",
      "-6\n",
      "----------------------------------------------------------------------------------------------------\n",
      "[-2, -8, -1, -1, -7]\n",
      "-7\n",
      "----------------------------------------------------------------------------------------------------\n",
      "[8, 2, 7, 9, -4]\n",
      "7\n",
      "----------------------------------------------------------------------------------------------------\n",
      "[2, -2]\n",
      "2\n",
      "----------------------------------------------------------------------------------------------------\n"
     ]
    }
   ],
   "source": [
    "from random import randint\n",
    "\n",
    "class Solution(object):\n",
    "    def thirdMax(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # Time complexity is O(n) and space-complexity is constant\n",
    "        if not nums:\n",
    "            return\n",
    "        \n",
    "        mx = max(nums)\n",
    "        mx_lst = [mx]\n",
    "        i = 1\n",
    "        \n",
    "        #try block for empty sequence error which can occured from max()\n",
    "        try:\n",
    "            while i < 3:\n",
    "                #try block for element which is not present in sequence\n",
    "                try:\n",
    "                    # remove all occurence of max element and if ValueError occurs update the max\n",
    "                    while True:\n",
    "                        nums.remove(mx)\n",
    "                except ValueError:\n",
    "                    mx = max(nums)\n",
    "                    mx_lst.append(mx)\n",
    "                    i += 1\n",
    "        except ValueError:\n",
    "            if len(mx_lst) < 3:\n",
    "                return max(mx_lst)\n",
    "            \n",
    "        return mx\n",
    "\n",
    "\n",
    "    \n",
    "if __name__ == '__main__':\n",
    "    # random test-case generator\n",
    "    times = randint(1,10)\n",
    "    for t in range(times):\n",
    "        lst = [randint(-10,10) for ele in range(randint(1,5))]\n",
    "        print(lst)\n",
    "        \n",
    "        obj = Solution()\n",
    "        print(obj.thirdMax(lst))\n",
    "        print('-'*100)\n",
    "                "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Find All Numbers Disappeared in an Array\n",
    "Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.\n",
    "\n",
    "*Example 1:* <br>\n",
    "Input: nums = [4,3,2,7,8,2,3,1] <br>\n",
    "Output: [5,6]\n",
    "\n",
    "*Example 2:* <br>\n",
    "Input: nums = [1,1] <br>\n",
    "Output: [2]\n",
    " \n",
    "\n",
    "*Constraints:*\n",
    "* n == nums.length\n",
    "* $1 <= n <= 10^5$\n",
    "* 1 <= nums[i] <= n\n",
    " \n",
    "\n",
    "Follow up: Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.\n",
    "\n",
    "**Solution**: <br>\n",
    "While accessing the element from the array, make the array[element] to negative (use the element as index and make that index value negative). Now after this operation, we were left out with some non-negative values, now just append those non-negative element's index position + 1 (ie. indx+1) to resultant array. Resulatant array would be the answer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[5, 6]\n"
     ]
    }
   ],
   "source": [
    "class Solution(object):\n",
    "    def findDisappearedNumbers(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        # By using negative index method, in O(n) time and O(1) space complexity respectively\n",
    "        len_ = len(nums)\n",
    "        res = []\n",
    "        \n",
    "        for ele in nums:\n",
    "            # negate the indx pos\n",
    "            indx = abs(ele) - 1\n",
    "            if nums[indx] > 0:\n",
    "                nums[indx] = -nums[indx]\n",
    "        \n",
    "        # append the indx + 1 to res for non-negative elements\n",
    "        for i in range(len_):\n",
    "            if nums[i] > 0:\n",
    "                res.append(i + 1)\n",
    "        \n",
    "        return res\n",
    "        \n",
    "        \n",
    "    def _findDisappearedNumbers(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        # By use of hashing it takes O(n) time and space complexity\n",
    "        len_ = len(nums)\n",
    "        hash_ary = [0]*(len_+1)\n",
    "        \n",
    "        #incr the count of nums\n",
    "        for ele in nums:\n",
    "            hash_ary[ele] += 1\n",
    "        \n",
    "        return [indx for indx in range(1, len_+1) if not hash_ary[indx]]\n",
    "\n",
    "\n",
    "    \n",
    "if __name__ == '__main__':\n",
    "    obj = Solution()\n",
    "    lst = [4,3,2,7,8,2,3,1]\n",
    "    print(obj.findDisappearedNumbers(lst))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.10.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}