Code_Craft_count_smaller_elements_to_right.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyODsEWW+cTdzBRpZa+irJ6s",
      "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/walkerjian/DailyCode/blob/main/Code_Craft_count_smaller_elements_to_right.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "##Problem:\n",
        "Given an array of integers, return a new array where each element in the new array is the number of smaller elements to the right of that element in the original input array.\n",
        "\n",
        "For example, given the array [3, 4, 9, 6, 1], return [1, 1, 2, 1, 0], since:\n",
        "\n",
        "There is 1 smaller element to the right of 3\n",
        "There is 1 smaller element to the right of 4\n",
        "There are 2 smaller elements to the right of 9\n",
        "There is 1 smaller element to the right of 6\n",
        "There are no smaller elements to the right of 1"
      ],
      "metadata": {
        "id": "2lWyrXjB8EeD"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "##Solution:\n",
        "The algorithm to find the number of smaller elements to the right of each element in an array is implemented as follows:\n",
        "\n",
        "1. **Initialize a Result Array**: A new array `counts` of the same length as the input array `nums` is created, initialized with zeros. This array will store the count of smaller elements to the right of each element in the input array.\n",
        "\n",
        "2. **Iterate Through the Array**: The main part of the algorithm involves iterating through the input array from the second-to-last element to the first element (in reverse order). The reason for starting from the end and moving backwards is that we are interested in elements to the \"right\" of the current element. The last element of the array is skipped in this loop because there are no elements to its right, so it will always have a count of 0 for smaller elements to its right (this is handled by the initialization step).\n",
        "\n",
        "3. **Count Smaller Elements for Each Element**: For each element at index `i`, the algorithm iterates through all elements to its right (from index `i+1` to the end of the array). If an element to the right is smaller than the current element, a counter (`count`) is incremented. This process essentially compares the current element with each of its right-hand neighbors to count how many of them are smaller.\n",
        "\n",
        "4. **Update the Result Array**: After counting the smaller elements to the right of the current element, the count is stored in the corresponding position of the `counts` array.\n",
        "\n",
        "5. **Handle the Last Element**: The last element of the array is automatically assigned a count of 0, as there are no elements to its right. This step is implicitly handled by the initialization of the `counts` array with zeros.\n",
        "\n",
        "6. **Return the Result Array**: Once all elements have been processed, the `counts` array, which now contains the count of smaller elements to the right of each element in the input array, is returned.\n",
        "\n",
        "This brute-force approach works well for small to medium-sized arrays but can be inefficient for very large arrays due to its quadratic time complexity, \\(O(n^2)\\), where \\(n\\) is the length of the input array. The inefficiency arises because for each element, it scans all the elements to its right, resulting in a significant number of comparisons, especially for elements towards the beginning of the array."
      ],
      "metadata": {
        "id": "jIohycTB8Hjb"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "##Implementation:\n"
      ],
      "metadata": {
        "id": "pkWuQrLB8K8H"
      }
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "id": "TIIt0l_k7Oi1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "cbfefa82-32c1-41dd-a986-95c3dd7d6f05"
      },
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[1, 1, 2, 1, 0]"
            ]
          },
          "metadata": {},
          "execution_count": 1
        }
      ],
      "source": [
        "def count_smaller_elements_to_right(nums):\n",
        "    # Initialize an array to hold the counts of smaller elements to the right\n",
        "    counts = [0] * len(nums)\n",
        "\n",
        "    # Iterate through the array from the end to the beginning\n",
        "    for i in range(len(nums) - 2, -1, -1):\n",
        "        # For each element, count how many elements to its right are smaller\n",
        "        count = 0\n",
        "        for j in range(i+1, len(nums)):\n",
        "            if nums[i] > nums[j]:\n",
        "                count += 1\n",
        "        counts[i] = count\n",
        "\n",
        "    # The last element will always have 0 smaller elements to its right\n",
        "    counts[-1] = 0\n",
        "    return counts\n",
        "\n",
        "# Example array\n",
        "nums = [3, 4, 9, 6, 1]\n",
        "count_smaller_elements_to_right(nums)\n"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "##Testing:\n",
        "Given the array `[3, 4, 9, 6, 1]`, the new array where each element is the number of smaller elements to the right of that element in the original input array is `[1, 1, 2, 1, 0]`. This matches the example provided, indicating that the function correctly calculates the desired output.\n",
        "\n",
        "- There is 1 smaller element to the right of 3\n",
        "- There is 1 smaller element to the right of 4\n",
        "- There are 2 smaller elements to the right of 9\n",
        "- There is 1 smaller element to the right of 6\n",
        "- There are no smaller elements to the right of 1\n"
      ],
      "metadata": {
        "id": "j1_1v7Jw8Sav"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def test_count_smaller_elements_to_right():\n",
        "    # Define test cases\n",
        "    test_cases = [\n",
        "        ([3, 4, 9, 6, 1], [1, 1, 2, 1, 0]),\n",
        "        ([5, 2, 6, 1], [2, 1, 1, 0]),\n",
        "        ([], []),\n",
        "        ([1], [0]),\n",
        "        ([7, 7, 7, 7], [0, 0, 0, 0]),\n",
        "        ([9, 2, 7, 3, 1], [4, 1, 2, 1, 0]),\n",
        "    ]\n",
        "\n",
        "    # Execute test cases\n",
        "    for i, (nums, expected) in enumerate(test_cases):\n",
        "        result = count_smaller_elements_to_right(nums)\n",
        "        assert result == expected, f\"Test case {i+1} failed: expected {expected}, got {result}\"\n",
        "        print(f\"Test case {i+1} passed: {nums} -> {result}\")\n",
        "\n",
        "test_count_smaller_elements_to_right()\n"
      ],
      "metadata": {
        "id": "nTlc5bxp8UOh",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 356
        },
        "outputId": "330326cc-4a7a-490a-890c-2ea238dad111"
      },
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Test case 1 passed: [3, 4, 9, 6, 1] -> [1, 1, 2, 1, 0]\n",
            "Test case 2 passed: [5, 2, 6, 1] -> [2, 1, 1, 0]\n"
          ]
        },
        {
          "output_type": "error",
          "ename": "IndexError",
          "evalue": "list assignment index out of range",
          "traceback": [
            "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
            "\u001b[0;31mIndexError\u001b[0m                                Traceback (most recent call last)",
            "\u001b[0;32m<ipython-input-2-ed8cc75db176>\u001b[0m in \u001b[0;36m<cell line: 18>\u001b[0;34m()\u001b[0m\n\u001b[1;32m     16\u001b[0m         \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34mf\"Test case {i+1} passed: {nums} -> {result}\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     17\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 18\u001b[0;31m \u001b[0mtest_count_smaller_elements_to_right\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
            "\u001b[0;32m<ipython-input-2-ed8cc75db176>\u001b[0m in \u001b[0;36mtest_count_smaller_elements_to_right\u001b[0;34m()\u001b[0m\n\u001b[1;32m     12\u001b[0m     \u001b[0;31m# Execute test cases\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     13\u001b[0m     \u001b[0;32mfor\u001b[0m \u001b[0mi\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0mnums\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mexpected\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32min\u001b[0m \u001b[0menumerate\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mtest_cases\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 14\u001b[0;31m         \u001b[0mresult\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mcount_smaller_elements_to_right\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnums\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     15\u001b[0m         \u001b[0;32massert\u001b[0m \u001b[0mresult\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0mexpected\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34mf\"Test case {i+1} failed: expected {expected}, got {result}\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     16\u001b[0m         \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34mf\"Test case {i+1} passed: {nums} -> {result}\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m<ipython-input-1-5eb3c775dc00>\u001b[0m in \u001b[0;36mcount_smaller_elements_to_right\u001b[0;34m(nums)\u001b[0m\n\u001b[1;32m     13\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m     \u001b[0;31m# The last element will always have 0 smaller elements to its right\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 15\u001b[0;31m     \u001b[0mcounts\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     16\u001b[0m     \u001b[0;32mreturn\u001b[0m \u001b[0mcounts\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     17\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;31mIndexError\u001b[0m: list assignment index out of range"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "The test harness encountered an `IndexError` when running the test case with an empty input array (`[]`). This error occurred because the code attempted to set the last element of an empty `counts` list to 0, which is invalid for an empty list.\n",
        "\n",
        "To fix this issue, let's modify the `count_smaller_elements_to_right` function to handle the case of an empty input list properly by checking if the input list is empty before attempting to set the last element of the `counts` list. I'll update the function and rerun the test harness.\n",
        "\n"
      ],
      "metadata": {
        "id": "e820tMKh_biu"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def count_smaller_elements_to_right_fixed(nums):\n",
        "    if not nums:  # Check if the list is empty\n",
        "        return []\n",
        "    # Initialize an array to hold the counts of smaller elements to the right\n",
        "    counts = [0] * len(nums)\n",
        "\n",
        "    # Iterate through the array from the end to the beginning\n",
        "    for i in range(len(nums) - 2, -1, -1):\n",
        "        # For each element, count how many elements to its right are smaller\n",
        "        count = 0\n",
        "        for j in range(i+1, len(nums)):\n",
        "            if nums[i] > nums[j]:\n",
        "                count += 1\n",
        "        counts[i] = count\n",
        "\n",
        "    # The last element will always have 0 smaller elements to its right\n",
        "    counts[-1] = 0\n",
        "    return counts\n",
        "\n",
        "# Update the test harness to use the fixed function\n",
        "def test_count_smaller_elements_to_right_fixed():\n",
        "    # Define test cases\n",
        "    test_cases = [\n",
        "        ([3, 4, 9, 6, 1], [1, 1, 2, 1, 0]),\n",
        "        ([5, 2, 6, 1], [2, 1, 1, 0]),\n",
        "        ([], []),\n",
        "        ([1], [0]),\n",
        "        ([7, 7, 7, 7], [0, 0, 0, 0]),\n",
        "        ([9, 2, 7, 3, 1], [4, 1, 2, 1, 0]),\n",
        "    ]\n",
        "\n",
        "    # Execute test cases\n",
        "    for i, (nums, expected) in enumerate(test_cases):\n",
        "        result = count_smaller_elements_to_right_fixed(nums)\n",
        "        assert result == expected, f\"Test case {i+1} failed: expected {expected}, got {result}\"\n",
        "        print(f\"Test case {i+1} passed: {nums} -> {result}\")\n",
        "\n",
        "test_count_smaller_elements_to_right_fixed()\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "jdRtkl5K_a5l",
        "outputId": "5ddf79c7-0147-41f0-d688-9cf7a1e8c5a7"
      },
      "execution_count": 3,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Test case 1 passed: [3, 4, 9, 6, 1] -> [1, 1, 2, 1, 0]\n",
            "Test case 2 passed: [5, 2, 6, 1] -> [2, 1, 1, 0]\n",
            "Test case 3 passed: [] -> []\n",
            "Test case 4 passed: [1] -> [0]\n",
            "Test case 5 passed: [7, 7, 7, 7] -> [0, 0, 0, 0]\n",
            "Test case 6 passed: [9, 2, 7, 3, 1] -> [4, 1, 2, 1, 0]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "The test harness, now using the corrected `count_smaller_elements_to_right_fixed` function, successfully passed all test cases without halting program execution. Here's a summary of the test cases covered:\n",
        "\n",
        "1. A standard case with a mix of larger and smaller elements (`[3, 4, 9, 6, 1] -> [1, 1, 2, 1, 0]`).\n",
        "2. Another standard case with different values (`[5, 2, 6, 1] -> [2, 1, 1, 0]`).\n",
        "3. An empty array case, ensuring the function can handle an empty input without errors (`[] -> []`).\n",
        "4. A single-element array case, confirming that a single element correctly results in `[0]` as there are no elements to its right.\n",
        "5. A case with all elements being equal, verifying that each element correctly calculates zero smaller elements to its right since all are equal (`[7, 7, 7, 7] -> [0, 0, 0, 0]`).\n",
        "6. A case with a descending and then ascending pattern, to test the algorithm's ability to count across a variety of patterns (`[9, 2, 7, 3, 1] -> [4, 1, 2, 1, 0]`).\n",
        "\n",
        "These tests confirm the function's ability to accurately count the number of smaller elements to the right across a variety of input scenarios, ensuring its robustness and correctness."
      ],
      "metadata": {
        "id": "bMols_bB_fXh"
      }
    }
  ]
}