Neetcode - Array -  Longest Consecutive Sequence.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Neetcode - Array -  Longest Consecutive Sequence.ipynb",
      "provenance": [],
      "authorship_tag": "ABX9TyOKRnFim44BaLn90qWz25WX",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/sahug/neetcode/blob/main/Neetcode%20-%20Array%20-%20%20Longest%20Consecutive%20Sequence.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Neetcode - Array -  Longest Consecutive Sequence**"
      ],
      "metadata": {
        "id": "0AgtVKj7vAti"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.\n",
        "\n",
        "You must write an algorithm that runs in O(n) time.\n",
        "\n",
        "**Example 1:**\n",
        "\n",
        "```\n",
        "Input: nums = [100,4,200,1,3,2]\n",
        "Output: 4\n",
        "Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.\n",
        "```\n",
        "\n",
        "**Example 2:**\n",
        "```\n",
        "Input: nums = [0,3,7,2,5,8,4,6,0,1]\n",
        "Output: 9\n",
        "```"
      ],
      "metadata": {
        "id": "2DXu5QJ1u3XD"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "from typing import List\n",
        "from collections import defaultdict\n",
        "class Solution:\n",
        "  \n",
        "  # O(n^2) Complexity\n",
        "  def longestSequence1(self, strs: List[int]) -> List[int]:    \n",
        "    op = []\n",
        "    for i in range(len(strs)):\n",
        "      seq = []      \n",
        "      temp = strs[i]\n",
        "      for j in range(len(strs)):        \n",
        "        if temp + j in strs:          \n",
        "          seq.append(temp + j)\n",
        "      op.append(seq)              \n",
        "    print(max(len(i) for i in op))\n",
        "\n",
        "  # O(n) Complexity\n",
        "  def longestSequence2(self, strs: List[int]) -> List[int]:    \n",
        "    numSet = set(strs)\n",
        "    longest = 0\n",
        "    \n",
        "    for n in strs:\n",
        "        # check if its the start of a sequence\n",
        "        if (n - 1) not in numSet:\n",
        "            length = 1\n",
        "            while (n + length) in numSet:\n",
        "                length += 1\n",
        "            longest = max(length, longest)\n",
        "    print(longest)"
      ],
      "metadata": {
        "id": "0iNTz4FD1bE8"
      },
      "execution_count": 69,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "solution = Solution()\n",
        "solution.longestSequence1([100,4,200,1,3,2])\n",
        "solution.longestSequence1([0,3,7,2,5,8,4,6,0,1])\n",
        "\n",
        "solution.longestSequence2([100,4,200,1,3,2])\n",
        "solution.longestSequence2([0,3,7,2,5,8,4,6,0,1])"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Vm4Xy22g18vp",
        "outputId": "25c08787-ef04-4ff4-c8eb-e690bc5a052d"
      },
      "execution_count": 70,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "4\n",
            "9\n",
            "4\n",
            "9\n"
          ]
        }
      ]
    }
  ]
}