Find_Missing_Positive_Integer.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Getting a Different Number\n",
    "\n",
    "#### Given an array arr of unique nonnegative integers, implement a function getDifferentNumber that finds the smallest nonnegative integer that is NOT in the array.\n",
    "\n",
    "#### Even if your programming language of choice doesn’t have that restriction (like Python), assume that the maximum value an integer can have is MAX_INT = 2^31-1. So, for instance, the operation MAX_INT + 1 would be undefined in our case.\n",
    "\n",
    "#### Your algorithm should be efficient, both from a time and a space complexity perspectives.\n",
    "\n",
    "#### Solve first for the case when you’re NOT allowed to modify the input arr. If successful and still have time, see if you can come up with an algorithm with an improved space complexity when modifying arr is allowed. Do so without trading off the time complexity.\n",
    "\n",
    "#### Analyze the time and space complexities of your algorithm.\n",
    "\n",
    "#### Example:\n",
    "\n",
    "#### input:  arr = [0, 1, 2, 3]\n",
    "\n",
    "#### output: 4 \n",
    "#### Constraints:\n",
    "\n",
    "#### [time limit] 5000ms\n",
    "\n",
    "#### [input] array.integer arr\n",
    "\n",
    "#### 1 ≤ arr.length ≤ MAX_INT\n",
    "#### 0 ≤ arr[i] ≤ MAX_INT for every i, 0 ≤ i < MAX_INT\n",
    "#### [output] integer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def find(arr):\n",
    "    sorted_arr = sorted(arr)\n",
    "    for _ in range(1,sorted_arr[-1]):\n",
    "        if _ not in arr:\n",
    "            return _\n",
    "    return sorted_arr[-1]+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find([0, 1, 2, 3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def find2(arr):\n",
    "    max_value = -1\n",
    "    value_set = set()\n",
    "    for _ in arr:\n",
    "        value_set.add(_)\n",
    "        if _ > max_value:\n",
    "            max_value = _\n",
    "    for _ in range(1,_+1):\n",
    "        if _ not in value_set:\n",
    "            return _\n",
    "    return _+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find2([-1,1,2,4])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "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.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}