{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyPKS8ATQwYGAld9M5c891zB",
      "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/Tanu-N-Prabhu/Python/blob/master/Python%20Coding%20Interview%20Prep/Children_with_candy.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "<h1>Assigning Candies to Childrens<h1>\n",
        "\n",
        "## Problem Statement\n",
        "\n",
        "There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.\n",
        "You are giving candies to these children subjected to the following requirements:\n",
        "Each child must have at least one candy.\n",
        "Children with a higher rating get more candies than their neighbors.\n",
        "Return the minimum number of candies you need to have to distribute the candies to the children.\n",
        "\n",
        "## Example\n",
        "\n",
        "```\n",
        "Example 1:**bold text**\n",
        "Input: ratings = [1,0,2]\n",
        "Output: 5\n",
        "Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.\n",
        "\n",
        "Example 2:\n",
        "Input: ratings = [1,2,2]\n",
        "Output: 4\n",
        "Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.\n",
        "The third child gets 1 candy because it satisfies the above two conditions.\n",
        "\n",
        "Constraints:\n",
        "n == ratings.length\n",
        "1 <= n <= 2 * 104\n",
        "0 <= ratings[i] <= 2 * 104\n",
        "```\n",
        "\n",
        "## Solution"
      ],
      "metadata": {
        "id": "CpCMQv8CXrWL"
      }
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "s26tYMsXWoiD",
        "outputId": "d0e766e6-871e-411f-baad-750ba04eab12"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "5\n",
            "4\n"
          ]
        }
      ],
      "source": [
        "from typing import List\n",
        "\n",
        "class Solution:\n",
        "    def candy(self, ratings: List[int]) -> int:\n",
        "        n = len(ratings)\n",
        "        candies = [1] * n\n",
        "\n",
        "        # Iterate from left to right\n",
        "        for i in range(1, n):\n",
        "            if ratings[i] > ratings[i - 1]:\n",
        "                candies[i] = candies[i - 1] + 1\n",
        "\n",
        "        total_candies = candies[n - 1]\n",
        "\n",
        "        # Iterate from right to left and update candies\n",
        "        for i in range(n - 2, -1, -1):\n",
        "            if ratings[i] > ratings[i + 1]:\n",
        "                candies[i] = max(candies[i], candies[i + 1] + 1)\n",
        "            total_candies += candies[i]\n",
        "\n",
        "        return total_candies\n",
        "\n",
        "# Example usage\n",
        "if __name__ == \"__main__\":\n",
        "    solution = Solution()\n",
        "    ratings1 = [1, 0, 2]\n",
        "    ratings2 = [1, 2, 2]\n",
        "    print(solution.candy(ratings1))  # Expected output: 5\n",
        "    print(solution.candy(ratings2))  # Expected output: 4\n"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Credits\n",
        "\n",
        "I would like to thank [Dhirajpatra](https://github.com/dhirajpatra) for writing this piece of code. Feel free to reach him out if you have any questions about Python Programming."
      ],
      "metadata": {
        "id": "3_di5W04imv6"
      }
    }
  ]
}