DynamicArrayIQ.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "91651f63",
   "metadata": {},
   "source": [
    "## Contains Duplicates\n",
    "\n",
    "Strategy:\n",
    "\n",
    "Two approaches to check for duplicates\n",
    "\n",
    "### Approach 1 using sorting\n",
    "\n",
    "1. Sort the array in ascending order\n",
    "2. check if the adjacent elements are same\n",
    "\n",
    "\n",
    "Time Complexity: O(n log n)  \n",
    "Space Complexity: O(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "2f2f90a1",
   "metadata": {},
   "outputs": [],
   "source": [
    "def has_duplicates(arr):\n",
    "    # Sort the array in ascending order\n",
    "    arr.sort()\n",
    "    \n",
    "    # Check adjacent elements for duplicates\n",
    "    for i in range(1, len(arr)):\n",
    "        if arr[i] == arr[i-1]:\n",
    "            return True\n",
    "    \n",
    "    return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "9472831c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "has_duplicates([1,2,3,4,5,5])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "70e42667",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "has_duplicates([10,9,1,3,4,5])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b22806c3",
   "metadata": {},
   "source": [
    "### Approach 2 using hash set\n",
    "\n",
    "1. create a hash set\n",
    "2. Loop through and add each item into hash set\n",
    "3. while adding, check if the item already exists in hash set, if yes then duplicate if no, then no duplicates\n",
    "\n",
    "Big O: \n",
    "\n",
    "Time Complexity: O(n)   \n",
    "Space Complexity: O(n)   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "a1b86da8",
   "metadata": {},
   "outputs": [],
   "source": [
    "def has_duplicates(nums):\n",
    "    seen = set()  # Create an empty set to store seen numbers\n",
    "\n",
    "    for num in nums:\n",
    "        if num in seen:  # If the number is already in the set, it's a duplicate\n",
    "            return True\n",
    "        else:\n",
    "            seen.add(num)  # Add the number to the set of seen numbers\n",
    "\n",
    "    return False  # No duplicates found\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "7fbb6b47",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Example usage\n",
    "numbers = [1, 2, 3, 4, 5, 2, 3, 4]\n",
    "has_duplicates(numbers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "ac505055",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "has_duplicates([1,8,2,4])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8ffe42c4",
   "metadata": {},
   "source": [
    "## Anagram Check\n",
    "\n",
    "Strategy:\n",
    "\n",
    "We can check if two strings are anagrams in two ways.\n",
    "\n",
    "### Approach 1 using sorting\n",
    "\n",
    "1. Remove the spaces and lower case both the string\n",
    "2. Sort the strings and compare them\n",
    "3. if both are equal, then they are anagrams\n",
    "\n",
    "#### Big O\n",
    "\n",
    "Time complexity is O(nlogn) since we are using sorting   \n",
    "Space complexity is O(n) \n",
    "\n",
    "> python uses tim sort which is a combination of merge sort and insertion sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "ad673c58",
   "metadata": {},
   "outputs": [],
   "source": [
    "def anagrams(string1, string2):\n",
    "    # Remove whitespace and convert both strings to lowercase\n",
    "    string1 = string1.replace(\" \", \"\").lower()\n",
    "    string2 = string2.replace(\" \", \"\").lower()\n",
    "\n",
    "    # Sort the characters of both strings\n",
    "    sorted_string1 = sorted(string1)\n",
    "    sorted_string2 = sorted(string2)\n",
    "\n",
    "    # Compare the sorted strings for equality\n",
    "    return sorted_string1 == sorted_string2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "a3f55072",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "anagrams(\"Clint Eastwood\", \"old west action\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "0ee22970",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "anagrams(\"aaaaa\", \"baaaa\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8a941ac2",
   "metadata": {},
   "source": [
    "### Approach 2 using hash map and counting\n",
    "\n",
    "1. Remove the spaces and lower case both the string\n",
    "2. Compare the length of the string, if length is not equal, then the are not anagrams\n",
    "3. Count occurence of each char in string1 by loading it to a hashmap key(char): value(count)\n",
    "4. Subtract the occurence of each char in String2 from the hashmap\n",
    "5. In hashmap, if all the key (char) has a count 0, then they are anagrams or else no\n",
    "\n",
    "#### Big O\n",
    "Time Complexity: O(n + m) (or simply O(n) since n >= m) where m is the counter dictionary length which will contain only unique characters\n",
    "Space Complexity: O(n + k) (since we are modifying string 1 and string 2 and storing it again)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "23645c45",
   "metadata": {},
   "outputs": [],
   "source": [
    "def anagram_hash(string1, string2):\n",
    "    # Remove whitespace and convert both strings to lowercase\n",
    "    string1 = string1.replace(\" \", \"\").lower()\n",
    "    string2 = string2.replace(\" \", \"\").lower()\n",
    "\n",
    "    # Check if the lengths of the two strings are different\n",
    "    if len(string1) != len(string2):\n",
    "        return False\n",
    "\n",
    "    # Create a dictionary to keep track of character frequencies in string1\n",
    "    counter = {}\n",
    "\n",
    "    # Count the occurrences of each letter in string1\n",
    "    for letter in string1:\n",
    "        if letter not in counter:\n",
    "            counter[letter] = 1\n",
    "        else:\n",
    "            counter[letter] += 1\n",
    "\n",
    "    # Compare the frequencies of characters in string2 with the counter dictionary\n",
    "    for letter in string2:\n",
    "        if letter not in counter:\n",
    "            return False\n",
    "        else:\n",
    "            counter[letter] -= 1\n",
    "\n",
    "    # Check if there are any non-zero frequencies in the counter dictionary\n",
    "    for k in counter:\n",
    "        if counter[k] != 0:\n",
    "            return False\n",
    "\n",
    "    # All checks passed, the strings are anagrams\n",
    "    return True\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "cdce7d16",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "anagrams(\"Clint Eastwood\", \"old west action\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "651fdbe9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "anagrams(\"aaaaa\", \"baaaa\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f4ff5176",
   "metadata": {},
   "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.8.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}