Print all subarrays with 0 sum.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Given an array, print all subarrays in the array which has sum 0.\n",
    "\n",
    "Examples:\n",
    "\n",
    "Input:  arr = [6, 3, -1, -3, 4, -2, 2,\n",
    "             4, 6, -12, -7]\n",
    "Output:  \n",
    "Subarray found from Index 2 to 4\n",
    "Subarray found from Index 2 to 6          \n",
    "Subarray found from Index 5 to 6\n",
    "Subarray found from Index 6 to 9\n",
    "Subarray found from Index 0 to 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A simple solution is to consider all subarrays one by one and check if sum of every subarray is equal to 0 or not. The complexity of this solution would be O(n^2).\n",
    "\n",
    "A better approach is to use Hashing.\n",
    "\n",
    "Do following for each element in the array\n",
    "\n",
    "Maintain sum of elements encountered so far in a variable (say sum).\n",
    "If current sum is 0, we found a subarray starting from index 0 and ending at index current index\n",
    "Check if current sum exists in the hash table or not.\n",
    "If current sum exists in the hash table, that means we have subarray(s) present with 0 sum that ends at current index.\n",
    "Insert current sum into the hash tabl"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[-1, -3, 4]\n",
      "[-1, -3, 4, -2, 2]\n",
      "[-2, 2]\n",
      "[2, 4, 6, -12]\n",
      "[6, 3, -1, -3, 4, -2, 2, 4, 6, -12, -7]\n"
     ]
    }
   ],
   "source": [
    "arr = [6, 3, -1, -3, 4, -2, 2, 4, 6, -12, -7]\n",
    "n = len(arr)\n",
    "sumdict = {}\n",
    "temp_sum=0\n",
    "for i in range(n):\n",
    "    temp_sum+=arr[i]\n",
    "    sumdict[temp_sum] = sumdict.get(temp_sum,[])+[i]\n",
    "# for key,value in enumerate(sumdict):\n",
    "for key in sumdict.keys():\n",
    "    if key==0:\n",
    "        temparr = sumdict[key]\n",
    "        for i in range(len(temparr)):\n",
    "            print(arr[0:temparr[i]+1])\n",
    "            for j in range(i+1,len(temparr)):\n",
    "                print(arr[temparr[i]+1:temparr[j]+1])\n",
    "    elif len(sumdict[key])>1:\n",
    "        temparr = sumdict[key]\n",
    "        for i in range(len(temparr)):\n",
    "#             print(arr[0:temparr[i]+1])\n",
    "            for j in range(i+1,len(temparr)):\n",
    "                print(arr[temparr[i]+1:temparr[j]+1])\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}