{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Majority Element\n",
    "A majority element in an array A[] of size n is an element that appears more than n/2 times  \n",
    "and hence there is at most one such element\n",
    "\n",
    "[3 3 4 2 4 4 2 4 4] => 4  \n",
    "[3 3 4 2 4 4 2 4] => None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Using Dictionary: O(n) - O(Distinct(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def findMajorityElement(arr):\n",
    "    dict = {}\n",
    "    \n",
    "    for a in arr:\n",
    "        if a not in dict:\n",
    "            dict[a] = 0\n",
    "        \n",
    "        dict[a] += 1\n",
    "        if dict[a] > (len(arr) / 2):\n",
    "            return a\n",
    "        \n",
    "    return 'None'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 3, 4, 2, 4, 4, 2, 4, 4]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [3, 3, 4, 2, 4, 4, 2, 4, 4]\n",
    "arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "findMajorityElement(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 3, 4, 2, 4, 2, 4]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [3, 3, 4, 2, 4, 2, 4]\n",
    "arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'None'"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "findMajorityElement(arr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Moore's Voting Algo: O(n)\n",
    "This is a two step process.\n",
    "1. The first step gives the element that may be majority element in the array\n",
    "2. Check if the element obtained from above step is majority element\n",
    "\n",
    "Basic idea of the algorithm is if we cancel out each occurrence of an element e with all the other elements that are different from e then e will exist till end if it is a majority element"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def chooseOne(arr):\n",
    "    chosen_index = 0\n",
    "    count = 1\n",
    "    \n",
    "    for i in range(1, len(arr)):\n",
    "        if arr[chosen_index] == arr[i]:\n",
    "            count += 1\n",
    "        else:\n",
    "            count -= 1\n",
    "            \n",
    "        if count == 0:\n",
    "            chosen_index = i\n",
    "            count = 1\n",
    "    \n",
    "    return arr[chosen_index] if isMajority(arr, arr[chosen_index]) else 'None'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def isMajority(arr, chosenOne):\n",
    "    count = 0\n",
    "    \n",
    "    for a in arr:\n",
    "        if chosenOne == a:\n",
    "            count += 1\n",
    "    \n",
    "    if count > (len(arr) / 2):\n",
    "        return True\n",
    "    else:\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 3, 4, 2, 4, 4, 2, 4, 4]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [3, 3, 4, 2, 4, 4, 2, 4, 4]\n",
    "arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "chooseOne(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 3, 4, 2, 4, 2, 4]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [3, 3, 4, 2, 4, 2, 4]\n",
    "arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'None'"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "chooseOne(arr)"
   ]
  }
 ],
 "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.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}