Smallest_Difference.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Smallest Difference",
      "provenance": [],
      "authorship_tag": "ABX9TyOgpL1uo0OqKpNHCuesumX9",
      "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/saima8/DS-and-Algo/blob/main/Smallest_Difference.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qcgo_dPdrbDH"
      },
      "source": [
        "# arrayOne = [-1, 5, 10, 20, 28, 3]\n",
        "# arrayTwo = [26, 134, 135, 15, 17]\n",
        "\n",
        "# arrayOne.sort()\n",
        "# arrayTwo.sort()\n",
        "\n",
        "# oneLeft = 0\n",
        "# twoLeft = len(arrayTwo) - 1\n",
        "# minimum = [arrayOne[0]]\n",
        "\n",
        "# while oneLeft < twoLeft:\n",
        "#   subtract = abs(oneleft - twoleft)\n",
        "#   if subtract < minimum:\n",
        "#     minimum = subtract\n",
        "#     minimum[0], minimum[1] = oneleft, twoleft\n",
        "#   else:\n",
        "#     continue\n"
      ],
      "execution_count": 1,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "amdTPX-fvggG",
        "outputId": "a055c2d9-241b-43a6-8e94-274cb43dcde0"
      },
      "source": [
        "def smallestDifference(arrayOne, arrayTwo):\n",
        "    # Write your code here.\n",
        "    arrayOne.sort()\n",
        "    arrayTwo.sort()\n",
        "    idxOne = 0\n",
        "    idxTwo = 0\n",
        "    smallest = float(\"inf\")\n",
        "    current = float(\"inf\")\n",
        "    smallestPair = []\n",
        "\n",
        "    while idxOne < len(arrayOne)and idxTwo < len(arrayTwo):\n",
        "      firstNum = arrayOne[idxOne]\n",
        "      secondNum = arrayTwo[idxTwo]\n",
        "      if firstNum < secondNum:\n",
        "        current = secondNum - firstNum\n",
        "        idxOne += 1\n",
        "      elif secondNum < firstNum:\n",
        "        current = firstNum - secondNum\n",
        "        idxTwo += 1\n",
        "      else:\n",
        "        return [firstNum, secondNum]\n",
        "      if smallest > current:\n",
        "        smallest = current\n",
        "        smallestPair = [firstNum, secondNum]\n",
        "    return smallestPair\n",
        "\n",
        "smallestDifference([-1, 5, 10, 20, 28, 3], [26, 134, 135, 15, 17])"
      ],
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[28, 26]"
            ]
          },
          "metadata": {},
          "execution_count": 6
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "gnStx1i7xxbX"
      },
      "source": [
        "Time : O(nlog(n) + mlog(m))\n",
        "\n",
        "Space : O(1)"
      ]
    }
  ]
}