{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "3c2ff30a-7947-41cb-8173-84aa53605495",
   "metadata": {},
   "source": [
    "# Divide and Conquer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "2b3aa2bc-6332-4eb6-82d8-175e951dd8e9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<script>code_show=true; function code_toggle() { if (code_show){ $('div.nbinput').show(); } else { $('div.nbinput').hide(); } code_show = !code_show} $( document ).ready(code_toggle);</script><form action=\"javascript:code_toggle()\"><input type=\"submit\" value=\"Click here to toggle on/off the raw code.\"></form>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import IPython; IPython.display.HTML('''<script>code_show=true; function code_toggle() { if (code_show){ $('div.nbinput').show(); } else { $('div.nbinput').hide(); } code_show = !code_show} $( document ).ready(code_toggle);</script><form action=\"javascript:code_toggle()\"><input type=\"submit\" value=\"Click here to toggle on/off the raw code.\"></form>''')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "39926574-a2f5-4837-b207-713b758ecdb0",
   "metadata": {},
   "source": [
    "## [169. Majority Element](https://leetcode.com/problems/majority-element/)\n",
    "\n",
    "Easy\n",
    "\n",
    "Given an array nums of size n, return the majority element.\n",
    "\n",
    "The majority element is the element that appears more than floor(n/2) times. You may assume that the majority element always exists in the array.\n",
    "\n",
    "Example 2:\n",
    "\n",
    "    Input: nums = [2,2,1,1,1,2,2]\n",
    "    Output: 2\n",
    "\n",
    "Constraints:\n",
    "\n",
    "    n == nums.length\n",
    "    1 <= n <= 5 * 10^4\n",
    "    -10^9 <= nums[i] <= 10^9\n",
    "\n",
    "Follow-up: Could you solve the problem in linear time and in O(1) space?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "185b32f4-9892-431e-8b80-96ebdb5ae5bb",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# The Boyer-Moore Voting Algorithm: Because this majority element occurs more than n/2 (floor value) times, even if other elements will 'vote against it', it will win\n",
    "\n",
    "def majorityElement(nums):\n",
    "    res = count = 0\n",
    "    for n in nums:\n",
    "        if count==0:\n",
    "            res = n\n",
    "        count += (1 if n==res else -1)\n",
    "    return res\n",
    "\n",
    "majorityElement([2, 2, 1, 1, 1, 2, 2])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0aa1a7a8-707c-4b21-b89f-3eb6acb9b40b",
   "metadata": {},
   "source": [
    "## [153. Find Minimum in Rotated Sorted Array](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/)\n",
    "\n",
    "Medium\n",
    "\n",
    "Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:\n",
    "\n",
    "    [4,5,6,7,0,1,2] if it was rotated 4 times.\n",
    "    [0,1,2,4,5,6,7] if it was rotated 7 times.\n",
    "\n",
    "Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].\n",
    "\n",
    "Given the sorted rotated array nums of unique elements, return the minimum element of this array.\n",
    "\n",
    "You must write an algorithm that runs in O(log n) time.\n",
    "\n",
    " \n",
    "\n",
    "Example 1:\n",
    "\n",
    "    Input: nums = [3,4,5,1,2]\n",
    "    Output: 1\n",
    "    Explanation: The original array was [1,2,3,4,5] rotated 3 times.\n",
    " \n",
    "\n",
    "Constraints:\n",
    "\n",
    "    n == nums.length\n",
    "    1 <= n <= 5000\n",
    "    -5000 <= nums[i] <= 5000\n",
    "    All the integers of nums are unique.\n",
    "    nums is sorted and rotated between 1 and n times."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "a85c6fba-6407-49d4-8d53-7a285cbccc7a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def findMin(nums):\n",
    "    l = 0\n",
    "    r = len(nums) - 1\n",
    "    while l < r-1:\n",
    "        i = (l + r)//2\n",
    "        if nums[i] > nums[r]:\n",
    "            l = i\n",
    "        else:\n",
    "            r = i\n",
    "\n",
    "    return min(nums[l], nums[r])\n",
    "\n",
    "findMin([3, 4, 5, 1, 2])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ee973a86-f82c-4477-a400-4beeb8563701",
   "metadata": {},
   "source": [
    "## [912. Sort an Array](https://leetcode.com/problems/sort-an-array/)\n",
    "\n",
    "Medium\n",
    "\n",
    "Given an array of integers nums, sort the array in ascending order and return it.\n",
    "\n",
    "You must solve the problem without using any built-in functions in O(nlog(n)) time complexity and with the smallest space complexity possible.\n",
    "\n",
    "Example 1:\n",
    "\n",
    "    Input: nums = [5,2,3,1]\n",
    "    Output: [1,2,3,5]\n",
    "    Explanation: After sorting the array, the positions of some numbers are not changed (for example, 2 and 3), while the positions of other numbers are changed (for example, 1 and 5).\n",
    "\n",
    "Constraints:\n",
    "\n",
    "    1 <= nums.length <= 5 * 10^4\n",
    "    -5 * 10^4 <= nums[i] <= 5 * 10^4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "0df40f4c-f545-4eeb-8d8c-69e5ab46fc28",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 5]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def sortArray(nums):\n",
    "    n = len(nums)\n",
    "    if n in [0, 1]:\n",
    "        return nums\n",
    "    else:\n",
    "        left = sortArray(nums[:n//2])\n",
    "        right = sortArray(nums[n//2:])\n",
    "        \n",
    "        i = j = 0\n",
    "        merged = []\n",
    "        while (i != len(left)) and (j != len(right)):\n",
    "            if left[i] < right[j]:\n",
    "                merged.append(left[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                merged.append(right[j])\n",
    "                j += 1\n",
    "                \n",
    "        if i==len(left):\n",
    "            merged += right[j:]\n",
    "        else:\n",
    "            merged += left[i:]\n",
    "    \n",
    "        return merged\n",
    "\n",
    "sortArray([5, 2, 3, 1])"
   ]
  }
 ],
 "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.12.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}