text:
<repo_name>NRishab17/code<file_sep>/README.md
# code
all codes by rishab
<file_sep>/circularlist.py
#creating circularlist and functions
class Node:
    def __init__(self,data=None,next=None):
        self.data=data
        self.next=None

class circularlist:
    def __init__(self):
        self.head=None

    def append(self,data):
        if not self.head:
            self.head=Node(data)
            self.head.next=self.head
        else:
            newnode=Node(data)
            cur=self.head
            while cur.next!=self.head:
                cur=cur.next
            cur.next=newnode
            newnode.next=self.head
    def printelements(self):
        cur=self.head
        while cur:
            print(cur.data,end=' ')
            cur=cur.next
            if cur==self.head:
                break
    def prepend(self,data):
        newnode=Node(data)
        cur=self.head
        newnode.next=self.head
        if not self.head:
            newnode.next=newnode
        else:
            while cur.next!=self.head:
                cur=cur.next
            cur.next=newnode
        self.head=newnode
    def remove(self,key):
        if self.head.data==key:
            cur=self.head
            while cur.next!=self.head:
                cur=cur.next
            cur.next=self.head.next
            self.head=self.head.next
        if self.head==self.head.next and self.head.data==key:
            self.head=None
        else:
            cur=self.head
            prev=None
            while cur.next!=self.head:
                prev=cur
                cur=cur.next
                if cur.data==key:
                    prev.next=cur.next
                    cur=cur.next

#queue for circularlist
class circlequeue:
    def __init__(self,size):
        self.size=size
        self.front=-1
        self.rear=-1
        self.queue=[None for i in range(size)]
    def enqueue(self,data):
        if ((self.rear+1)%self.size==self.front):
            print('queue is full')
        elif self.front==-1:
            self.front=0
            self.rear=0
            self.queue[self.rear]=data
        else:
            self.rear=(self.rear+1)%self.size
            self.queue[self.rear]=data
    def dequeue(self):
        if self.front==-1:
            print('empty queue')
        elif self.front==self.rear:
            temp=self.queue[self.front]
            self.front=-1
            self.rear=-1
            return temp
        else:
            temp=self.queue[self.front]
            self.front=(self.front+1)%self.size
            return temp
'''a=circularlist()
a.append(12)
a.append(13)
a.printelements()
a.remove(12)
print('remove12')
a.printelements()
a.prepend(10)
a.printelements()
a=circlequeue(5)
a.enqueue(10)
a.enqueue(11)
a.enqueue(12)
print(a.dequeue())'''
<file_sep>/recursion.py
#print n to 1
def backprint(n):
    if n==0:
        return
    print(n)
    backprint(n-1)
#backprint(5)
#sum of n natural numbers
def naturalsum(n,s=0):
    if n==0:
        print(s)
        return
    s+=n
    naturalsum(n-1,s)
#naturalsum(2,0)
def factorial(n,fact=1):
    if n==0:
        print(fact)
        return
    fact*=n
    factorial(n-1,fact)
#factorial(2,1)
def fibannoci(a,b,n):
    if n==0:
        return
    print(a)
    fibannoci(b,a+b, n-1)
#fibannoci(0, 1, 5)
#print x^n using x^n=x*(x^n-1) stack height=n
def power(x,n):
    if x==0:
        return 0
    if n==0:
        return 1
    a=power(x, n-1)
    b=x*a
    return b
#print(power(2,5))
'''2^5=2*2^4=2*2*2^3=2*2*2*2^2=2*2*2*2*2^1=2*2*2*2*2*2^0=32'''
#print x*n using x^n=x^(n/2)*x^(n/2) stack height=logn
def powerbylog(x,n):
    if x==0:
        return 0
    if n==0:
        return 1
    if n%2==0:
        return powerbylog(x, n//2)*powerbylog(x, n//2)
    else:
        return powerbylog(x, n//2)*powerbylog(x, n//2)*x
#print(powerbylog(2,2))
'''2^5=2^2*2^2*2=4*4*2=32 as 5//2=2 and x=2
   2^4=2^2*2^2=4*4=16  as 4//2=2 and x=2'''
def towerofhanoi(n,source,destination,auxiliary):
    if n==1:
        print('move disk 1 from source',source,'to destination',destination)
        return
    towerofhanoi(n-1,source,auxiliary,destination)
    print('move disk',n,'from source',source,'to destination',destination)
    towerofhanoi(n-1,auxiliary,destination,source)
#towerofhanoi(4, 'a','b','c')

def revstring(string,index):
    if index==0:
        print(string[index] ,end='')
        return
    print(string[index],end='')
    revstring(string,index-1)
#revstring('abcd',3)
first=-1
last=-1
def getindexes(string,element,index):
    if index==len(string):
        return
    if string[index]==element:
        global first
        global last
        if first==-1:
            first=index
        else:
            last=index
    getindexes(string, element, index+1)
'''getindexes('aabbccd','a',0)
print(first)
print(last)
first returns 1st occurrence and last returns last occurrance'''
def arrayincreasing(arr,index):
    if index==len(arr)-1:
        return True
    if not arrayincreasing(arr, index+1):
        return False
    return arr[index]<arr[index+1]
'''print(arrayincreasing([1,2,3,4],0))
[1,2,3,4] is strictly increasing
[1,2,2,3] is not strictly increasing but sorted
[3,2,1] is not increasing'''
def addxatlast(count):
    newstr=''
    for i in range(count):
        newstr+='x'
    return newstr
def movextolast(string,index,count):
    if index==len(string):
        return addxatlast(count)
    if string[index]=='x':
        return movextolast(string, index+1, count+1)
    else:
         newstr=movextolast(string, index+1, count)
         return string[index]+newstr
#print(movextolast('abcd',0,0))
'''we find all x and increase count and using
addxatlast function add x to last of string
if no x in string then return string with that
last index element+newstr(which has previous elements of string)'''
def subsequences(string,index,result):
    if index==len(string):
        print(result)
        return
    #if element at that index joins
    subsequences(string, index+1, result+string[index])
    #if element at that index doesnt join
    subsequences(string, index+1, result)
#subsequences('abc',0,'')
'refer to subsequences notes'
s=[]
def removeduplicates(string,index):
    if index==len(string):
        return ''.join(s)
    if string[index] in s:
        removeduplicates(string, index+1)
    else:
        s.append(string[index])
        removeduplicates(string, index+1)
    return ''.join(s)
#print(removeduplicates('aabb',0))
'''we create s list which stores unique values of string in list
as we append those elements not in list and increase index or
increase index if already present in list'''
def findcombinations(keypad,keys,combinations,index,result):
    if index==-1:
        combinations.add(result)
        return
    digit=keys[index]
    length=len(keypad[digit])
    for i in range(length):
        findcombinations(keypad, keys, combinations, index-1,keypad[digit][i]+ result)
def findallcombinations(keypad,keys):
    if not keypad or not keys:
        return set()
    combinations=set()
    findcombinations(keypad, keys, combinations,len(keys)-1,'')
    return combinations
keypad={
        2:['a','b','c'],
        3:['d','e','f'],
        4:['g','h','i'],
        5:['j','k','l'],
        6:['m','n','o'],
        7:['p','q','r','s'],
        8:['t','u','v'],
        9:['w','x','y','z']
                                }
keys=[2,3]
#print(findallcombinations(keypad, keys))

sn=[]
global m
m=0
def uniquesubsequences(string,list1,index1,index2):
    if index1==m:
        list1[index2]=None
        temp=''.join([i for i in list1 if i])
        sn.append(temp)
        return  ' '.join(set(sn))
    else:
        list1[index2]=string[index1]
        uniquesubsequences(string, list1, index1+1, index2+1)
        uniquesubsequences(string, list1, index1+1, index2)
        return ' '.join(set(sn))
string='ggg'
m=len(string)
n=int((2**m)+1)
list1=[None for i in range(n)]
#print(uniquesubsequences(string, list1,0,0))
def permutationsofstring(string,per):
    if len(string)==0:
        print(per)
        return
    for i in range(len(string)):
        curr=string[i]
        #from abc curr stores element at i index and adds it to newchar
        newstr=string[0:i]+string[i+1:]
        permutationsofstring(newstr,per+curr)
#permutationsofstring('abc','')
''' in abc possible combinations are abc,acb,bac,bca,cab,cba
3 string character so possible combinations=3!=6
time complexity is O(n!)'''
def paths(i,j,n,m):
    if i==n-1 and j==m-1:
        return 1
    if i==n or j==m:
        return 0
    #moving down
    downpaths=paths(i+1, j, n, m)
    #move right
    rightpaths=paths(i,j+1,n,m)
    return downpaths+rightpaths
#print(paths(0,0,3,3))
''' in a maze move from (0,0) to (n,m) where  we can move
right or downward only
in our case we take n,m=3,3 total paths by logic is 6
every cell has 2 choices move right or down
but corner cell have only one choice
let our cell be at(i,j) sowe can move (i+1,j) or (i,j+1)
but at corner cell we have one option as
i becomes n-1 then move only down or j becomes m-1move only right
we recursively find paths from certain cell to get to destination
every times and find total by adding all paths'''
def placetiles(n,m):
    if n==m:
        return 2
    if n<m:
        return 1
    verticalplacements=placetiles(n-m, m)
    horizontalplacements=placetiles(n-1, m)
    return verticalplacements+horizontalplacements
#print(placetiles(4, 2))
''' place tiles of 1*m in floor in size of n*m in our case n=4,m=2
place n tiles if vertically arranged then place n-m tiles
if horizontally then place n-1
base case is when n=m then ways=2 horizontally and vertically eg:n=2,m=2
n<m then ways=1 because only horizontal eg:n=2,m=4'''
def callguests(n):
    if n<=1:
        return 1
    single=callguests(n-1)
    pairs=(n-1)*callguests(n-2)
    return single+pairs
#print(callguests(4))
'''finding no of ways in which invite n people to party in single or in pairs
eg: n=4 we have 10 ways and n=3 we have 4 ways
calling a guest single then call n-1 guests and if we pair n-1 choices then call
n-2 guests'''
def subsets(n,lists):
    if n==0:
        print(lists)
        return
    #add hoga
    lists.append(n)
    subsets(n-1,lists)
    #add nahi hoga
    lists.pop()
    subsets(n-1,lists)
#subsets(3,[])
'''print all subsets of n natural numbers eg:n=3
subset=(1,2,3),(1,2),(1,3),(2,3),(1),(2),(3),() O(2^n)'''

    <file_sep>/2d array.py
#finding element in 2d array
n=int(input('no of rows'))
m=int(input('no of columns'))
target=int(input('element to find'))
lists=[[1,4,7,11],
       [2,5,8,12],
       [3,6,9,16],
       [10,13,14,17]]
found=False
r,c=0,n-1
while r<m and c>=0:
    if lists[r][c]==target:
        found=True
        break
    if lists[r][c]>target:
        c-=1
    else:
        r+=1
if found:
    print('found')
else:
    print('not found')
#matrix multiplication
'''given 2 array of n1*n2 and n2*n3 find new matrix of order n1*n3'''
list1=[[2,4,1,2],
       [8,4,3,6],
       [1,7,9,5]]
list2=[[1,2,3],
       [4,5,6],
       [7,8,9],
       [4,5,6]]
list3=[[0,0,0],
       [0,0,0],
       [0,0,0],]
n1,n2,n3=3,4,3
for i in range(n1):
    for j in range(n3):
        for k in range(n2):
            list3[i][j]+=list1[i][k]*list2[k][j]
for i in range(n1):
    for j in range(n3):
        print(list3[i][j],end=' ')
    print()
#largest word in a sentence
inp=list(input().split())
i=maxlength=0
while i<len(inp):
    word=inp[i]
    length=len(inp[i])
    if length>maxlength:
        maxlength=length
        string=inp[i]
    i+=1
print(maxlength)
print(string)
def getbit(value,index):
    return ((value & (1<<index))!=0)
def setbit(value,index):
    return value | (1<<index)
def clearbit(value,index):
    return value & ~(1<<index)
def togglebit(value,index):
    return value ^ (1<<index)
def updatebit(n,pos,value):
    mask=~(1<<pos)
    n=n&mask
    return n | (value<<pos)
<file_sep>/graphds.py
class AdjNode:#adjacency list format
    def __init__(self, data):
        self.vertex = data
        self.next = None
# A class to represent a graph. A graph is the list of the adjacency lists. Size of the array will be the no. of the vertices "V"
class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [None] * self.V
    # Function to add an edge in an undirected graph
    def add_edge(self, src, dest):
        node = AdjNode(dest)# Adding the node to the source node
        node.next = self.graph[src]
        self.graph[src] = node
        node = AdjNode(src)# Adding the source node to the destination asit is the undirected graph
        node.next = self.graph[dest]
        self.graph[dest] = node
    def print_graph(self):
        for i in range(self.V):
            print("Adjacency list of vertex {}\n head".format(i), end="")
            temp = self.graph[i]
            while temp:
                print(" -> {}".format(temp.vertex), end="")
                temp = temp.next
            print(" \n")
V = 5
graph = Graph(V)
graph.add_edge(0, 1)
graph.add_edge(0, 4)
graph.add_edge(1, 2)
graph.add_edge(1, 3)
graph.add_edge(1, 4)
graph.add_edge(2, 3)
graph.add_edge(3, 4)
graph.print_graph()
''' 1)Adjacency Matrix: Adjacency Matrix is a 2D array of size V x V where V is the number of vertices in a graph. Let the 2D array be adj[][], a slot adj[i][j] = 1 indicates that there is an edge from vertex i to vertex j. Adjacency matrix for undirected graph is always symmetric. Adjacency Matrix is also used to represent weighted graphs. If adj[i][j] = w, then there is an edge from vertex i to vertex j with weight w.
Pros: Representation is easier to implement and follow. Removing an edge takes O(1) time. Queries like whether there is an edge from vertex ‘u’ to vertex ‘v’ are efficient and can be done O(1).
Cons: Consumes more space O(V^2). Even if the graph is sparse(contains less number of edges), it consumes the same space. Adding a vertex is O(V^2) time.
Please see this for a sample Python implementation of adjacency matrix.
2)Adjacency List: An array of lists is used. The size of the array is equal to the number of vertices. Let the array be an array[]. An entry array[i] represents the list of vertices adjacent to the ith vertex. This representation can also be used to represent a weighted graph. The weights of edges can be represented as lists of pairs. Following is the adjacency list representation of the above graph.'''
from collections import defaultdict
class Graph:#This class represents a directed graph using adjacency list representation
    def __init__(self):
        self.graph = defaultdict(list)
    def addEdge(self,u,v):
        self.graph[u].append(v)
    def BFS(self, s):
        # Mark all the vertices as not visited
        visited = [False] * (max(self.graph) + 1)
        queue = []
        # Mark the source node asvisited and enqueue it
        queue.append(s)
        visited[s] = True
        while queue: # Dequeue a vertex fromqueue and print it
            s = queue.pop(0)
            print (s, end = " ")
            # Get all adjacent vertices of thedequeued vertex s. If a adjacenthas not been visited, then mark itvisited and enqueue it
            for i in self.graph[s]:
                if visited[i] == False:
                    queue.append(i)
                    visited[i] = True
g = Graph()
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 3)
print ("Following is Breadth First Traversal (starting from vertex 2)")
g.BFS(2)
'''Breadth first search is a graph traversal algorithm that starts traversing the graph from root node and explores all the neighbouring nodes. Then, it selects the nearest node and explore all the unexplored nodes. The algorithm follows the same process for each of the nearest node until it finds the goal.The algorithm of breadth first search is given below. The algorithm starts with examining the node A and all of its neighbours. In the next step, the neighbours of the nearest node of A are explored and process continues in the further steps. The algorithm explores all neighbours of all the nodes and ensures that each node is visited exactly once and no node is visited twice.
Breadth-First Search Algorithm or BFS is the most widely utilized method
BFS is a graph traversal approach in which you start at a source node and layer by layer through the graph, analyzing the nodes directly related to the source node. Then, in BFS traversal, you must move on to the next-level neighbor nodes.
According to the BFS, you must traverse the graph in a breadthwise direction:
To begin, move horizontally and visit all the current layer's nodes.Continue to the next layer.bredth-first-search-in-graph-data-structure
Breadth-First Search uses a queue data structure to store the node and mark it as "visited" until it marks all the neighboring vertices directly related to it. The queue operates on the First In First Out (FIFO) principle, so the node's neighbors will be viewed in the order in which it inserts them in the node, starting with the node that was inserted first.'''
'''Depth first search (DFS) algorithm starts with the initial node of the graph G, and then goes to deeper and deeper until we find the goal node or the node which has no children. The algorithm, then backtracks from the dead end towards the most recent node that is yet to be completely unexplored.
The data structure which is being used in DFS is stack. The process is similar to BFS algorithm. In DFS, the edges that leads to an unvisited node are called discovery edges while the edges that leads to an already visited node are called block edges.
Algorithm:
Step 1: SET STATUS = 1 (ready state) for each node in G
Step 2: Push the starting node A on the stack and set its STATUS = 2 (waiting state)
Step 3: Repeat Steps 4 and 5 until STACK is empty
Step 4: Pop the top node N. Process it and set its STATUS = 3 (processed state)
Step 5: Push on the stack all the neighbours of N that are in the ready state (whose STATUS = 1) and set their
STATUS = 2 (waiting state) and exit'''
import numpy as np
# DFS is called recusrively untill all nodes of given graph are traversed
def DFS(vertex) :
    if visited[vertex] == None :
        print(vertex)
        visited[vertex] = 1
        for x in range(vertices) :
            if visited[x] == None and adjacency_matrix[vertex][x] == 1 :
                DFS(x)
    else :
        return
vertices = int(input("enter number of vertices present in graph :- "))
visited = np.array([None]*vertices)
adjacency_matrix = [[0,1,1,1,0,0,0],
                    [1,0,1,0,0,0,0],
                    [1,1,0,1,1,0,0],
                    [1,0,1,0,1,0,0],
                    [0,0,1,1,0,1,1],
                    [0,0,0,0,1,0,0],
                    [0,0,0,0,1,0,0]]# This adjacency matrix represents the graph shown in example above
DFS(0)# You can choose any vertex of gievn graoh as the starting vertex<file_sep>/linkedlist.py
#code for linked list and functions
class Node:
    def __init__(self,data=None,next=None):
        self.data=data
        self.next=next

class linkedlist:
    def __init__(self):
        self.head=None

    def printelements(self):
        if self.head is None:
            print('empty list')
            return
        itr=self.head
        llstr=''
        while itr:
            llstr+=str(itr.data)+'-->'
            itr=itr.next
        print(llstr)

    def length(self):
        count=0
        itr=self.head
        while itr:
            count+=1
            itr=itr.next
        return count

    def insertatbegining(self,data):
        node=Node(data,self.head)
        self.head=node

    def insertatend(self,data):
        if self.head is None:
            self.head=Node(data,None)
            return
        itr=self.head
        while itr.next:
            itr=itr.next
        itr.next=Node(data,None)

    def insertat(self,index,data):
        if index<0 or index>self.length():
            raise Exception('invalid index')
        if index==0:
            self.insertatbegining(data)
            return
        count=0
        itr=self.head
        while itr:
            if count==index-1:
                node=Node(data,itr.next)
                itr.next=node
                break
            itr=itr.next
            count+=1

    def removeat(self,index):
        if index<0 or index>self.length():
            raise Exception('invalid index')
        if index==0:
            self.head=self.head.next
            return
        count=0
        itr=self.head
        while itr:
            if count==index-1:
                itr.next=itr.next.next
                break
            itr=itr.next
            count+=1

    def insertvalues(self,list):
        self.head=None
        for i in list:
            self.insertatend(i)

    def insert_after(self,data_after,data_insert):
        if self.head is None:
            return
        if self.head.data==data_after:
            self.head.next=Node(data_insert,self.head.next)
            return
        itr=self.head
        while itr:
            if itr.data==data_after:
                itr.next=Node(data_insert,itr.next)
                break
            itr=itr.next

    def remove_by(self,value):
        if self.head is None:
            return
        if self.head.data==value:
            self.head=self.head.next

        itr=self.head
        while itr.next:
            if itr.next.data==value:
                itr.next=itr.next.next
                break
            itr=itr.next
    def reverselist(self):
        prev=None
        curr=self.head
        while curr is not None:
            next=curr.next
            curr.next=prev
            prev=curr
            curr=next
        self.head=prev
    def reverseknode(self,head,k):
        if head==None:
            return None
        curr=head
        next=None
        prev=None
        count=0
        while curr is not None and count<k:#same as reverse only apply upto k elements
            next=curr.next
            curr.next=prev
            prev=curr
            curr=next
            count+=1
        if next is not None:#next is now k+1 node pointer recursively call for list starting from curr and make rest  of list as next of first node
            head.next=self.reverseknode(next, k)
        return prev#prev is head of input list
#code for stack in linked list
class stack:
    def __init__(self):
        self.head=None
    def isempty(self):
        if self.head==None:
            return True
        else:
            return False
    def push(self,data):
        if self.head==None:
            self.head=Node(data)
        else:
            newnode=Node(data)
            newnode.next=self.head
            self.head=newnode
    def pop(self):
        if self.isempty():
            return None
        else:
            popnode=self.head
            self.head=self.head.next
            popnode.next=None
            return popnode.data
    def peek(self):
        if self.isempty():
            return None
        else:
            return self.head.data
    def display(self):
        itr=self.head
        if self.isempty():
            print('stack empty')
        else:
            while itr!=None:
                print(itr.data,'-->',end=' ')
                itr=itr.next
            return
#queue in linkedlist
class queue:
    def __init__(self):
        self.front=None
        self.rear=None
    def isempty(self):
        return self.front==None
    def enqueue(self,data):
        if self.rear==None:
            self.front=Node(data)
            self.rear=self.front
        else:
            self.rear.next=Node(data)
            self.rear=self.rear.next
    def dequeue(self):
        if self.front==None:
            return None
        else:
            val=self.front.data
            self.front=self.front.next
            return val

'''ll=linkedlist()
ll.insertvalues(['banana','mango','grapes','orange'])
ll.printelements()
ll.insert_after('banana','apple')
ll.printelements()
ll.remove_by('apple')
ll.printelements()'''
'''a=stack()
print(a.isempty())
a.push(10)
a.push(11)
a.display()
print(a.pop())
print(a.peek())'''
'''b=queue()
b.isempty()
b.enqueue(10)
b.enqueue(11)
b.enqueue(12)
print('queue front:'+str(b.front.data))
print('queue rear:'+str(b.rear.data))
print(b.dequeue())
print(b.dequeue())'''
class doublylinkedlistnode:
    def __init__(self,data,next=None,prev=None):
        self.data=data
        self.next=next
        self.prev=prev
class doublylinkedlist:
    def __init__(self):
        self.head=None
    def printelements(self):
        if self.head is None:
            print('empty list')
            return
        itr=self.head
        llstr=''
        while itr:
            llstr+=str(itr.data)+'-->'
            itr=itr.next
        print(llstr)
    def getlastnode(self):
        itr=self.head
        while itr:
            itr=itr.next
        return itr
    def backprint(self):
        if self.head is None:
            print('list is empty')
            return
        lastnode=self.getlastnode()
        itr=lastnode
        llstr=''
        while itr:
            llstr+=str(itr.data)+'-->'
            itr=itr.next
        print(llstr)
    def length(self):
        count=0
        itr=self.head
        while itr:
            count+=1
            itr=itr.next
        return count
    def insertatbegining(self,data):
        if self.head==None:
            node=doublylinkedlistnode(data,self.head,None)
            self.head=node
        else:
            node=doublylinkedlistnode(data,self.head,None)
            self.head.prev=node
            self.head=node
    def insertatend(self,data):
        if self.head==None:
            node=doublylinkedlistnode(data,self.head,None)
            self.head=node
            return
        itr=self.head
        while itr.next:
            itr=itr.next
        itr.next=doublylinkedlistnode(data,None,itr)
    def insertat(self,index,data):
        if index<0 or index>self.length():
            raise Exception('invalid index')
        if index==0:
            self.insertatbegining(data)
        count=0
        itr=self.head
        while itr:
            if count==index-1:
                node=doublylinkedlistnode(data,itr.next,itr)
                if node.next:
                    node.next.prev=node
                itr.next=node
                break
            itr=itr.next
            count+=1
    def removeat(self,index):
        if index<0 or index>self.length():
            raise Exception('invalid index')
        if index==0:
            self.head=self.head.next
            self.head.prev=None

        count=0
        itr=self.head
        while itr:
            if count==index:
                itr.prev.next=itr.next
                if itr.next:
                    itr.next.prev=itr.prev
                break
            itr=itr.next
            count+=1
    def insertvalues(self,list1):
        self.head=None
        for data in list1:
            self.insertatend(data)
'''l=doublylinkedlist()
l.insertvalues([1,2,3,4,5])
l.printelements()
l.backprint()
l.insertatbegining(10)
l.insertatend(11)
l.insertat(3,12)
l.backprint()
l.removeat(3)'''

<file_sep>/tree.py
#tree structure code
class TreeNode():
    def __init__(self,data):
        self.data=data
        self.children=[]
        self.parent=None
    def getlevel(self):
        level=0
        p=self.parent
        while p:
            level+=1
            p=p.parent
        return level
    def printtree(self):
        spaces=' '*self.getlevel()
        print(spaces+self.data)
        if self.children:
            for child in self.children:
                child.printtree()
    def addchild(self,child):
        child.parent=self
        self.children.append(child)
'''a=treenode('electronics')
laptop=treenode('laptop')
laptop.addchild(treenode('mac'))
laptop.addchild(treenode('hp'))
phone=treenode('phone')
phone.addchild(treenode('vivo'))
phone.addchild(treenode('oppo'))
a.addchild(laptop)
a.addchild(phone)
a.printtree()
print(laptop.getlevel())'''

<file_sep>/evaluations.py
'''convert expression to infex,postfix,prefix eg:4*2+3
infix:<operand><operators><operands>, ((4*2)+3)
prefix:<operators><operands><operands>, +*4 2 3
postfix:<operands><operands><operators>, 4 2* 3+'''
def prefixevaluation(s):
    stack=[]
    for c in s[::-1]:
        if c.isdigit():
            stack.append(int(c))
        else:
            o1=stack.pop()
            o2=stack.pop()
            if c=='+':
                stack.append(o1+o2)
            if c=='-':
                stack.append(o1-o2)
            if c=='*':
                stack.append(o1*o2)
            if c=='/':
                stack.append(o1//o2)
    return stack.pop()
#print(prefixevaluation('+*423'))
'''class evaluate_postfix:
    def __init__(self):
        self.items=[]
        self.size=-1
    def isEmpty(self):
        return self.items==[]
    def push(self,item):
        self.items.append(item)
        self.size+=1
    def pop(self):
        if self.isEmpty():
            return 0
        else:
            self.size-=1
            return self.items.pop()
    def seek(self):
        if self.isEmpty():
            return False
        else:
            return self.items[self.size]
    def evalute(self,expr):
        for i in expr:
            if i in '0123456789':
                self.push(i)
            else:
                op1=self.pop()
                op2=self.pop()
                result=self.cal(op2,op1,i)
                self.push(result)
        return self.pop()
    def cal(self,op2,op1,i):
        if i == '*':
            return int(op2)*int(op1)
        elif i == '/':
            return int(op2)/int(op1)
        elif i == '+':
            return int(op2)+int(op1)
        elif i == '-':
            return int(op2)-int(op1)
s=evaluate_postfix()
expr=input('enter the postfix expression')
value=s.evalute(expr)
print('the result of postfix expression',expr,'is',value)'''
class infix_to_postfix:
    precedence={'^':5,'*':4,'/':4,'+':3,'-':3,'(':2,')':1}#as certain operation have more precendence than others
    def __init__(self):
        self.items=[]
        self.size=-1
    def push(self,value):
        self.items.append(value)
        self.size+=1
    def pop(self):
        if self.isempty():
            return 0
        else:
            self.size-=1
            return self.items.pop()
    def isempty(self):
        if(self.size==-1):
            return True
        else:
            return False
    def seek(self):
        if self.isempty():
            return False
        else:
            return self.items[self.size]
    def isOperand(self,i):
        if i in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890abcdefghijklmnopqrstuvwxyz':
            return True
        else:
            return False
    def infixtopostfix (self,expr):
        postfix=""
        print('postfix expression after every iteration is:')
        for i in expr:
            if(len(expr)%2==0):
                print("Incorrect infix expr")
                return False
            elif(self.isOperand(i)):
                postfix +=i
            elif(i in '+-*/^'):
                while(len(self.items)and self.precedence[i]<=self.precedence[self.seek()]):
                    postfix+=self.pop()
                self.push(i)
            elif i == '(':
                self.push(i)
            elif i == ')':
                o=self.pop()
                while o!='(':
                    postfix +=o
                    o=self.pop()
            print(postfix)
        while len(self.items):
            if(self.seek()=='('):
                self.pop()
            else:
                postfix+=self.pop()
        return postfix
#s=infix_to_postfix()
#expr=input('enter the expression ')
#result=s.infixtopostfix(expr)
#if (result!=False):
    #print("the postfix expr of :",expr,"is",result)
    def reverse(self,expr):
        rev=""
        for i in expr:
            if i == '(':
                i=')'
            elif i == ')':
                i='('
            rev+=i
        return rev
    def infixtoprefix (self,expr):
        prefix=""
        print('prefix expression after every iteration is:')
        for i in expr:
            if(len(expr)%2==0):
                print("Incorrect infix expr")
                return False
            elif(self.isOperand(i)):
                prefix +=i
            elif(i in '+-*/^'):
                while(len(self.items)and self.precedence[i] < self.precedence[self.seek()]):
                    prefix+=self.pop()
                self.push(i)
            elif i == '(':
                self.push(i)
            elif i == ')':
                o=self.pop()
                while o!='(':
                    prefix +=o
                    o=self.pop()
            print(prefix)
                #end of for
        while len(self.items):
            if(self.seek()=='('):
                self.pop()
            else:
                prefix+=self.pop()
                print(prefix)
        return prefix
s=infix_to_postfix()
expr=input('enter the expression ')
rev=""
rev=s.reverse(expr)
result=s.infixtoprefix(rev)
if (result!=False):
    prefix=s.reverse(result)
    print("the prefix expr of :",expr,"is",prefix)
    <file_sep>/stack.py
from collections import deque

class Stack:
    def __init__(self):
        self.container = deque()
    def push(self, val):
        self.container.append(val)
    def pop(self):
        return self.container.pop()
    def peek(self):
        return self.container[-1]
    def is_empty(self):
        return len(self.container) == 0
    def size(self):
        return len(self.container)
#REVERSE STRING USING STACK
def reversestring(s):
    a=Stack()
    for ch in s:
        a.push(ch)
    rstr=''
    while a.size()!=0:
        rstr+=a.pop()
    return rstr
print(reversestring('hello bc'))
#PARANTHESIS BALANCING USING STACK'''
def is_match(ch1, ch2):
    match_dict = {
        ')': '(',
        ']': '[',
        '}': '{'
    }
    return match_dict[ch1] == ch2

def is_balanced(s):
    stack = Stack()
    for ch in s:
        if ch=='(' or ch=='{' or ch == '[':
            stack.push(ch)
        if ch==')' or ch=='}' or ch == ']':
            if stack.size()==0:
                return False
            if not is_match(ch,stack.pop()):
                return False

    return stack.size()==0

print(is_balanced('[]{}'))

        <file_sep>/heap.py
'''eg:[1,3,5,4,6,13,10,9,8,15,17]   17
                                  /     \
                               15       13
                               / \     / \
                              9   6    5 10
                             / \  / \
                            4 8   3 1
we need to build a Max-Heap from the above-given array elements. It can be clearly seen that the above complete binary tree formed does not follow the Heap property. So, the idea is to heapify the complete binary tree formed from the array in reverse level order following a top-down approach
So the idea is to find the position of the last non-leaf node and perform the heapify operation of each non-leaf node in reverse level order.
Last non-leaf node = Node at index ((n-1) - 1)/2= (n/2) - 1
Total Nodes = 11.
Last Non-leaf node index = (11/2) - 1 = 4.
Therefore, last non-leaf node = 6.
To build the heap, heapify only the nodes:
[1, 3, 5, 4, 6] in reverse order.
Heapify 6: Swap 6 and 17
Heapify 4: Swap 4 and 9
Heapify 5: Swap 13 and 5.
Heapify 3: First Swap 3 and 17, again swap 3 and 15.
Heapify 1: First Swap 1 and 17, again swap 1 and 15,
           finally swap 1 and 6.
'''
def heapify(arr, n, i):
    largest = i # Initialize largest as root
    l = 2 * i + 1
    r = 2 * i + 2
    # If left child is larger than root
    if l < n and arr[l] > arr[largest]:
        largest = l
    # If right child is larger than largest so far
    if r < n and arr[r] > arr[largest]:
        largest = r
    # If largest is not root
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        # Recursively heapify the affected sub-tree
        heapify(arr, n, largest)
def buildHeap(arr, n):
    startIdx = n // 2 - 1
    # Perform reverse level order traversal# from last non-leaf node and heapify each node
    for i in range(startIdx, -1, -1):
        heapify(arr, n, i)
def printHeap(arr, n):
    for i in range(n):
        print(arr[i], end = " ")
arr = [ 1, 3, 5, 4, 6, 13, 10, 9, 8, 15, 17 ]
buildHeap(arr, len(arr))
printHeap(arr, len(arr))
''' maxheap is binary tree where value of parent>=childvalues mapping elements of heap into arraay is trivial as node at k index has left child at index2k+1 and right child at index 2k+2
The root element will be at Arr[0]. Below table shows indexes of other nodes for the ith node, i.e., Arr[i]:
Arr[(i-1)/2] Returns the parent node.Arr[(2*i)+1] Returns the left child node.Arr[(2*i)+2] Returns the right childnode.
 '''
import sys
class MaxHeap:
    def __init__(self, maxsize):
        self.maxsize = maxsize
        self.size = 0
        self.Heap = [0] * (self.maxsize + 1)
        self.Heap[0] = sys.maxsize
        self.FRONT = 1
    # Function to return the position of  parent for the node currently at pos
    def parent(self, pos):
        return pos // 2
    # Function to return the position of# the left child for the node currently    # at pos
    def leftChild(self, pos):
        return 2 * pos
    # Function to return the position of # the right child for the node currently # at pos
    def rightChild(self, pos):
        return (2 * pos) + 1
    def isLeaf(self, pos):
        if pos >= (self.size//2) and pos <= self.size:
            return True
        return False
    # Function to swap two nodes of the heap
    def swap(self, fpos, spos):
        self.Heap[fpos], self.Heap[spos] = (self.Heap[spos], self.Heap[fpos])
    def maxHeapify(self, pos):
        # If the node is a non-leaf node and smallerthan any of its child
        if not self.isLeaf(pos):
            if (self.Heap[pos] < self.Heap[self.leftChild(pos)] or self.Heap[pos] < self.Heap[self.rightChild(pos)]):
                # Swap with the left child and heapifythe left child
                if (self.Heap[self.leftChild(pos)] > self.Heap[self.rightChild(pos)]):
                    self.swap(pos, self.leftChild(pos))
                    self.maxHeapify(self.leftChild(pos))
                # Swap with the right child and heapifythe right child
                else:
                    self.swap(pos, self.rightChild(pos))
                    self.maxHeapify(self.rightChild(pos))
    def insert(self, element):
        if self.size >= self.maxsize:
            return
        self.size += 1
        self.Heap[self.size] = element
        current = self.size
        while (self.Heap[current] > self.Heap[self.parent(current)]):
            self.swap(current, self.parent(current))
            current = self.parent(current)
    def Printheap(self):
        for i in range(1, (self.size // 2) + 1):
            print(" PARENT : " + str(self.Heap[i]) +
                  " LEFT CHILD : " + str(self.Heap[2 * i]) +
                  " RIGHT CHILD : " + str(self.Heap[2 * i + 1]))
    # Function to remove and return the maximum element from the heap
    def extractMax(self):
        popped = self.Heap[self.FRONT]
        self.Heap[self.FRONT] = self.Heap[self.size]
        self.size -= 1
        self.maxHeapify(self.FRONT)
        return popped
maxHeap = MaxHeap(15)
maxHeap.insert(5)
maxHeap.insert(3)
maxHeap.insert(17)
maxHeap.insert(10)
maxHeap.insert(84)
maxHeap.insert(19)
maxHeap.insert(6)
maxHeap.insert(22)
maxHeap.insert(9)
maxHeap.Printheap()
'''eg: we add 1 and 2 so median of this object is 1.5 as even no. of term we take average of middle values
    we add 3 to object then median is 2 as 2 is middle term of object for odd terms we take middle element as median
we add number and find median for that flow of input

'''
import heapq
class Median_Finder:
    def __init__(self):
        self.max_heap = []
        self.min_heap = []
    def add_Number(self, num):
        if not self.max_heap and not self.min_heap:#for inserting 1st element in max_heap and min_heap as their null before adding these values
            heapq.heappush(self.min_heap, num)
            return
        if not self.max_heap:#inserting into max_heap which isnt empty
            if num > self.min_heap[0]:#check if num>1st value of min value
                heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))#pop value at minheap and add it in maxheap
                heapq.heappush(self.min_heap, num)#add value to min heap
            else:
                heapq.heappush(self.max_heap, -num)
            return
        if len(self.max_heap) == len(self.min_heap):#minheap matches maxheap in length
            if num < -self.max_heap[0]:
                heapq.heappush(self.max_heap, -num)
            else:
                heapq.heappush(self.min_heap, num)
        elif len(self.max_heap) > len(self.min_heap):
            if num < -self.max_heap[0]:
                heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))
                heapq.heappush(self.max_heap, -num)
            else:
                heapq.heappush(self.min_heap, num)
        else:
            if num > self.min_heap[0]:
                heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))
                heapq.heappush(self.min_heap, num)
            else:
                heapq.heappush(self.max_heap, -num)
    def find_Median(self):
        if len(self.max_heap) == len(self.min_heap):
            return (-self.max_heap[0] + self.min_heap[0]) / 2
        elif len(self.max_heap) > len(self.min_heap):
            return -self.max_heap[0]
        else:
            return self.min_heap[0]
S = Median_Finder()
S.add_Number(1)
S.add_Number(2)
result = S.find_Median()
print(result)
S.add_Number(3)
result = S.find_Median()
print(result)
S.add_Number(4)
S.add_Number(5)
result = S.find_Median()
print(result)
li = [5, 7, 9, 1, 3]
heapq.heapify(li)
print (list(li))
# using heappush() to push elements into heap pushes 4
heapq.heappush(li,4)
print (list(li))
print (heapq.heappop(li))# using heappop() to pop smallest element
li1 = [5, 7, 9, 4, 3]
li2 = [5, 7, 9, 4, 3]
heapq.heapify(li1)
heapq.heapify(li2)
# using heappushpop() to push and pop items simultaneouslypops 2
print ("The popped item using heappushpop() is : ",end="")
print (heapq.heappushpop(li1, 2))
print(li1)
# using heapreplace() to push and pop items simultaneouslypops 3
print(li2)
print ("The popped item using heapreplace() is : ",end="")
print (heapq.heapreplace(li2, 1))
print(li2)
li1 = [6, 7, 9, 4, 3, 5, 8, 10, 1]
heapq.heapify(li1)
# using nlargest to print 3 largest numbersprints 10, 9 and 8
print("The 3 largest numbers in list are : ",heapq.nlargest(3, li1),end="")
# using nsmallest to print 3 smallest numbers prints 1, 3 and 4
print("The 3 smallest numbers in list are : ",heapq.nsmallest(3, li1),end="")
'''heapq.heappush(heap,item) : Push the value item onto the heap, maintaining the heap invariant.
heapq.heappop(heap) : Pop and return the smallest item from the heap, maintaining the heap invariant. If the heap is empty, IndexError is raised. To access the smallest item without popping it, use heap[0].
heapq.heappushpop(heap, item) : Push item on the heap, then pop and return the smallest item from the heap. The combined action runs more efficiently than heappush() followed by a separate call to heappop().
heapq.heapify(x) : Transform list x into a heap, in-place, in linear time.
heapq.merge(*iterables) : Merge multiple sorted inputs into a single sorted output (for example, merge timestamped entries from multiple log files). Returns an iterator over the sorted values.'''
<file_sep>/bst.py
#code for binarytree
class Node:
    def __init__(self,key):
        self.left=None
        self.right=None
        self.val=key
    def inorder(self):
        if self.left:
            self.left.inorder()
        print(self.val,end=' ')
        if self.right:
            self.right.inorder()
    def postorder(self):
        if self.left:
            self.left.postorder()
        if self.right:
            self.right.postorder()
        print(self.val,end=' ')
    def preorder(self):
        print(self.val,end=' ')
        if self.left:
            self.left.preorder()
        if self.right:
            self.right.preorder()
'''root=Node(1)
root.left=Node(2)
root.right=Node(3)
root.left.left=Node(4)           1
root.preorder()                 /\
print()                        2  3
root.postorder()              /
print()                      4
root.inorder()
print()'''
def printkthlevelsum(root,k):
        if root==None:
            return 0
        q=[]
        q.append(root)
        level=0
        sum=0
        flag=0
        while len(q)!=0:
            size=len(q)
            while size!=0:
                size-=1
                ptr=q[0]
                q.pop(0)
                if level==k:
                    sum+=ptr.val
                    flag=1
                else:
                    if ptr.left:
                        q.append(ptr.left)
                    if ptr.right:
                        q.append(ptr.right)
            level+=1
            if flag==1:
                break
        return sum
def printlevelorder(root):
    h=height(root)
    for i in range(1,h+1):
        printcurrentlevel(root,i)
def printcurrentlevel(root,level):
    if root is None:
        return
    if level==1:
        print(root.val,end=' ')
    elif level>1:
        printcurrentlevel(root.left, level-1)
        printcurrentlevel(root.right, level-1)
def height(root):#returns length of tree
    if root is None:#no root element so return 0
        return 0
    else:
        lheight=height(root.left)
        rheight=height(root.right)
        if lheight>rheight:
            return lheight+1
        else:
            return rheight+1
#diameter of tree is no of nodes on longest path between 2 end nodes in our case from 4-3
#diameter=max(diameter of left subtree or right subtree or longest path between leaves through root(which is height of subtrees of root))
#when 5 was added diameter became 4 as 5-4-2-1 is longer
def diameter(root):
    if root is None:
        return 0
    lheight=height(root.left)
    rheight=height(root.right)
    lwidth=diameter(root.left)
    rwidth=diameter(root.right)
    return max(lheight+rheight+1,(max(rwidth,lwidth)))
'''we add values of child nodes to parent such that parent node=parentnode value+child values root is found to be sum of all nodes ofbinary tree'''
def sumreplacement(root):
    if root==None:
        return
    sumreplacement(root.left)
    sumreplacement(root.right)
    if root.left:
        root.val+=root.left.val
    if root.right:
        root.val+=root.right.val
''' mod(left subtree height - right subtree height)<=1 is a balanced height tree'''
'''      a)        1         b)       1
                 /\                / \
                2  3              2   3
             /                  /
            4                   4
                                \
                                5
in a) 4 is child so is balanced,2 has left subtree only abs(lh-rh)=1, 3 is child node so balanced,1 has 2 subtree lh=2 and rh=1 so abs(lh-rh)=1
in b) 5 is child so balanced,4 has right subtree so abs(lh-rh)=abs(0-1)=1,2 has left subtree so abs(lh-rh)=abs(2-0)=2 so unbalanced'''

def balancedheighttree(root):
    if root==None:
        return True
    if balancedheighttree(root.left)==False:
        return False
    if balancedheighttree(root.right)==False:
        return False
    lh=height(root.left)
    rh=height(root.right)
    if abs(lh-rh)<=1:
        return True
    else:
       return False
#root=Node(1)
#root.left=Node(2)
#root.right=Node(3)
#root.left.left=Node(4)
#root.left.left.right=Node(5)     1                1
#root.preorder()                 /\                / \
#print()                        2  3              2   3
#root.postorder()              /                  /
#print()                      4                   4
#root.inorder()                                    \
#print()                                            5
'''we try to print elements of tree when viewed from rightside
eg:  a)  1          b)   1
        / \           / \
        2  3         2   3
        /            / \
        4           4  5
a)1 3 4 are visisble from right side so these areprinted
b)1 3 5 are visisble from side as 4 is hided by 5 on viewing from right side
we declare maxlevel to keep maxlevel for each recursion(as a list)

rot is none is base case Whenever we see a node whose level is more than maximum level so far, we print the node because this is the last node in its level
we call right side of subtree first in recursion then left as right element can hide left element'''
class Node:
    def __init__(self,data):
        self.val=data
        self.left=None
        self.right=None
def rightViewUtil(root, level, max_level):
    if root is None:
        return
    if (max_level[0] < level):
        print (root.val)
        max_level[0] = level
    rightViewUtil(root.right, level+1, max_level)
    rightViewUtil(root.left, level+1, max_level)
def rightView(root):
    max_level = [0]
    rightViewUtil(root, 1, max_level)
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.right = Node(5)
root.left.left=Node(4)
rightView(root)
def leftViewUtil(root, level, max_level):
    # Base Case
    if root is None:
        return
    # If this is the first node of its level
    if (max_level[0] < level):
        print(root.val)
        max_level[0] = level
    # Recur for left and right subtree
    leftViewUtil(root.left, level + 1, max_level)
    leftViewUtil(root.right, level + 1, max_level)
def leftView(root):
    max_level = [0]
    leftViewUtil(root, 1, max_level)
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.right = Node(5)
root.left.left=Node(4)
leftView(root)
''' we print elements of tree when viewed from left side so left side elements hide right subtree if not rightsubtree is print
as soon as 1st element is found of its level we print it and set new max level then itrerate through left tree first then right tree '''
def pathToNode(root, path, k):
    # base case handling
    if root is None:
        return False
     # append the node value in path
    path.append(root.val)
    # See if the k is same as root's data
    if root.val== k :
        return True
    # Check if k is found in left or right
    # sub-tree
    if ((root.left != None and pathToNode(root.left, path, k)) or
            (root.right!= None and pathToNode(root.right, path, k))):
        return True
    # If not present in subtree rooted with root,
    # remove root from path and return False
    path.pop()
    return False
def distance(root, data1, data2):
    if root:# store path corresponding to node: data1,data2
        path1 = []
        pathToNode(root, path1, data1)
        path2 = []
        pathToNode(root, path2, data2)
        # iterate through the paths to find the
        # common path length
        i=0
        while i<len(path1) and i<len(path2):
            # get out as soon as the path differs
            # or any path's length get exhausted
            if path1[i] != path2[i]:
                break
            i = i+1
         # get the path length by deducting the
        # intersecting path length (or till LowestCommonAncestor)
        return (len(path1)+len(path2)-2*i)#we subtract 2*i as commonancestor is repeated in counting path of 2 points
    else:
        return 0
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.right = Node(5)
root.left.left=Node(4)
print(distance(root, 3, 2))
'''       b)   1
              / \
             2   3
            / \
           4  5
we try to print shortest distance between given 2 points distance=no.of edges between 2 points
eg: from 5 to 3 we go to 2,1,3 to reach three so distance is 3 and its shortest distance
The distance between two nodes can be obtained
Dist(n1, n2) = Dist(root, n1) + Dist(root, n2) - 2*Dist(root, lca)
we store path corresponding to give node and call pathtonode function
in pathtonode we try to find in which subtree node value our pathvalue=k value
then in distance function get out as soon as the path differor  or any path's length get exhausted
as soon as path1[i]!=path2[i] break the loop and return Dist(root, n1) + Dist(root, n2) - 2*Dist(root, lca) '''
# Function to convert binary tree into
# linked list by altering the right node
# and making left node point to None
def flatten(root):
    # Base condition- return if root is None
    # or if it is a leaf node
    if (root == None or root.left == None and
                        root.right == None):
        return
    # If root.left exists then we have
    # to make it root.right
    if (root.left != None):
        # Move left recursively
        flatten(root.left)
        # Store the node root.right
        tmpRight = root.right
        root.right = root.left
        root.left = None
        # Find the position to insert
        # the stored value
        t = root.right
        while (t.right != None):
            t = t.right
        # Insert the stored value
        t.right = tmpRight
    # Now call the same function
    # for root.right
    flatten(root.right)
def inorder(root):#to print inorder way
    if (root == None):
        return
    inorder(root.left)
    print(root.val, end = ' ')
    inorder(root.right)
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.right.right = Node(5)
root.right.left=Node(4)
inorder(root)
flatten(root)
print()
inorder(root)
'''            1           1
              / \          \
             2   3          2
             / \              \             flatten version
            4  5               4
                               \
                                5
                                 \
                                 3
binary tree flatten in linked list(not using other ds) such that left node point to none and right points to next node
Base condition- return if root is None or if it is a leaf node
we covert all left subtree nodes to right side elements then right side elements get pushed down as left occupy those positions'''
def printkDistanceNodeDown(root, k):
    # Base Case
    if root is None or k< 0 :
        return
    # If we reach a k distant node, print it
    if k == 0 :
        print (root.val)
        return
    # Recur for left and right subtree
    printkDistanceNodeDown(root.left, k-1)
    printkDistanceNodeDown(root.right, k-1)
# Prints all nodes at distance k from a given target node The k distant nodes may be upward or downward. This function
# returns distance of root from target node, it returns -1
# if target node is not present in tree rooted with root
def printkDistanceNode(root, target, k):
    # Base Case 1 : IF tree is empty return -1
    if root is None:
        return -1
    # If target is same as root. Use the downward function
    # to print all nodes at distance k in subtree rooted with
    # target or root
    if root == target:
        printkDistanceNodeDown(root, k)
        return 0
    # Recur for left subtree
    dl = printkDistanceNode(root.left, target, k)
    # Check if target node was found in left subtree
    if dl != -1:
        # If root is at distance k from target, print root
        # Note: dl is distance of root's left child
        # from target
        if dl +1 == k :
            print (root.val)
        # Else go to right subtreee and print all k-dl-2
        # distant nodes
        # Note: that the right child is 2 edges away from
        # left chlid
        else:
            printkDistanceNodeDown(root.right, k-dl-2)
        # Add 1 to the distance and return value for
        # for parent calls
        return 1 + dl
    # MIRROR OF ABOVE CODE FOR RIGHT SUBTREE
    # Note that we reach here only when node was not found
    # in left subtree
    dr = printkDistanceNode(root.right, target, k)
    if dr != -1:
        if (dr+1 == k):
            print (root.val)
        else:
            printkDistanceNodeDown(root.left, k-dr-2)
        return 1 + dr
    # If target was neither present in left nor in right subtree
    return -1
root = Node(20)
root.left = Node(8)
root.right = Node(22)
root.left.left = Node(4)
root.left.right = Node(12)
root.left.right.left = Node(10)
root.left.right.right = Node(14)
printkDistanceNode(root,root.left.right, 2)
'''we print all node k given distance from target node
There are two types of nodes to be considered.
1) Nodes in the subtree rooted with target node. For example, if the target node is 8 and k is 2, then such nodes are 10 and 14.
2) Other nodes, may be an ancestor of target, or a node in some other subtree. For target node 8 and k is 2, the node 22 comes in this category.
Finding the first type of nodes is easy to implement. Just traverse subtrees rooted with the target node and decrement k in recursive call. When the k becomes 0, print the node currently being traversed (See this for more details). Here we call the function as printkdistanceNodeDown().
How to find nodes of second type? For the output nodes not lying in the subtree with the target node as the root, we must go through all ancestors. For every ancestor, we find its distance from target node, let the distance be d, now we go to other subtree (if target was found in left subtree, then we go to right subtree and vice versa) of the ancestor and find all nodes at k-d distance from the ancestor.'''
INT_MIN=-2**32
def maxPathSumUtil(root, res):
    # Base Case
    if root is None:
        return 0
    # Find maximumsum in left and righ subtree. Also
    # find maximum root to leaf sums in left and right
    # subtrees ans store them in ls and rs
    ls = maxPathSumUtil(root.left, res)
    rs = maxPathSumUtil(root.right, res)
    # If both left and right children exist
    if root.left is not None and root.right is not None:
        # update result if needed
        res[0] = max(res[0], ls + rs + root.val)
        # Return maximum possible value for root being
        # on one side
        return max(ls, rs) + root.val
    # If any of the two children is empty, return
    # root sum for root being on one side
    if root.left is None:
        return rs + root.val
    else:
        return ls + root.val
# The main function which returns sum of the maximum
# sum path betwee ntwo leaves. THis function mainly
# uses maxPathSumUtil()
def maxPathSum(root):
    res = [INT_MIN]
    maxPathSumUtil(root, res)
    return res[0]
root = Node(1)
root.left=Node(2)
root.right=Node(-3)
root.left.left=Node(4)
root.left.right=Node(10)
print(maxPathSum(root))
# Finds the path from root node to given root of the tree.
# Stores the path in a list path[], returns true if path
# exists otherwise false
def findPath( root, path, k):
    # Baes Case
    if root is None:
        return False
    # Store this node is path vector. The node will be
    # removed if not in path from root to k
    path.append(root.val)
    # See if the k is same as root's key
    if root.val== k :
        return True
    # Check if k is found in left or right sub-tree
    if ((root.left != None and findPath(root.left, path, k)) or
            (root.right!= None and findPath(root.right, path, k))):
        return True
    # If not present in subtree rooted with root, remove
    # root from path and return False
    path.pop()
    return False
# Returns LCA if node n1 , n2 are present in the given
# binary tre otherwise return -1
def findLCA(root, n1, n2):
    # To store paths to n1 and n2 fromthe root
    path1 = []
    path2 = []
    # Find paths from root to n1 and root to n2.
    # If either n1 or n2 is not present , return -1
    if (not findPath(root, path1, n1) or not findPath(root, path2, n2)):
        return -1
    # Compare the paths to get the first different value
    i = 0
    while(i < len(path1) and i < len(path2)):
        if path1[i] != path2[i]:
            break
        i += 1
    return path1[i-1]
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print ("LCA(4, 5) = %d" %(findLCA(root, 4, 5,)))
# function to convert sorted array to a
# balanced BST
# input : sorted array of integers
# output: root node of balanced BST
def sortedArrayToBST(arr):
    if not arr:
        return None
    # find middle
    mid = (len(arr)) // 2
    # make the middle element the root
    root = Node(arr[mid])
    # left subtree of root has all
    # values <arr[mid]
    root.left = sortedArrayToBST(arr[:mid])
    # right subtree of root has all
    # values >arr[mid]
    root.right = sortedArrayToBST(arr[mid+1:])
    return root
def preOrder(node):
    if not node:
        return
    print (node.val)
    preOrder(node.left)
    preOrder(node.right)
"""Constructed balanced BST is
    4
/ \
2 6
/ \ / \
1 3 5 7"""
arr = [1, 2, 3, 4, 5, 6, 7]
root = sortedArrayToBST(arr)
preOrder(root)
def zizagtraversal(root):
    # Base Case
    if root is None:
        return
    # Create two stacks to store current
    # and next level
    currentLevel = []
    nextLevel = []
    # if ltr is true push nodes from
    # left to right otherwise from
    # right to left
    ltr = True
    # append root to currentlevel stack
    currentLevel.append(root)
    # Check if stack is empty
    while len(currentLevel) > 0:
        # pop from stack
        temp = currentLevel.pop(-1)
        # print the data
        print(temp.val, " ", end="")
        if ltr:
            # if ltr is true push left
            # before right
            if temp.left:
                nextLevel.append(temp.left)
            if temp.right:
                nextLevel.append(temp.right)
        else:
            # else push right before left
            if temp.right:
                nextLevel.append(temp.right)
            if temp.left:
                nextLevel.append(temp.left)
        if len(currentLevel) == 0:
            # reverse ltr to push node in
            # opposite order
            ltr = not ltr
            # swapping of stacks
            currentLevel, nextLevel = nextLevel, currentLevel
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(7)
root.left.right = Node(6)
root.right.left = Node(5)
root.right.right = Node(4)
zizagtraversal(root)
def isIdentical(root1, root2) :
    # Check if both the trees are empty
    if (root1 == None and root2 == None) :
        return 1
    # If any one of the tree is non-empty
    # and other is empty, return false
    elif (root1 != None and root2 == None) :
        return 0
    elif (root1 == None and root2 != None) :
        return 0
    else: # Check if current data of both trees
          # equal and recursively check for left
          # and right subtrees
        if (root1.val == root2.val and
            isIdentical(root1.left, root2.left)
            and isIdentical(root1.right, root2.right)) :
            return 1
        else:
            return 0
root1 = Node(5)
root1.left = Node(3)
root1.right = Node(8)
root1.left.left = Node(2)
root1.left.right = Node(4)
root2 = Node(5)
root2.left = Node(3)
root2.right = Node(8)
root2.left.left = Node(2)
root2.left.right = Node(4)
if (isIdentical(root1, root2)):
    print("Both BSTs are identical")
else:
    print("BSTs are not identical")

# Returns size of the largest BST subtree
# in a Binary Tree (efficient version).
def largestBST(node):
    # Set the initial values for calling
    # largestBSTUtil()
    Min = [999999999999] # For minimum value in right subtree
    Max = [-999999999999] # For maximum value in left subtree
    max_size = [0] # For size of the largest BST
    is_bst = [0]
    largestBSTUtil(node, Min, Max,
                         max_size, is_bst)
    return max_size[0]
# largestBSTUtil() updates max_size_ref[0]
# for the size of the largest BST subtree.
# Also, if the tree rooted with node is
# non-empty and a BST, then returns size of
# the tree. Otherwise returns 0.
def largestBSTUtil(node, min_ref, max_ref,
                         max_size_ref, is_bst_ref):
    # Base Case
    if node == None:
        is_bst_ref[0] = 1 # An empty tree is BST
        return 0 # Size of the BST is 0
    Min = 999999999999
    # A flag variable for left subtree property
    # i.e., max(root.left) < root.data
    left_flag = False
    # A flag variable for right subtree property
    # i.e., min(root.right) > root.data
    right_flag = False
    ls, rs = 0, 0    # To store sizes of left and right subtree
    # Following tasks are done by recursive
    # call for left subtree
    # a) Get the maximum value in left subtree
    #   (Stored in max_ref[0])
    # b) Check whether Left Subtree is BST or
    #    not (Stored in is_bst_ref[0])
    # c) Get the size of maximum size BST in
    #    left subtree (updates max_size[0])
    max_ref[0] = -999999999999
    ls = largestBSTUtil(node.left, min_ref, max_ref,
                           max_size_ref, is_bst_ref)
    if is_bst_ref[0] == 1 and node.val > max_ref[0]:
        left_flag = True
    # Before updating min_ref[0], store the min
    # value in left subtree. So that we have the
    # correct minimum value for this subtree
    Min = min_ref[0]
    # The following recursive call does similar
    # (similar to left subtree) task for right subtree
    min_ref[0] = 999999999999
    rs = largestBSTUtil(node.right, min_ref, max_ref,
                        max_size_ref, is_bst_ref)
    if is_bst_ref[0] == 1 and node.val < min_ref[0]:
        right_flag = True
    # Update min and max values for the
    # parent recursive calls
    if Min < min_ref[0]:
        min_ref[0] = Min
    if node.val< min_ref[0]: # For leaf nodes
        min_ref[0] = node.val
    if node.val > max_ref[0]:
        max_ref[0] = node.val
    # If both left and right subtrees are BST.
    # And left and right subtree properties hold
    # for this node, then this tree is BST.
    # So return the size of this tree
    if left_flag and right_flag:
        if ls + rs + 1 > max_size_ref[0]:
            max_size_ref[0] = ls + rs + 1
        return ls + rs + 1
    else:
        # Since this subtree is not BST, set is_bst
        # flag for parent calls is_bst_ref[0] = 0;
        return 0
#     50
# /     \
# 10     60
# / \     / \
# 5 20 55 70
#         /     / \
#     45     65 80
root = Node(50)
root.left= Node(10)
root.right= Node(60)
root.left.left = Node(5)
root.left.right = Node(20)
root.right.left = Node(55)
root.right.left.left = Node(45)
root.right.right = Node(70)
root.right.right.left = Node(65)
root.right.right.right = Node(80)
print("Size of the largest BST is",largestBST(root))
# Utility function to track the nodes
# that we have to swap
def correctBstUtil(root, first, middle,last, prev):
    if(root):
        # Recur for the left sub tree
        correctBstUtil(root.left, first, middle, last, prev)
        # If this is the first violation, mark these
        # two nodes as 'first and 'middle'
        if(prev[0] and root.val < prev[0].val):
            if(not first[0]):
                first[0] = prev[0]
                middle[0] = root
            else:
                # If this is the second violation,
                # mark this node as last
                last[0] = root
        prev[0] = root
        # Recur for the right subtree
        correctBstUtil(root.right, first, middle, last, prev)
# A function to fix a given BST where
# two nodes are swapped. This function
# uses correctBSTUtil() to find out two
# nodes and swaps the nodes to fix the BST
def correctBst(root):
    # Followed four lines just for forming
    # an array with only index 0 filled
    # with None and we will update it accordingly.
    # we made it null so that we can fill
    # node data in them.
    first = [None]
    middle = [None]
    last = [None]
    prev = [None]
    # Setting arrays (having zero index only)
    # for capturing the required node
    correctBstUtil(root, first, middle, last, prev)
    # Fixing the two nodes
    if(first[0] and last[0]):
        # Swapping for first and last key values
        first[0].val, last[0].val = (last[0].val,first[0].val)
    elif(first[0] and middle[0]):
        # Swapping for first and middle key values
        first[0].val, middle[0].val = (middle[0].val,  first[0].val)
    # else tree will be fine
# Function to print inorder
# traversal of tree
def PrintInorder(root):
    if(root):
        PrintInorder(root.left)
        print(root.val, end = " ")
        PrintInorder(root.right)
    else:
        return
#      6
#     /   \
#   10    2
#  / \   / \
# 1   3 7   12
# Following 7 lines are for tree formation
root = Node(6)
root.left = Node(10)
root.right = Node(2)
root.left.left = Node(1)
root.left.right = Node(3)
root.right.left = Node(7)
root.right.right = Node(12)
PrintInorder(root)
correctBst(root)
PrintInorder(root)
<file_sep>/arrays.py
def reverselist(arr):
    start=0
    end=len(arr)-1
    while start<end:
        arr[start],arr[end]=arr[end],arr[start]
        start+=1
        end-=1
    return arr
#print(reverselist([1,2,3]))
'''we swap start index value and end value to reverse the list eg:[1,2,3] start=0,end=2 so exchange 1 and 3 values start=1 and end=1 so final reverse list is [3,2,1]'''
def getmaxmin(arr,low,high):
    arrmin=arrmax=arr[low]
    if low==high:#if there is only one element
        return arrmax,arrmin
    elif high==low+1:#if there is only 2 element
        if arr[low]>arr[high]:
            arrmax=arr[low]
            arrmin=arr[high]
        else:
            arrmax=arr[high]
            arrmin=arr[low]
        return arrmax,arrmin
    else:
        mid=(low+high)//2
        arrmax1,arrmin1=getmaxmin(arr, low, mid)
        arrmax2,arrmin2=getmaxmin(arr, mid+1, high)
        return (max(arrmax1,arrmax2),min(arrmin1,arrmin2))
#print(getmaxmin([1,2,3],0,2))
'''we initialize arrmax,arrmin with low index for more than 2 element take mid value then get 2arrmax with mid has highvalue and low value similarly with arrmin get minvalues '''
def kthsmallelement(arr,start,end,k):
    if k>0 and k<=end-start+1:
        pos=partition(arr,start,end)
        if pos-start==k-1:#position is same as k
            return arr[pos]
        if pos-start>k-1:#position greater than k recur through left subarrat
            return kthsmallelement(arr, start, pos-1, k)
        return kthsmallelement(arr,pos+1,end, k-pos+start-1)#else recur through right subarray
def partition(arr,start,end):
    a=arr[end]
    i=start
    for j in range(start,end):
        if arr[j]<=a:
            arr[i],arr[j]=arr[j],arr[i]
            i+=1
    arr[i],arr[end]=arr[end],arr[i]
    return i
#print(kthsmallelement([1,2,3,4,5,6,7],0,6,3))
'''paritition works as partition of quick sort assuming last element as pivot and moves all smaller element to left of it and greater eleemnts to right and return the index i of pivot such that array is sorted'''
def sort012(a,n):
    low=mid=0
    high=n-1
    while mid<high:
        if a[mid]==0:
            a[low],a[mid]=a[mid],a[low]
            low+=1
            mid+=1
        elif a[mid]==1:
            mid+=1
        else:
            a[mid],a[high]=a[high],a[mid]
            high-=1
    return a
#print(sort012([0,1,0,2,1,1],6))
'''traverse the array from start to end such that mid<high if mid index value is 0 push it low index and take low index value in mid and low+=1 and mid+=1if mid index value=1 then update mid as we want 1 to be near mid of the table if mid index value=2 then swap it with high index value so to keep 2 at rear end of list high-=1
0's are near low index value 1's are near the mid of array and 2's in high index/rear end of array'''
def rearrangearray(arr,n):
    j=0
    for i in range(0,n):
        if arr[i]<0:#if value is negative
            arr[i],arr[j]=arr[j],arr[i]#exchange the values to starting with i and j th index are exchanged
            j+=1
    return arr
#print(rearrangearray([1,2,3,-4,5],5))we move negative values to start of array
def printunion(arr1,arr2):
    i=j=0
    while i<len(arr1) and j<len(arr2):
        if arr1[i]<arr2[j]:
            print(arr1[i])#ith value is low so printed first
            i+=1
        elif arr2[j]<arr1[i]:
            print(arr2[j])#jth value is low so printed
            j+=1
        else:
            print(arr2[j])#print remaining values of j
            i+=1
            j+=1
    while i<len(arr1):#printing remaining elementd of larger array
        print(arr1[i])
        i+=1
    while j<len(arr2):
        print(arr2[j])
        j+=1
#printunion([1,2,4,5,6],[2,3,5,7])
def  rotate(arr,n):
    x=arr[n-1]
    for i in range(n-1,0,-1):
        arr[i]=arr[i-1]
    arr[0]=x
    return arr
#print(rotate([1,2,3],3))
'store last element in x then push all elements by one positition ahead and replace first eleemnt with x'
def largestsumarray(arr,n):
    maxsofar=-10000000000#take large value so 1st value is replaced easly
    maxend=0
    for i in range(0,n):
        maxend=maxend+arr[i]
        if maxsofar<maxend:
            maxsofar=maxend
        if maxend<0:#for negative value reset maxend value
            maxend=0
    return maxsofar
#print(largestsumarray([1,2,3,-6],4))
'''look for positive numbers and keep track of maximum sum contigous segment among all positive segments each time we get positive sum compare it with maxsofar and add it to maxsofar if its>maxsofar'''
def getmindiff(arr,n,k):
    if n==1:
        return 0
    arr.sort()
    ans=arr[n-1]-arr[0]
    small=arr[0]+k
    big=arr[n-1]-k
    if small>big:
        small,big=big,small
    for i in range(1,n-1):
        subtract=arr[i]-k
        add=arr[i]+k
        if subtract>=small or add<=big:
            continue
        if big-subtract<=add-small:
            small=subtract
        else:
            big=add
    return min(ans,big-small)
#print(getmindiff([4,6], 2, 10))
'''modify array by subtracting/adding k to every element such that differenece between maximum and minimum is minimized
we initilaize result by subtract last-first element handle corner elements as small and big by addin 1st element iwth k and last element - k
if small>big then exchange values traverse middle values if both subtraction and addition dont change the differeence
either subtraction causes smaller number or addititon causes greater number update small/big using this if big-subtract causes smaller diff update small else update big'''
def duplicates(arr,size):
    for i in range(0,size):
        if arr[abs(arr[i])]>=0:
            arr[abs(arr[i])]=-arr[abs(arr[i])]
        else:
            print(abs(arr[i]))
#duplicates([1,2,3,3,2,1],6)
'traverse the array for every element takes its absolute value if abs(arr[i]) is positive element hs been encountered before else if negative eleemnt has been encountered before print absolute value of current element'
def merge(a,b):
    for i in range(len(a)):#traverse e1st array and check for each element
        if a[i]>b[0]:
            a[i],b[0]=b[0],a[i]#shift b[0] to its correct position in second array
            j=0
            while j+1<len(b) and b[j]>b[j+1]:#shift elements with b also correctly
                b[j],b[j+1]=b[j+1],b[j]
                j+=1
    print(a)
    print(b)
#merge([1,2,4],[3,5,6])
def mergeintervals(arr):
    arr.sort()
    ans=[]
    for s,e in arr:
        if ans and s<=ans[-1][1]:
            ans[-1][1]=max(ans[-1][1],e)
        else:
            ans.append([s,e])
    print(ans)
#mergeintervals([[1,4],[2,6]])
'''sort the list and create new list ans for each start and end in arr if s<ans last elements 1st element then bigger interval with ans[1][1],e is created'''
def nextpermutate(arr):
    a=list(arr)
    for i in range(-1,-len(arr)+1,-1):
        if arr[i]>arr[i-1]:
            arr[i],arr[i-1]=arr[i-1],arr[i]
            break
    if arr!=a:
        return arr
    else:
        a.sort()
        return a
#print(nextpermutate([3,2,1]))
'''we take a=list(arr) we iterate in reverese order if last element>2nd last element then exchange value so we get next permutate of list values'''
def countinversion(arr):
    count=0
    for i in range(len(arr)):
        for j in range(len(arr)):
            if arr[i]>arr[j] and i<j:
                count+=1
    return count
#print(countinversion([3,2,1]))
'''count iversion is no of steps needed to sort the list'''
def maxprofit(arr):
    ans=0
    for i in range(1,len(arr)):
        if arr[i]-arr[i-1]>0:
            ans+=(arr[i]-arr[i-1])
    return ans
#print(maxprofit([7,1,6,5,4]))
'''we have array of stock prices we need to find when to buy and sell stock so maximum profit is possible constrait: we cant sell stock before buying it eg:[7,1,6]  actually maximum profit is obtained when we buy at 1 and sell at 7 but 7 price was available a day before so we cant sell before buying it that why maximum  profit is 5 as we can buy for 1 and sell it for 7'''
def sumarray(arr,k):
    d={}
    for i,e in enumerate(arr):
        if k-e in d:
            print(arr[d.get(k-e)],arr[i])
        d[e]=i
    return
#sumarray([1,5,7,-1],6)
'''we make d dictionary with e as keys and i as values then traverse such that i stores index value of array and e stores actucal value of element in arrayif k(target)-e is presnt in d then print arr([k-e]th index(key)i) with arr[i] and store e as key and i as value in dictionary so repetattion can be avoided'''
def commomeleemnts(arr1,arr2,arr3):
    arr1=set(arr1)
    arr2=set(arr2)
    arr3=set(arr3)
    arr1=arr1.intersection(arr2)
    arr1=arr1.intersection((arr3))
    return list(arr1)
#print(commomeleemnts([10,101,20],[10,101,20,2,34],[20,10]))
def rearrange(arr):
    arr.sort()
    i=j=1
    while j<len(arr):
        if arr[j]>0:
            break
        j+=1
    while (arr[i]<0) and (j<len(arr)):
        arr[i],arr[j]=arr[j],arr[i]
        i+=2
        j+=1
    return arr
#print(rearrange([5,-2,-3,4,5]))
'''we need to keep negative numbers at even index of list and positive numebrs at odd indexes of list so sort the list first  j pointer points positive value and i points negative value becuase we break loops as soon as arr[j]>0 then swaps its value iwth negative value available in the list making them be in even indexes and  increase i by 2 as i is negative index pointer'''
def sumis0(arr):#it is same as sumarray of k=0
    d={}
    for i,e in enumerate(arr):
        if 0-e in d:
            print('yes')
        d[e]=i
    return
#sumis0([1,-1,5,3])
def factorial(n):
    if n<=1:#base case
        return n
    else:
       return  n*factorial(n-1)
#print(factorial(5))
def maxproduct(arr,n):
    maxendhere=minendhere=1#max positive product ending at cuurent position and min positive product ending at cuurent position
    maxsofar=flag=0
    for i in range(n):#traverse through array  check maxendhere is alaway maxproduct ending with arr[i] or 1 minendhere is always negative product with arr[i] or 1
        if arr[i]>0:#if element is positive update max end here and minendhere
            maxendhere=maxendhere*arr[i]
            minendhere=min(minendhere*arr[i],1)
            flag=1
        elif arr[i]==0:#if eleemnt is zero maxendhere and minendhere cant here as value is greater than or equal to 1
             maxendhere=minendhere=1
        else:#if eleemnt is negative max end can be either be 1 or positive  min end can either be negative or 1 next min end can here will always be prev maxendhere*arr[i] next max  end here will be 1 if prev   minendhere is 1 otherwise next maxend here will be  p minendhere*arr[irev
             temp= maxendhere
             maxendhere=max(minendhere*arr[i],1)
             minendhere=temp*arr[i]
        if maxsofar<maxendhere:
            maxsofar=maxendhere
    if flag==0 and maxsofar==0:
        return 0
    return maxsofar
#print(maxproduct([0,10,6,-2,0],5))'''eg:[1,2,0,-3,-10] in this -3,-10 can give max product as contigious subarray '''
def longestconseqsubseq(a):
    a=set(a)
    maxlength=0
    for i in a:
        if i-1 not in a:
            length=1
            while i+length in a:
                length+=1
            maxlength=max(maxlength,length)
    return maxlength
#print(longestconseqsubseq([1,0,2,4,3]))
''' we nedd to find logest subsequence that are consecutive in given array eg:[1,7,8,55,2,3] has 3 with [1,2,3] as largest subsequence
make set out of array now iterate through every element in a if i is candidate for starting sequence as i-1 doesnt exist in the set then length of subsequence get value 1 (as i is starting value) then check for i+1,i+2...i+length available in set or not  then return maxlength as maximum value of maxlength and length'''
def morethannbyk(arr,n,k):
    x=n//k
    freq={}
    for i in range(n):
        if arr[i] in freq:
               freq[arr[i]]+=1
        else:
            freq[arr[i]]=1
    for i in freq:
        if freq[i]>x:
            print(i)
#morethannbyk([1,1,1],3, 2)
'''we have to show values whose frequency is more than n/k so x=n//k and freq dictinary created iterate over it  if arr[i] already exist increase its frequency or add it to freq{} then print all values in freq{} greater than x'''
def maxwater(arr):
    n=len(arr)
    left=result=lmax=rmax=0
    right=n-1
    while left<=right:#we need to check for mininmum of left and right max for every element
        if rmax<=lmax:#add difference between current element and right value
            result+=max(0,rmax-arr[right])
            rmax=max(rmax,arr[right])#update rightmax
            right-=1#update right pointer
        else:
            result+=max(0,lmax-arr[left])#similar to right we do for left
            lmax=max(lmax,arr[left])
            left+=1
    return result
#print(maxwater([0,1,0,2,1,0,1,3,2,1,2,1]))
'''at every index amount of rainwatre stored is difference between current index height and minimum of leftmaxheight and rightmaxheight
 given n non negative integers representing elevation map whree the width of bar is 1 comput how much watre can be stored between two bars 0 represnt the block is empty and 2 reperesent there is 2 block height bar
 eg:[2,0,2] we can trap 2 units of water as its suurounded by 2 units height block bars on left and right'''
def chocolatedis(arr,n,m):
    if m==0 or n==0:#if no of students or chocolates are 0
        return 0
    arr.sort()
    if n<m:# as students cant be more than number of packets
        return -1
    mindiff=arr[n-1]-arr[0]
    for i in range(len(arr)-m+1):
        mindiff=min(mindiff,arr[i+m-1]-arr[i])
    return mindiff
#print(chocolatedis([12,4,7,9,2,23,25,41,30,40,28,42,30,44,48,43,50],17, 7))
'''array of n integers where each value represent chocolates in packet divided among m students such that eaxh gets one packet differeence between no of maximum chocollates and minimum chocolates given to students is minimum
find the subarray of size m such that difference between last(maximum) and first(minimum) elements of subarray is minimum'''
def partittion3way(arr,n,low,high):
    start=i=0
    end=n-1
    while i<=end:#traverse from left of array
        if arr[i]<=low:#lower than low are put at beginning of array
            temp=arr[i]
            arr[i]=arr[start]
            arr[start]=temp
            i+=1
            start+=1
        elif arr[i]>high:#greater than high are put at end of arrray
            temp=arr[i]
            arr[i]=arr[end]
            arr[end]=temp
            end-=1
        else:#all other reamain at same positition as before
            i+=1
a=[1,5,3,4,2]
partittion3way(a, 5, 3, 4)
#print(a)
'''given an array and range(low,high) partition around the range sucthat all elements lowr than low come first all element in range of low and high come next and all element greater than high appera in end '''
def palindrome(n):
    str1=str(n)
    len1=len(str1)
    for i in range(int(len1/2)):
        if str1[i]!=str1[len1-1-i]:#if 1st and last index character are not same then not a palindrome similarly for 2nd and 2nd last....
            return False
    return True
def palindromearray(arr,n):
    for i in range(n):
        ans=palindrome(arr[i])
        if ans==False:
            return False
    return True
#print(palindromearray([111,122], 2))
'''given an array which have numbers return 1 if all elements in array in palindrome eg:[111,222,323,414] return one as elements in array are palindrome [121,343,556] return0 as 3rd element is not palindrome'''
def medianof2array(arr1,arr2):
    arr=arr1+arr2
    arr.sort()
    mid=len(arr)//2
    if len(arr)%2!=0:
        result=arr[mid]
    else:
        result=(arr[mid]+arr[mid+1])/2
    return result
#print(medianof2array([1,3],[2]))

    <file_sep>/sortalgorithm.py
def bubblesort(lists):
    size=len(lists)
    for i in range(size-1):
        swap=False
        for j in range(size-i-1):
            if lists[j]>lists[j+1]:
                lists[j],lists[j+1]=lists[j+1],lists[j]
                swap=True
        if not swap:
            break
'''def bubblesortfunction(lists,key):
    size=len(lists)
    if key=='name':
        for i in range(size-1):
            swap=False
            for j in range(size-i-1):
                if lists[j]['name']>lists[j+1]['name']:
                    lists[j]['name'],lists[j+1]['name']=lists[j+1]['name'],lists[j]['name']
                    swap=True
            if not swap:
                break
    elif key=='amount':
        for i in range(size-1):
            swap=False
            for j in range(size-i-1):
                if lists[j]['amount']>lists[j+1]['amount']:
                    lists[j]['amount'],lists[j+1]['amount']=lists[j+1]['amount'],lists[j]['amount']
                    swap=True
            if not swap:
                break
    elif key=='device':
        for i in range(size-1):
            swap=False
            for j in range(size-i-1):
                if lists[j]['device']>lists[j+1]['device']:
                    lists[j]['device'],lists[j+1]['device']=lists[j+1]['device'],lists[j]['device']
                    swap=True
            if not swap:
                break
a=[{'name':'mona','amount':1000,'device':'iphone'},
   {'name':'dhaval','amount':400,'device':'vivo'},
   {'name':'kathy','amount':200,'device':'oppe'},
   {'name':'amir','amount':800,'device':'iphone'}]
bubblesortfunction(a,'name')
print(a)'''
def insertionsort(lists):
    for i in range(1,len(lists)):
        key=lists[i]
        j=i-1
        while j>=0 and key<lists[j]:
            lists[j+1]=lists[j]
            j=j-1
        lists[j+1]=key
def selectionsort(lists):
    size=len(lists)
    for i in range(size-1):
        minindex=i
        for j in range(minindex+1,size):
            if lists[j]<lists[minindex]:
                minindex=j
        if i!=minindex:
            lists[i],lists[minindex]=lists[minindex],lists[i]
def swap(a,b,lists):
    if a!=b:
        lists[a],lists[b]=lists[b],lists[a]
def partition(lists,start,end):
    piv=start
    pivot=lists[piv]
    while start<end:
        while start<len(lists) and lists[start]<=pivot:
            start+=1
        while lists[end]>pivot:
            end-=1
        if start<end:
            swap(start,end,lists)
    swap(piv,end,lists)
    return end
def quicksort(lists,start,end):
    if start<end:
        pi=partition(lists,start,end)
        quicksort(lists,start,pi-1)
        quicksort(lists, pi+1, end)
def merge2list(list1,list2,list3):
    i=j=k=0
    while i<len(list1) and j<len(list2):
        if list1[i]<=list2[j]:
            list3[k]=list1[i]
            i+=1
        else:
            list3[k]=list2[j]
            j+=1
        k+=1
    while i<len(list1):
        list3[k]=list1[i]
        i+=1
        k+=1
    while j<len(list2):
        list3[k]=list2[j]
        j+=1
        k+=1
def merge1list(lists):
    if len(lists)<=1:
        return lists
    mid=len(lists)//2
    left=lists[:mid]
    right=lists[mid:]
    merge1list(left)
    merge1list(right)
    merge2list(left,right,lists)
'''a=[17,8,25,34,21]
merge1list(a)
print(a)'''
def shellsort(lists):
    size=len(lists)
    gap=size//2
    while gap>0:
        for i in range(gap,size):
            anchor=lists[i]
            j=i
            while j>=gap and lists[j-gap]>anchor:
                lists[j]=lists[j-gap]
                j-=gap
                lists[j]=anchor
        gap=gap//2
def countsort(lists):
    size=len(lists)
    output=[0]*size
    count=[0]*10
    for i in range(0,size):
        count[lists[i]]+=1
    for i in range(1,10):
        count[i]+=count[i-1]
    i=size-1
    while i>=0:
        output[count[lists[i]]-1]=lists[i]
        count[lists[i]]-=1
        i-=1
    for i in range(0,size):
        lists[i]=output[i]
def heapify(lists,n,i):
    largest=i
    l=2*i+1
    r=2*i+2
    if l<n and lists[i]<lists[l]:
        largest=l
    if r<n and lists[largest]<lists[r]:
        largest=r
    if largest!=i:
        lists[i],lists[largest]=lists[largest],lists[i]
        heapify(lists,n,largest)
def heapsort(lists):
    n=len(lists)
    for i in  range(n//2,-1,-1):
        heapify(lists,n,i)
    for i in range(n-1,0,-1):
        lists[i],lists[0]=lists[0],lists[i]
        heapify(lists,i,0)

            <file_sep>/DEqueue.py
#code for DoubleEndedqueue
class DEqueue:
    def __init__(self):
        self.items=[]
    def isempty(self):
        return self.items==[]
    def addrear(self,data):
        self.items.append(data)
    def addfront(self,data):
        self.items.insert(0,data)
    def removefront(self):
         return self.items.pop(0)
    def removerear(self):
        return  self.items.pop()
'''a=DEqueue()
print(a.isempty())
a.addrear(8)
a.addrear(9)
a.addfront(7)
a.addfront(6)
print(a.items)
print(a.removefront())
print(a.removerear())
print(a.items)'''
#code for queue
from collections import deque
class queue:
    def __init__(self):
        self.buffer=deque()
    def enqueue(self,val):
        self.buffer.appendleft(val)
    def dequeue(self):
        return self.buffer.pop()
    def is_empty(self):
        return len(self.buffer) == 0
    def size(self):
        return len(self.buffer)
    def front(self):
        return self.buffer[-1]
#placing orders using queue
a=queue()
def placeorder(key):
    for i in key:
        a.enqueue(i)
'''b=['pizza','burger']
placeorder(b)
print(a.dequeue())
print(a.dequeue())'''
#making pattern using queue
def producebinary(n):
    number=queue()
    number.enqueue('1')
    for i in range(n):
        front=number.front()
        print(front)
        number.enqueue(front+'0')
        number.enqueue(front+'1')
        number.dequeue()
#producebinary(9)

branch_name: refs/heads/main

languages: Markdown Python