5. Strings, List & 2D List.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "3470ab3d",
   "metadata": {},
   "source": [
    "# Check Palindrome\n",
    "    Given a string, determine if it is a palindrome, considering only alphanumeric characters.\n",
    "    Palindrome\n",
    "    A palindrome is a word, number, phrase, or other sequences of characters which read the same backwards and forwards.\n",
    "    Example:\n",
    "    If the input string happens to be, \"malayalam\" then as we see that this word can be read the same as forward and backwards, it is said to be a valid palindrome.\n",
    "\n",
    "    The expected output for this example will print, 'true'.\n",
    "    From that being said, you are required to return a boolean value from the function that has been asked to implement.\n",
    "    Input Format:\n",
    "    The first and only line of input contains a string without any leading and trailing spaces. All the characters in the string would be in lower case.\n",
    "    Output Format:\n",
    "    The only line of output prints either 'true' or 'false'.\n",
    "    Note:\n",
    "    You are not required to print anything. It has already been taken care of.\n",
    "    Constraints:\n",
    "    0 <= N <= 10^6\n",
    "    Where N is the length of the input string.\n",
    "\n",
    "    Time Limit: 1 second\n",
    "    Sample Input 1 :\n",
    "    abcdcba\n",
    "    Sample Output 1 :\n",
    "    true \n",
    "    Sample Input 2:\n",
    "    coding\n",
    "    Sample Output 2:\n",
    "    false"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c157e86b",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "from sys import stdin\n",
    "\n",
    "\n",
    "def isPalindrome(string) :\n",
    "    if string==string[::-1]:\n",
    "        return True\n",
    "    return False\n",
    "\n",
    "\t\n",
    "\n",
    "\n",
    "#main\n",
    "string = stdin.readline().strip();\n",
    "ans = isPalindrome(string)\n",
    "\n",
    "if ans :\n",
    "    print('true')\n",
    "else :\n",
    "    print('false')\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3e8d1b38",
   "metadata": {},
   "source": [
    "# Print all substrings\n",
    "    For a given input string(str), write a function to print all the possible substrings.\n",
    "    Substring\n",
    "    A substring is a contiguous sequence of characters within a string. \n",
    "    Example: \"cod\" is a substring of \"coding\". Whereas, \"cdng\" is not as the characters taken are not contiguous\n",
    "    Input Format:\n",
    "    The first and only line of input contains a string without any leading and trailing spaces. All the characters in the string would be in lower case.\n",
    "    Output Format:\n",
    "    Print the total number of substrings possible, where every substring is printed on a single line and hence the total number of output lines will be equal to the total number of substrings.\n",
    "    Note:\n",
    "    The order in which the substrings are printed, does not matter.\n",
    "    Constraints:\n",
    "    0 <= N <= 10^6\n",
    "    Where N is the length of the input string.\n",
    "\n",
    "    Time Limit: 1 second\n",
    "    Sample Input 1:\n",
    "    abc\n",
    "    Sample Output 1:\n",
    "    a \n",
    "    ab \n",
    "    abc \n",
    "    b \n",
    "    bc \n",
    "    c \n",
    "     Sample Input 2:\n",
    "    co\n",
    "    Sample Output 2:\n",
    "    c \n",
    "    co \n",
    "    o"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "769989b9",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "from sys import stdin\n",
    "\n",
    "\n",
    "def printSubstrings(s) :\n",
    "    for i in range(0,len(s)+1):\n",
    "        for j in range(0,len(s)+1):\n",
    "            if i!=j and j>i:\n",
    "                print(s[i:j])\n",
    "\n",
    "#main\n",
    "string = stdin.readline().strip();\n",
    "printSubstrings(string)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "36454076",
   "metadata": {},
   "source": [
    "# Swap Alternate\n",
    "    You have been given an array/list(ARR) of size N. You need to swap every pair of alternate elements in the array/list.\n",
    "    You don't need to print or return anything, just change in the input array itself.\n",
    "    Input Format :\n",
    "    The first line contains an Integer 't' which denotes the number of test cases or queries to be run. Then the test cases follow.\n",
    "\n",
    "    First line of each test case or query contains an integer 'N' representing the size of the array/list.\n",
    "\n",
    "    Second line contains 'N' single space separated integers representing the elements in the array/list.\n",
    "    Output Format :\n",
    "    For each test case, print the elements of the resulting array in a single row separated by a single space.\n",
    "\n",
    "    Output for every test case will be printed in a separate line.\n",
    "    Constraints :\n",
    "    1 <= t <= 10^2\n",
    "    0 <= N <= 10^5\n",
    "    Time Limit: 1sec\n",
    "    Sample Input 1:\n",
    "    1\n",
    "    6\n",
    "    9 3 6 12 4 32\n",
    "    Sample Output 1 :\n",
    "    3 9 12 6 32 4\n",
    "    Sample Input 2:\n",
    "    2\n",
    "    9\n",
    "    9 3 6 12 4 32 5 11 19\n",
    "    4\n",
    "    1 2 3 4\n",
    "    Sample Output 2 :\n",
    "    3 9 12 6 32 4 11 5 19 \n",
    "    2 1 4 3 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0fd58fff",
   "metadata": {},
   "outputs": [],
   "source": [
    "from sys import stdin\n",
    "\n",
    "def swapAlternate(s, n) :\n",
    "    for i in range(0,n-1,2):\n",
    "       \n",
    "        temp=s[i]\n",
    "        s[i]=s[i+1]\n",
    "        s[i+1]=temp\n",
    "    return s\n",
    "\n",
    "\n",
    "\n",
    "#Taking Input Using Fast I/O\n",
    "def takeInput() :\n",
    "    n = int(stdin.readline().rstrip())\n",
    "\n",
    "    if n == 0 :\n",
    "        return list(), 0\n",
    "\n",
    "    arr = list(map(int, stdin.readline().rstrip().split(\" \")))\n",
    "    return arr, n\n",
    "\n",
    "\n",
    "#Printing the array/list\n",
    "def printList(arr, n) :\n",
    "    for i in range(n) :\n",
    "        print(arr[i], end = \" \")\n",
    "    print()\n",
    "\n",
    "\n",
    "#main\n",
    "t = int(stdin.readline().rstrip())\n",
    "\n",
    "while t > 0 :\n",
    "    arr, n = takeInput()\n",
    "    if n != 0 :\n",
    "        swapAlternate(arr, n)\n",
    "        printList(arr, n)\n",
    "    t -= 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b8bf9a6b",
   "metadata": {},
   "source": [
    "# Array equilibrium index\n",
    "    For a given array/list(ARR) of size 'N,' find and return the 'Equilibrium Index' of the array/list.\n",
    "    Equilibrium Index of an array/list is an index 'i' such that the sum of elements at indices [0 to (i - 1)] is equal to the sum of elements at indices [(i + 1) to (N-1)]. One thing to note here is, the item at the index 'i' is not included in either part.\n",
    "    If more than one equilibrium indices are present, then the index appearing first in left to right fashion should be returned. Negative one(-1) if no such index is present.\n",
    "    Example:\n",
    "    Let's consider an array/list Arr = [2, 3, 10, -10, 4, 2, 9]  of size, N = 7.\n",
    "\n",
    "    There exist three equilibrium indices, one at 2, another at 3, and another at 5.\n",
    "\n",
    "    At index 2, the sum of all the elements to the left, [2 + 3] is 5, and the elements to its right, [-10 + 4 + 2 + 9] is also 5. Hence index 2 is an equilibrium index according to the condition we want to achieve. Mind it that we haven't included the item at index 2, which is 10, to either of the parts.\n",
    "\n",
    "    Similarly, we can see at index 3 and 5, the elements to its left sum up to 15 and 9 respectively and to the right, sum up to 15 and 9 respectively either. \n",
    "\n",
    "    Hence the answer would be 3.\n",
    "    Input Format :\n",
    "    The first line contains an Integer 't' which denotes the number of test cases or queries to be run. Then the test cases follow.\n",
    "\n",
    "    The first line of each test case or query contains an integer 'N' representing the size of the first array/list.\n",
    "\n",
    "    The second line contains 'N' single space separated integers representing the elements of the array/list\n",
    "    Output Format :\n",
    "    For each test case, print the 'Equilibrium Index'.\n",
    "\n",
    "    Output for every test case will be printed in a separate line.\n",
    "    Constraints :\n",
    "    1 <= t <= 10^2\n",
    "    0 <= N <= 10^6\n",
    "\n",
    "    Time Limit: 1 sec \n",
    "    Sample Input 1 :\n",
    "    1\n",
    "    5\n",
    "    1 4 9 3 2\n",
    "    Sample Output 1 :\n",
    "    2\n",
    "    Sample Input 2 :\n",
    "    2\n",
    "    3\n",
    "    1 4 6\n",
    "    3\n",
    "    1 -1 4\n",
    "    Sample Output 2 :\n",
    "    -1\n",
    "    \"2. Conditions and Loops.ipynb\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2971f1ed",
   "metadata": {},
   "outputs": [],
   "source": [
    "from sys import stdin\n",
    "\n",
    "def arrayEquilibriumIndex(arr, n) :\n",
    "    #Your code goes here\n",
    "\n",
    " \n",
    "    # finding the sum of whole array\n",
    "    total_sum = sum(arr)\n",
    "    leftsum = 0\n",
    "    for i, num in enumerate(arr):\n",
    "         \n",
    "        # total_sum is now right sum\n",
    "        # for index i\n",
    "        total_sum -= num\n",
    "         \n",
    "        if leftsum == total_sum:\n",
    "            return i\n",
    "        leftsum += num\n",
    "      \n",
    "      # If no equilibrium index found,\n",
    "      # then return -1\n",
    "    return -1\n",
    "     \n",
    "\n",
    "\n",
    "\n",
    "#Taking input using fast I/O method\n",
    "def takeInput() :\n",
    "    n = int(stdin.readline().strip())\n",
    "    if n == 0 :\n",
    "        return list(), 0\n",
    "\n",
    "    arr = list(map(int, stdin.readline().strip().split(\" \")))\n",
    "    return arr, n\n",
    "\n",
    "\n",
    "def printList(arr, n) : \n",
    "    for i in range(n) :\n",
    "        print(arr[i], end = \" \")\n",
    "    print()\n",
    "\n",
    "\n",
    "#main\n",
    "t = int(stdin.readline().strip())\n",
    "\n",
    "while t > 0 :\n",
    "    \n",
    "    arr, n = takeInput()\n",
    "    print(arrayEquilibriumIndex(arr, n))\n",
    "\n",
    "    t-= 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "60068077",
   "metadata": {},
   "source": [
    "# Row wise sum\n",
    "    For a given two-dimensional integer array/list of size (N x M), find and print the sum of each of the row elements in a single line, separated by a single space.\n",
    "    Input Format :\n",
    "    The first line contains an Integer 't' which denotes the number of test cases or queries to be run. Then the test cases follow.\n",
    "\n",
    "    First line of each test case or query contains two integer values, 'N' and 'M', separated by a single space. They represent the 'rows' and 'columns' respectively, for the two-dimensional array/list.\n",
    "\n",
    "    Second line onwards, the next 'N' lines or rows represent the ith row values.\n",
    "\n",
    "    Each of the ith row constitutes 'M' column values separated by a single space.\n",
    "    Output Format :\n",
    "    For each test case, print the sum of every ith row elements in a single line separated by a single space.\n",
    "\n",
    "    Output for every test case will be printed in a seperate line.\n",
    "    Constraints :\n",
    "    1 <= t <= 10^2\n",
    "    0 <= N <= 10^3\n",
    "    0 <= M <= 10^3\n",
    "    Time Limit: 1sec\n",
    "    Sample Input 1:\n",
    "    1\n",
    "    4 2 \n",
    "    1 2 \n",
    "    3 4 \n",
    "    5 6 \n",
    "    7 8\n",
    "    Sample Output 1:\n",
    "    3 7 11 15 \n",
    "    Sample Input 2:\n",
    "    2\n",
    "    2 5 \n",
    "    4 5 3 2 6 \n",
    "    7 5 3 8 9\n",
    "    4 4\n",
    "    1 2 3 4\n",
    "    9 8 7 6\n",
    "    3 4 5 6\n",
    "    -1 1 -10 5\n",
    "    Sample Output 2:\n",
    "    20 32 \n",
    "    10 30 18 -5 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "394ea3a1",
   "metadata": {},
   "outputs": [],
   "source": [
    "from sys import stdin\n",
    "\n",
    "def rowWiseSum(mat, nRows, mCols):\n",
    "    #Your code goes here\n",
    "    # print(mat,nRows,mCols)\n",
    "    for i in range(nRows):\n",
    "        sum=0\n",
    "        for j in range(mCols):\n",
    "            sum+=mat[i][j]\n",
    "        print(sum,end=' ')\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "#Taking Input Using Fast I/O\n",
    "def take2DInput() :\n",
    "    li = stdin.readline().rstrip().split(\" \")\n",
    "    nRows = int(li[0])\n",
    "    mCols = int(li[1])\n",
    "    \n",
    "    if nRows == 0 :\n",
    "        return list(), 0, 0\n",
    "    \n",
    "    mat = [list(map(int, input().strip().split(\" \"))) for row in range(nRows)]\n",
    "    return mat, nRows, mCols\n",
    "\n",
    "\n",
    "#main\n",
    "t = int(stdin.readline().rstrip())\n",
    "\n",
    "while t > 0 :\n",
    "\n",
    "    mat, nRows, mCols = take2DInput()\n",
    "    rowWiseSum(mat, nRows, mCols)\n",
    "    print()\n",
    "\n",
    "    t -= 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4d9cc71f",
   "metadata": {},
   "source": [
    "# Wave Print\n",
    "    For a given two-dimensional integer array/list of size (N x M), print the array/list in a sine wave order, i.e, print the first column top to bottom, next column bottom to top and so on.\n",
    "    Input format :\n",
    "    The first line contains an Integer 't' which denotes the number of test cases or queries to be run. Then the test cases follow.\n",
    "\n",
    "    First line of each test case or query contains two integer values, 'N' and 'M', separated by a single space. They represent the 'rows' and 'columns' respectively, for the two-dimensional array/list.\n",
    "\n",
    "    Second line onwards, the next 'N' lines or rows represent the ith row values.\n",
    "\n",
    "    Each of the ith row constitutes 'M' column values separated by a single space.\n",
    "    Output format :\n",
    "    For each test case, print the elements of the two-dimensional array/list in the sine wave order in a single line, separated by a single space.\n",
    "\n",
    "    Output for every test case will be printed in a seperate line.\n",
    "    Constraints :\n",
    "    1 <= t <= 10^2\n",
    "    0 <= N <= 10^3\n",
    "    0 <= M <= 10^3\n",
    "    Time Limit: 1sec\n",
    "    Sample Input 1:\n",
    "    1\n",
    "    3 4 \n",
    "    1  2  3  4 \n",
    "    5  6  7  8 \n",
    "    9 10 11 12\n",
    "    Sample Output 1:\n",
    "    1 5 9 10 6 2 3 7 11 12 8 4\n",
    "    Sample Input 2:\n",
    "    2\n",
    "    5 3 \n",
    "    1 2 3 \n",
    "    4 5 6 \n",
    "    7 8 9 \n",
    "    10 11 12 \n",
    "    13 14 15\n",
    "    3 3\n",
    "    10 20 30 \n",
    "    40 50 60\n",
    "    70 80 90\n",
    "    Sample Output 2:\n",
    "    1 4 7 10 13 14 11 8 5 2 3 6 9 12 15 \n",
    "    10 40 70 80 50 20 30 60 90 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ec8ea447",
   "metadata": {},
   "outputs": [],
   "source": [
    "from sys import stdin\n",
    "\n",
    "def wavePrint(mat, nRows, mCols):\n",
    "    #Your code goes here\n",
    "    j=0\n",
    "    i=0\n",
    "    num=1\n",
    "    while j<mCols:\n",
    "        if num==1:\n",
    "            i=0\n",
    "            while i<nRows:\n",
    "                print(mat[i][j],end=' ')\n",
    "                i+=1\n",
    "        else:\n",
    "            i=nRows-1\n",
    "            while i>=0:\n",
    "                print(mat[i][j],end=' ')\n",
    "                i-=1\n",
    "        j+=1\n",
    "        if num==1:\n",
    "            num=0\n",
    "        else:\n",
    "            num=1\n",
    "  \n",
    "#Taking Iput Using Fast I/O\n",
    "def take2DInput() :\n",
    "    li = stdin.readline().rstrip().split(\" \")\n",
    "    nRows = int(li[0])\n",
    "    mCols = int(li[1])\n",
    "    \n",
    "    if nRows == 0 :\n",
    "        return list(), 0, 0\n",
    "    \n",
    "    mat = [list(map(int, input().strip().split(\" \"))) for row in range(nRows)]\n",
    "    return mat, nRows, mCols\n",
    "\n",
    "\n",
    "#main\n",
    "t = int(stdin.readline().rstrip())\n",
    "\n",
    "while t > 0 :\n",
    "\n",
    "    mat, nRows, mCols = take2DInput()\n",
    "    wavePrint(mat, nRows, mCols)\n",
    "    print()\n",
    "\n",
    "    t -= 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2eb5e667",
   "metadata": {},
   "source": [
    "# Remove Consecutive Duplicates\n",
    "    For a given string(str), remove all the consecutive duplicate characters.\n",
    "    Example:\n",
    "    Input String: \"aaaa\"\n",
    "    Expected Output: \"a\"\n",
    "\n",
    "    Input String: \"aabbbcc\"\n",
    "    Expected Output: \"abc\"\n",
    "     Input Format:\n",
    "    The first and only line of input contains a string without any leading and trailing spaces. All the characters in the string would be in lower case.\n",
    "    Output Format:\n",
    "    The only line of output prints the updated string.\n",
    "    Note:\n",
    "    You are not required to print anything. It has already been taken care of.\n",
    "    Constraints:\n",
    "    0 <= N <= 10^6\n",
    "    Where N is the length of the input string.\n",
    "\n",
    "    Time Limit: 1 second\n",
    "    Sample Input 1:\n",
    "    aabccbaa\n",
    "    Sample Output 1:\n",
    "    abcba\n",
    "    Sample Input 2:\n",
    "    xxyyzxx\n",
    "    Sample Output 2:\n",
    "    xyzx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a3f25359",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "from sys import stdin\n",
    "\n",
    "def removeConsecutiveDuplicates(s) :\n",
    "    if len(s)<=1:\n",
    "        return s\n",
    "\t# Your code goes here\n",
    "    tmp=''\n",
    "    for i in range(len(s)):\n",
    "     \n",
    "        if s[i]!=s[i-1]:\n",
    "            tmp+=s[i]\n",
    "    if len(tmp)==0:\n",
    "    \ttmp+=s[0]        \n",
    "    return tmp\n",
    "\n",
    "\n",
    "\n",
    "#main\n",
    "string = stdin.readline().strip()\n",
    "\n",
    "ans = removeConsecutiveDuplicates(string)\n",
    "\n",
    "print(ans)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "807d0705",
   "metadata": {},
   "source": [
    "# Reverse Each Word\n",
    "    Aadil has been provided with a sentence in the form of a string as a function parameter. The task is to implement a function so as to print the sentence such that each word in the sentence is reversed.\n",
    "    Example:\n",
    "    Input Sentence: \"Hello, I am Aadil!\"\n",
    "    The expected output will print, \",olleH I ma !lidaA\".\n",
    "    Input Format:\n",
    "    The first and only line of input contains a string without any leading and trailing spaces. The input string represents the sentence given to Aadil.\n",
    "    Output Format:\n",
    "    The only line of output prints the sentence(string) such that each word in the sentence is reversed. \n",
    "    Constraints:\n",
    "    0 <= N <= 10^6\n",
    "    Where N is the length of the input string.\n",
    "\n",
    "    Time Limit: 1 second\n",
    "    Sample Input 1:\n",
    "    Welcome to Coding Ninjas\n",
    "    Sample Output 1:\n",
    "    emocleW ot gnidoC sajniN\n",
    "    Sample Input 2:\n",
    "    Always indent your code\n",
    "    Sample Output 2:\n",
    "    syawlA tnedni ruoy edoc"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d73644b8",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "from sys import stdin\n",
    "\n",
    "\n",
    "def reverseEachWord(string) :\n",
    "    # Your code goes here\n",
    "\n",
    "\n",
    "    stringList=string.split(' ')\n",
    "\n",
    "    resultString=''\n",
    "    for i in stringList:\n",
    "        resultString+=i[::-1]\n",
    "        resultString+=' '\n",
    "    return resultString\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "#main\n",
    "string = stdin.readline().strip()\n",
    "\n",
    "ans = reverseEachWord(string)\n",
    "\n",
    "print(ans)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "13703e80",
   "metadata": {},
   "source": [
    "# Highest Occuring Character\n",
    "    For a given a string(str), find and return the highest occurring character.\n",
    "    Example:\n",
    "    Input String: \"abcdeapapqarr\"\n",
    "    Expected Output: 'a'\n",
    "    Since 'a' has appeared four times in the string which happens to be the highest frequency character, the answer would be 'a'.\n",
    "    If there are two characters in the input string with the same frequency, return the character which comes first.\n",
    "    Consider:\n",
    "    Assume all the characters in the given string to be in lowercase always.\n",
    "    Input Format:\n",
    "    The first and only line of input contains a string without any leading and trailing spaces.\n",
    "    Output Format:\n",
    "    The only line of output prints the updated string. \n",
    "    Note:\n",
    "    You are not required to print anything explicitly. It has already been taken care of.\n",
    "    Constraints:\n",
    "    0 <= N <= 10^6\n",
    "    Where N is the length of the input string.\n",
    "\n",
    "    Time Limit: 1 second\n",
    "    Sample Input 1:\n",
    "    abdefgbabfba\n",
    "    Sample Output 1:\n",
    "    b\n",
    "    Sample Input 2:\n",
    "    xy\n",
    "    Sample Output 2:\n",
    "    x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "41c45d5a",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "from sys import stdin\n",
    "ASCII_SIZE = 256\n",
    "\n",
    "def highestOccuringChar(string) :\n",
    "\t#Your code goes here\n",
    "    count = [0] * ASCII_SIZE\n",
    " \n",
    "    # Utility variables\n",
    "    max = -1\n",
    "    c = ''\n",
    " \n",
    "    # Traversing through the string and maintaining the count of\n",
    "    # each character\n",
    "    for i in string:\n",
    "        count[ord(i)]+=1;\n",
    " \n",
    "    for i in string:\n",
    "        if max < count[ord(i)]:\n",
    "            max = count[ord(i)]\n",
    "            c = i\n",
    " \n",
    "    return c\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "#main\n",
    "string = stdin.readline().strip();\n",
    "ans = highestOccuringChar(string)\n",
    "\n",
    "print(ans)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e42f0424",
   "metadata": {},
   "source": [
    "# Arrange Numbers in the Array\n",
    "    You have been given an empty array(ARR) and its size N. The only input taken from the user will be N and you need not worry about the array.\n",
    "    Your task is to populate the array using the integer values in the range 1 to N(both inclusive) in the order - 1,3,5,.......,6,4,2.\n",
    "    Note:\n",
    "    You need not print the array. You only need to populate it.\n",
    "    Input Format :\n",
    "    The first line contains an Integer 't' which denotes the number of test cases or queries to be run. Then the test cases follow.\n",
    "\n",
    "    The first and the only line of each test case or query contains an integer 'N'.\n",
    "    Output Format :\n",
    "    For each test case, print the elements of the array/list separated by a single space.\n",
    "\n",
    "    Output for every test case will be printed in a separate line.\n",
    "    Constraints :\n",
    "    1 <= t <= 10^2\n",
    "    0 <= N <= 10^4\n",
    "\n",
    "    Time Limit: 1sec\n",
    "    Sample Input 1 :\n",
    "    1\n",
    "    6\n",
    "    Sample Output 1 :\n",
    "    1 3 5 6 4 2\n",
    "    Explanation of Sample Input 1 :\n",
    "    Since the value of N is 6, the number will be stored in the array in such a fashion that 1 will appear at 0th index, then 2 at the last index, in a similar fashion 3 is stored at index 1. Hence the array becomes 1 3 5 6 4 2.\n",
    "    Sample Input 2 :\n",
    "    2\n",
    "    9\n",
    "    3\n",
    "    Sample Output 2 :\n",
    "    1 3 5 7 9 8 6 4 2\n",
    "    1 3 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2c159507",
   "metadata": {},
   "outputs": [],
   "source": [
    "from sys import stdin\n",
    "\n",
    "def arrange(arr, n) :\n",
    "    #Your code goes here\n",
    "    j=0\n",
    "    for i in range(1,n+1):\n",
    "        if i%2!=0:\n",
    "            arr[j]=i\n",
    "            j+=1\n",
    "        else:\n",
    "            arr[n-j]=i\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "#to print the array/list\n",
    "def printList(arr, n) :\n",
    "    for i in range(n) :\n",
    "        print(arr[i], end = ' ')\n",
    "    print()\n",
    "\n",
    "\n",
    "\n",
    "#main\n",
    "t = int(stdin.readline().strip())\n",
    "\n",
    "while t > 0 :\n",
    "    n = int(stdin.readline().strip())\n",
    "    arr = n * [0]\n",
    "    arrange(arr, n)\n",
    "    printList(arr, n)\n",
    "    t -= 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f7b2c8c1",
   "metadata": {},
   "source": [
    "# Leaders in array\n",
    "    Given an integer array A of size n. Find and print all the leaders present in the input array. An array element A[i] is called Leader, if all the elements following it (i.e. present at its right) are less than or equal to A[i].\n",
    "    Print all the leader elements separated by space and in the same order they are present in the input array.\n",
    "    Input Format :\n",
    "    Line 1 : Integer n, size of array\n",
    "    Line 2 : Array A elements (separated by space)\n",
    "    Output Format :\n",
    "     leaders of array (separated by space)\n",
    "    Constraints :\n",
    "    1 <= n <= 10^6\n",
    "    Sample Input 1 :\n",
    "    6\n",
    "    3 12 34 2 0 -1\n",
    "    Sample Output 1 :\n",
    "    34 2 0 -1\n",
    "    Sample Input 2 :\n",
    "    5\n",
    "    13 17 5 4 6\n",
    "    Sample Output 2 :\n",
    "    17 6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c54fa598",
   "metadata": {},
   "outputs": [],
   "source": [
    "## Read input as specified in the question.\n",
    "## Print output as specified in the question.\n",
    "def printLeaders(arr,n):\n",
    "     \n",
    "    answer = []     \n",
    "\n",
    "    for i in range(n):\n",
    "        for j in range(i+1, n):\n",
    "            # If outer loop picked element is less than inner loop element.\n",
    "            if(elements[i] < elements[j]):\n",
    "                break\n",
    "        else:\n",
    "            answer.append(elements[i])\n",
    "\n",
    "    return answer\n",
    " \n",
    "def takeInput():\n",
    "    n = int(input())\n",
    "    elements = list(map(int, input().strip().split(\" \")))\n",
    "\n",
    "    return n, elements\n",
    "\n",
    "# Main.\n",
    "\n",
    "n, elements = takeInput()\n",
    "answer = printLeaders(elements, n)\n",
    "for ans in answer:\n",
    "        print(ans, end=\" \")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c1f04e5d",
   "metadata": {},
   "source": [
    "# Maximise the sum\n",
    "    Given 2 sorted arrays (in increasing order), find a path through the intersections that produces maximum sum and return the maximum sum.\n",
    "    That is, we can switch from one array to another array only at common elements.\n",
    "    If no intersection element is present, we need to take sum of all elements from the array with greater sum.\n",
    "    Input Format :\n",
    "     Line 1 : An integer M i.e. size of first array\n",
    "     Line 2 : M integers which are elements of first array, separated by spaces\n",
    "     Line 3 : An integer N i.e. size of second array\n",
    "     Line 4 : N integers which are elements of second array, separated by spaces\n",
    "    Output Format :\n",
    "    Maximum sum value\n",
    "    Constraints :\n",
    "    1 <= M, N <= 10^6\n",
    "    Sample Input :\n",
    "    6\n",
    "    1 5 10 15 20 25\n",
    "    5\n",
    "    2 4 5 9 15\n",
    "    Sample Output :\n",
    "    81\n",
    "    Explanation :\n",
    "    We start from array 2 and take sum till 5 (sum = 11). Then we'll switch to array at element 10 and take till 15. So sum = 36. Now, no elements left in array after 15, so we'll continue in array 1. Hence sum is 81"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "be1f338f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def maxPathSum(ar1, ar2, m, n):\n",
    "\n",
    "    i, j = 0, 0\n",
    " \n",
    " \n",
    "    result, sum1, sum2 = 0, 0, 0\n",
    " \n",
    "   \n",
    "    while (i < m and j < n):\n",
    " \n",
    "   \n",
    "        if ar1[i] < ar2[j]:\n",
    "            sum1 += ar1[i]\n",
    "            i += 1\n",
    " \n",
    "       \n",
    "        elif ar1[i] > ar2[j]:\n",
    "            sum2 += ar2[j]\n",
    "            j += 1\n",
    " \n",
    "        else:   \n",
    " \n",
    "            \n",
    "            result += max(sum1, sum2) +ar1[i]\n",
    "           \n",
    "            sum1 = 0\n",
    "            sum2 = 0\n",
    "           \n",
    "            i +=1\n",
    "            j +=1\n",
    " \n",
    "           \n",
    " \n",
    "\n",
    "    while i < m:\n",
    "        sum1 += ar1[i]\n",
    "        i += 1\n",
    "    \n",
    "    while j < n:\n",
    "        sum2 += ar2[j]\n",
    "        j += 1\n",
    " \n",
    "   \n",
    "    result += max(sum1, sum2)\n",
    " \n",
    "    return result\n",
    " \n",
    "\n",
    "def takeInput():\n",
    "    n = int(input())\n",
    "    elements = list(map(int, input().strip().split(\" \")))\n",
    "\n",
    "    return n, elements\n",
    "\n",
    "# Main.\n",
    "\n",
    "m, arr1 = takeInput()\n",
    "n, arr2 = takeInput()\n",
    "\n",
    "print(maxPathSum(arr1, arr2, m, n))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "876393a2",
   "metadata": {},
   "source": [
    "# Largest Row or Column\n",
    "    For a given two-dimensional integer array/list of size (N x M), you need to find out which row or column has the largest sum(sum of all the elements in a row/column) amongst all the rows and columns.\n",
    "    Note :\n",
    "    If there are more than one rows/columns with maximum sum, consider the row/column that comes first. And if ith row and jth column has the same largest sum, consider the ith row as answer.\n",
    "    Input Format :\n",
    "    The first line contains an Integer 't' which denotes the number of test cases or queries to be run. Then the test cases follow.\n",
    "\n",
    "    First line of each test case or query contains two integer values, 'N' and 'M', separated by a single space. They represent the 'rows' and 'columns' respectively, for the two-dimensional array/list.\n",
    "\n",
    "    Second line onwards, the next 'N' lines or rows represent the ith row values.\n",
    "\n",
    "    Each of the ith row constitutes 'M' column values separated by a single space.\n",
    "    Output Format :\n",
    "    For each test case, If row sum is maximum, then print: \"row\" <row_index> <row_sum>\n",
    "    OR\n",
    "    If column sum is maximum, then print: \"column\" <col_index> <col_sum>\n",
    "    It will be printed in a single line separated by a single space between each piece of information.\n",
    "\n",
    "    Output for every test case will be printed in a seperate line.\n",
    "     Consider :\n",
    "    If there doesn't exist a sum at all then print \"row 0 -2147483648\", where -2147483648 or -2^31 is the smallest value for the range of Integer.\n",
    "    Constraints :\n",
    "    1 <= t <= 10^2\n",
    "    0 <= N <= 10^3\n",
    "    0 <= M <= 10^3\n",
    "    Time Limit: 1sec\n",
    "    Sample Input 1 :\n",
    "    1\n",
    "    2 2 \n",
    "    1 1 \n",
    "    1 1\n",
    "    Sample Output 1 :\n",
    "    row 0 2\n",
    "    Sample Input 2 :\n",
    "    2\n",
    "    3 3\n",
    "    3 6 9 \n",
    "    1 4 7 \n",
    "    2 8 9\n",
    "    4 2\n",
    "    1 2\n",
    "    90 100\n",
    "    3 40\n",
    "    -10 200\n",
    "    Sample Output 2 :\n",
    "    column 2 25\n",
    "    column 1 342"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e4f73ea4",
   "metadata": {},
   "outputs": [],
   "source": [
    "'''\n",
    "    In order to print two or more integers in a line separated by a single \n",
    "    space then you may consider printing it with the statement, \n",
    "\n",
    "    print(str(num1) + \" \" + str(num2))\n",
    "    Take Minimum value as MIN_VALUE = -2147483648\n",
    "\n",
    "'''\n",
    "\n",
    "from sys import stdin\n",
    "\n",
    "MIN_VALUE = -2147483648\n",
    "def findLargest(arr, nRows, mCols):\n",
    "    #Your code goes here\n",
    "    isRow = True\n",
    "    largestSum = MIN_VALUE\n",
    "    num = 0\n",
    "    for i in range(nRows):\n",
    "        rowSum = 0\n",
    "        for j in range(mCols):\n",
    "            rowSum += arr[i][j]\n",
    "        if rowSum > largestSum:\n",
    "            largestSum = rowSum\n",
    "            num = i\n",
    "    for j in range(mCols):\n",
    "        colSum = 0\n",
    "        for i in range(nRows):\n",
    "            colSum += arr[i][j]\n",
    "        if colSum > largestSum:\n",
    "            largestSum = colSum\n",
    "            num = j\n",
    "            isRow = False\n",
    "    if isRow:\n",
    "        print(\"row \"+str(num)+\" \"+str(largestSum))\n",
    "    else:\n",
    "        print(\"column \"+str(num)+\" \"+str(largestSum))\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "#Taking Input Using Fast I/O\n",
    "def take2DInput() :\n",
    "    li = stdin.readline().rstrip().split(\" \")\n",
    "    nRows = int(li[0])\n",
    "    mCols = int(li[1])\n",
    "    \n",
    "    if nRows == 0 :\n",
    "        return list(), 0, 0\n",
    "    \n",
    "    mat = [list(map(int, input().strip().split(\" \"))) for row in range(nRows)]\n",
    "    return mat, nRows, mCols\n",
    "\n",
    "\n",
    "#main\n",
    "t = int(stdin.readline().rstrip())\n",
    "\n",
    "while t > 0 :\n",
    "\n",
    "    mat, nRows, mCols = take2DInput()\n",
    "    findLargest(mat, nRows, mCols)\n",
    "\n",
    "    t -= 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ea2cd908",
   "metadata": {},
   "source": [
    "# Print Spiral\n",
    "    For a given two-dimensional integer array/list of size (N x M), print it in a spiral form. That is, you need to print in the order followed for every iteration:\n",
    "        a. First row(left to right)\n",
    "        b. Last column(top to bottom)\n",
    "    c. Last row(right to left)\n",
    "    d. First column(bottom to top)\n",
    "     Mind that every element will be printed only once.\n",
    "    Refer to the Image:\n",
    "    Spiral path of a matrix\n",
    "\n",
    "    Input format :\n",
    "    The first line contains an Integer 't' which denotes the number of test cases or queries to be run. Then the test cases follow.\n",
    "\n",
    "    First line of each test case or query contains two integer values, 'N' and 'M', separated by a single space. They represent the 'rows' and 'columns' respectively, for the two-dimensional array/list.\n",
    "\n",
    "    Second line onwards, the next 'N' lines or rows represent the ith row values.\n",
    "\n",
    "    Each of the ith row constitutes 'M' column values separated by a single space.\n",
    "    Output format :\n",
    "    For each test case, print the elements of the two-dimensional array/list in the spiral form in a single line, separated by a single space.\n",
    "\n",
    "    Output for every test case will be printed in a seperate line.\n",
    "    Constraints :\n",
    "    1 <= t <= 10^2\n",
    "    0 <= N <= 10^3\n",
    "    0 <= M <= 10^3\n",
    "    Time Limit: 1sec\n",
    "    Sample Input 1:\n",
    "    1\n",
    "    4 4 \n",
    "    1 2 3 4 \n",
    "    5 6 7 8 \n",
    "    9 10 11 12 \n",
    "    13 14 15 16\n",
    "    Sample Output 1:\n",
    "    1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10 \n",
    "    Sample Input 2:\n",
    "    2\n",
    "    3 3 \n",
    "    1 2 3 \n",
    "    4 5 6 \n",
    "    7 8 9\n",
    "    3 1\n",
    "    10\n",
    "    20\n",
    "    30\n",
    "    Sample Output 2:\n",
    "    1 2 3 6 9 8 7 4 5 \n",
    "    10 20 30 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "062e382a",
   "metadata": {},
   "outputs": [],
   "source": [
    "from sys import stdin\n",
    "\n",
    "def spiralPrint(a, m, n):\n",
    "    k = 0\n",
    "    l = 0\n",
    " \n",
    "    ''' k - starting row index\n",
    "        m - ending row index\n",
    "        l - starting column index\n",
    "        n - ending column index\n",
    "        i - iterator '''\n",
    " \n",
    "    while (k < m and l < n):\n",
    " \n",
    "        # Print the first row from\n",
    "        # the remaining rows\n",
    "        for i in range(l, n):\n",
    "            print(a[k][i], end=\" \")\n",
    " \n",
    "        k += 1\n",
    " \n",
    "        # Print the last column from\n",
    "        # the remaining columns\n",
    "        for i in range(k, m):\n",
    "            print(a[i][n - 1], end=\" \")\n",
    " \n",
    "        n -= 1\n",
    " \n",
    "        # Print the last row from\n",
    "        # the remaining rows\n",
    "        if (k < m):\n",
    " \n",
    "            for i in range(n - 1, (l - 1), -1):\n",
    "                print(a[m - 1][i], end=\" \")\n",
    " \n",
    "            m -= 1\n",
    " \n",
    "        # Print the first column from\n",
    "        # the remaining columns\n",
    "        if (l < n):\n",
    "            for i in range(m - 1, k - 1, -1):\n",
    "                print(a[i][l], end=\" \")\n",
    " \n",
    "            l += 1\n",
    "\n",
    "\n",
    "#Taking Input Using Fast I/O\n",
    "def take2DInput() :\n",
    "    li = stdin.readline().rstrip().split(\" \")\n",
    "    nRows = int(li[0])\n",
    "    mCols = int(li[1])\n",
    "    \n",
    "    if nRows == 0 :\n",
    "        return list(), 0, 0\n",
    "    \n",
    "    mat = [list(map(int, input().strip().split(\" \"))) for row in range(nRows)]\n",
    "    return mat, nRows, mCols\n",
    "\n",
    "\n",
    "#main\n",
    "t = int(stdin.readline().rstrip())\n",
    "\n",
    "while t > 0 :\n",
    "\n",
    "    mat, nRows, mCols = take2DInput()\n",
    "    spiralPrint(mat, nRows, mCols)\n",
    "    print()\n",
    "\n",
    "    t -= 1"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.10.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}