<repo_name>varun21290/leetcode_solutions<file_sep>/Perfect Squares/Readme.md
# Problem Statement

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.


Example 1:

Input: n = 12

Output: 3 

Explanation: 12 = 4 + 4 + 4.
<file_sep>/Possible Bipartition/Readme.md
# Problem Statement

Given a set of N people (numbered 1, 2, ..., N), we would like to split everyone into two groups of any size.


Each person may dislike some other people, and they should not go into the same group. 


Formally, if dislikes[i] = [a, b], it means it is not allowed to put the people numbered a and b into the same group.


Return true if and only if it is possible to split everyone into two groups in this way.

Input: N = 4, dislikes = [[1,2],[1,3],[2,4]]

Output: true

Explanation: group1 [1,4], group2 [2,3]


Input: N = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]

Output: false
<file_sep>/PerfectSquare/PerfectSquare.py
def isPerfectSquare(self, num: int) -> bool:
    if(num<2): return True
    x=2
    y=num//2
    while(y>=x):
        z=(x+y)//2
        srt=z*z
        if(srt==num): return True
        elif(srt>num): y=z-1
        else: x=z+1
    return False
        
nums = [4,9,144,399]
for x in nums:
    print (x,isPerfectSquare(x))
<file_sep>/Two City Scheduling/solution.py
class Solution:
    def twoCitySchedCost(self, costs: [[int]]) -> int:
        l=sorted(costs,key=lambda x: x[0]-x[1])
        n=len(costs)
        return (sum(x[0] for x in l[0:n//2]) + sum(x[1] for x in l[n//2:]))
<file_sep>/Insert Delete GetRandom O(1)/solution.py
class RandomizedSet:
    ds={}
    size=0
    import random
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.ds={}
        self.size=0
        

    def insert(self, val: int) -> bool:
        """
        Inserts a value to the set. Returns true if the set did not already contain the specified element.
        """
        if val in self.ds:
            return False
        else:
            self.ds[val]=val
            self.size+=1
            return True

    def remove(self, val: int) -> bool:
        """
        Removes a value from the set. Returns true if the set contained the specified element.
        """
        if val in self.ds:
            self.ds.pop(val)
            self.size-=1
            return True
        else:
            return False
        

    def getRandom(self) -> int:
        """
        Get a random element from the set.
        """
        sel=random.randint(0,self.size-1)
        return self.ds[list(self.ds.keys())[sel]]


# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()
<file_sep>/Permutation In String/permutationInString.py
class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if(len(s2)<len(s1)): return False
        count_s1=Counter(s1)
        len_s1=len(s1)
        len_s2=len(s2)
        i=len_s1-1
        while(i<len_s2):
            if(s1.find(s2[i])!=-1):
                if (count_s1==Counter(s2[i-len_s1+1:i+1])):
                    return True
                i+=1
            else:
                i+=len_s1
        return False
    
    def checkInclusionHash(self, s1: str, s2: str) -> bool:
        if(len(s2)<len(s1)): return False
        len_s1=len(s1)
        len_s2=len(s2)
        shashs1=0
        shashs2=0
        
        for i in range(len_s1):
            shashs1=shashs1+hash(s1[i])
            shashs2=shashs2+hash(s2[i])
        if(shashs1==shashs2): return True
        
        for i in range(len_s1,len_s2):
            shashs2=shashs2+hash(s2[i])-hash(s2[i-len_s1])
            if(shashs1==shashs2): return True
        return False
<file_sep>/Cousins in Binary Tree/Readme.md
# Problem Statement

In a binary tree, the root node is at depth 0, and children of each depth k node are at depth k+1.


Two nodes of a binary tree are cousins if they have the same depth, but have different parents.


We are given the root of a binary tree with unique values, and the values x and y of two different nodes in the tree.


Return true if and only if the nodes corresponding to the values x and y are cousins.

Input: root = [1,2,3,4], x = 4, y = 3

Output: false

Input: root = [1,2,3,null,4,null,5], x = 5, y = 4

Output: true
<file_sep>/Find All Anagrams/findAllAnagrams.py
class Solution:
    def findAnagrams(self, s: str, p: str) -> [int]:
        if(len(s)==0 or len(p)>len(s)): return []
        find=[]
        anagrams={}
        lp=sorted(p)
        len_p=len(p)
        len_s=len(s)
        i=len_p-1
        while(i<len_s):
            if(p.find(s[i])!=-1):
                if (lp==sorted(s[i-len_p+1:i+1])):
                    find.append(i-len_p+1)
                i+=1
            else: i+=len_p
        return find
        
            
    def findAnagrams2(self, s: str, p: str) -> [int]:
        if(len(s)==0 or len(p)>len(s)): return []
        find=[]
        count_p=Counter(p)
        len_p=len(p)
        len_s=len(s)
        i=len_p-1
        while(i<len_s):
            if(p.find(s[i])!=-1):
                if (count_p==Counter(s[i-len_p+1:i+1])):
                    find.append(i-len_p+1)
                i+=1
            else:
                i+=len_p
        return find
            
<file_sep>/Find the Town Judge/TownJudge.py
def townJudge(A,N):
  a0 = {x[0] for x in A}
  candidate=-1
  trustedby=0
  for i in range(N):
    if (i+1 not in a0): can=i+1
  for a in A:
    if (a[1]==candidate): trustedby+=1
  if(trustedby==N-1): return candidate
    else : return -1
<file_sep>/Permutation In String/Readme.md
# Problem Statement

Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. 
In other words, one of the first string's permutations is the substring of the second string.

Input: s1 = "ab" s2 = "eidbaooo"

Output: True

Explanation: s2 contains one permutation of s1 ("ba").
<file_sep>/Reconstruct Itinerary/Solution.py
import bisect
class Solution:
    def findItinerary(self, tickets: [[str]]) -> [str]:
        graph={}
        itinerary=[]
        
        for ticket in tickets:
            if ticket[0] not in graph:
                graph[ticket[0]]=[ticket[1]]
            else:
                bisect.insort(graph[ticket[0]],ticket[1])
                
        def dfs(graph,itinerary,src):
            if src in graph:
                while(len(graph[src])>0):
                    new_src=graph[src][0]
                    graph[src]=graph[src][1:]
                    dfs(graph,itinerary,new_src)
            itinerary.append(src)
            
            
        dfs(graph,itinerary,"JFK")
        itinerary.reverse()
        return itinerary
        
<file_sep>/Sort Characters By Frequency/frequencySort.py
class Solution:
    def frequencySort(self, s: str) -> str:
        freq={}
        arr=[]
        for i in range(len(string)):
            if(string[i] in freq.keys()): freq[string[i]]=freq[string[i]]+1
            else: freq[string[i]]=1
        
        
        for key,item in freq.items():
            arr.append([key,item])
    
        from operator import itemgetter
        res = sorted(arr, key = itemgetter(1))
        s=''
        for i in range(len(res),0,-1):
            l=[res[i-1][0]]*res[i-1][1]
            for x in l:
                s=s+x
        return s
<file_sep>/Word Search II/Solution.py
from collections import defaultdict
class Solution:
    def __init__(self):
        self.result=set()
    
    def findWords(self, board: [[str]], words: [str]) -> [str]:
        class Trie(object):
            def __init__(self):
                self.child = {'#':0}
            def insert(self, word):
                current = self.child
                for l in word:
                    if l not in current:
                        current[l] = {'#':0}
                    current = current[l]
                current['#']=1
            def search(self,word):
                current=self.child
                for l in word:
                    if l in current:
                        current=current[l]
                    elif l not in current:
                        return -1
                if(current['#']==1): return 1
                else: return 0
                
        trie=Trie()
        for word in words:
            trie.insert(word)
            
        def dfs(i,j,graph,c):
            ss=graph[i][j]
            if (ss=='-1'): return
            graph[i][j]='-1'
            c=c+ss
            t=trie.search(c)
#             print(c,t)
            if (t!=-1):
                if t==1: 
                    self.result.add(c)
                dfs(i,j+1,graph,c)
                dfs(i,j-1,graph,c)
                dfs(i+1,j,graph,c)
                dfs(i-1,j,graph,c)
            graph[i][j]=ss
                
                
                

        graph=[['-1']*(len(board[0])+2) for _ in range(len(board)+2)]
        
        for i in range(len(board)):
            for j in range(len(board[0])):
                graph[i+1][j+1]=board[i][j]
        
        
        for i in range(1,len(graph)-1):
            for j in range(1,len(graph[0])-1):
                dfs(i,j,graph,"")
                
        return list(self.result)
<file_sep>/Delete Node in a List/Readme.md
# Problem Statement

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Input: head = [4,5,1,9], node = 5

Output: [4,1,9]

Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.
<file_sep>/MajorityElement/MajorityElement.py
def majority(nums,n,e,m,i):
    if(nums.count(nums[n])>e):
        return nums[n]
    else:
        i=i+1
        if (n==0 or n==m-1):
            return 'na'
        if(n<=e):
            o = majority(nums,0+int(m/(2**i)),e,m,i)
            if o!='na' : 
                return o
        if(n>=e):
            o = majority(nums,n+int(m/(2**i)),e,m,i)
            if o!='na' :
                return o
        return 'na'
nums=[1,0,1,1]
n=len(nums)
print (majority(nums,int(n/(2**1)),int(n/2),n,1))     
<file_sep>/Odd Even Linked List/oddEvenLinkedList.py
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        if (head is None): return head
        node=head
        temp1=node.next
        temp2=node.next
        node.next=temp2.next
        if(node.next is not None):
            node=node.next
            temp1.next=node.next
            while(node.next is not None):
                temp2=node.next
                node.next=temp2.next
                if(node.next is None): break
                node=node.next
                temp2.next=node.next

        node.next=temp1
        temp2.next=None
        return head
    
    
    def oddEvenListBetter(self, head: ListNode) -> ListNode:
        if (head is None): return head
        odd=head
        evenHead=head.next
        even=evenHead
        while( even is not None and even.next is not None):
            odd.next=even.next
            odd=odd.next
            even.next=odd.next
            even=even.next
        odd.next=evenHead
        return head
    

        
<file_sep>/Cheapest flights within K stops/solution.py
class Solution:
    def findCheapestPrice(self, n: int, flights: [[int]], src: int, dst: int, K: int) -> int:
        # import collections
        graph=collections.defaultdict(list)
        for u,v,c in flights:
            graph[u].append((v,c))
        queue=collections.deque([(src,0,0)])
        inf=float('inf')
        minCost=inf
        while queue:
            node, steps, costSoFar=queue.popleft()
            
            if(node==dst):
                minCost=min(minCost,costSoFar)
                continue
                
            if(steps>K or costSoFar>minCost):
                continue
                
            for v,c in graph[node]:
                queue.append((v,steps+1,costSoFar+c))
        
        return minCost if minCost!=inf else -1
<file_sep>/FirstUniqueCharacter/FirstUniqueCharacter.java
import java.io.IOException;

public class FirstUniqueCharacter {
    
    public static int firstUniqChar(String s) {
    	int map[] = new int[26];
    	int j = s.length();
    	for (char c : s.toCharArray()) {
    		map[c-97]+= 1;
    	}
    	for (int i = 0;i<26;i++) {
    		if(map[i]==1 && s.indexOf(i+97) < j) j = s.indexOf(i+97);
    	}
		return j==s.length()?-1:j;
    }
    
    
	public static void main(String[] args) throws IOException {
		
		String s = "leetccodel";
		System.out.println(firstUniqChar(s));
	}
    
}
<file_sep>/Coin Change 2/Readme.md
# Problem Statement

You are given coins of different denominations and a total amount of money. 
Write a function to compute the number of combinations that make up that amount. 
You may assume that you have infinite number of each kind of coin.

Input: amount = 5, coins = [1, 2, 5]

Output: 4

Explanation: there are four ways to make up the amount:

5=5

5=2+2+1

5=2+1+1+1

5=1+1+1+1+1
<file_sep>/Construct BST/bst.py
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
class Solution:
    def bstFromPreorder(self, preorder: [int]) -> TreeNode:
        root=TreeNode(preorder[0])
        for i in range(1,len(preorder)):
            node=root
            while(node):
                if(node.val>preorder[i]):
                    if(node.left): node = node.left
                    else: 
                        node.left = TreeNode(preorder[i])
                        break
                if(node.val<preorder[i]):
                    if(node.right): node=node.right
                    else:
                        node.right = TreeNode(preorder[i])
                        break
        return root
<file_sep>/Invert Binary Tree/solution.py
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
        
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        
        def reverse(root1,root2):
            if(root1.left):
                root2.right=TreeNode(root1.left.val)
                reverse(root1.left,root2.right)
                
            if(root1.right):
                root2.left=TreeNode(root1.right.val)
                reverse(root1.right,root2.left)
        
        if(root): 
            new_root = TreeNode(root.val)
            reverse(root,new_root)
            return new_root
<file_sep>/Uncrossed Lines/solution.py
class Solution:
    def maxUncrossedLines(self, A: [int], B: [int]) -> int:
#         dp=[0]*(len(A)+1)
#         for i in range((len(A)+1)):
#             dp[i]=[0]*(len(B)+1)

        elem = set(A)&set(B)
        A,B = [a for a in A if a in elem],[b for b in B if b in elem]
        dp=[[0]*(len(B)+1) for _ in range(len(A)+1)]
        i=len(A)-1
        while(i>=0):
            j=len(B)-1
            while(j>=0):
                if(A[i]==B[j]):
                    dp[i][j]=1+dp[i+1][j+1]
                if(A[i]!=B[j]):
                    dp[i][j]=max(dp[i][j+1],dp[i+1][j])
                j-=1
            i-=1
        return dp[0][0]
<file_sep>/Longest Duplicate Substring/Solution.py
class Solution:
    def longestDupSubstring(self, S: str) -> str:
    
        def rabinKarp(pattern, text, p_len, t_len):
  
            hash_map={}
            res=0
            p=0
            t=0
            h=1
            d=26
            q=10000001
        
            for i in range(p_len-1): 
                h = (h*d)%q 
  
            for i in range(p_len): 
                p = (d*p + ord(pattern[i]))%q 
                t = (d*t + ord(text[i+1]))%q
                
            hash_map[p]=0
            
            if(t==p and text[1:p_len+1] == pattern):
                    return pattern,0
            hash_map[t]=1

            for i in range(1,t_len-p_len+1):
                t=(d*(t-ord(text[i])*h) + ord(text[i+p_len]))%q
            
                if t<0: t+=q
                if(t in hash_map and text[i+1:i+1+p_len] == text[hash_map[t]:hash_map[t]+p_len]):
                    return text[i+1:i+1+p_len],hash_map[t]
                else:
                    hash_map[t]=i+1
                
            
            return '',0

        final_res=""
        l=0
        i=0
        r=len(S)-1
        while(l<=r):
            S_len=len(S)
            sub_res=''
            m=(l+r)//2
            pattern=S[i:i+m]
            sub_res,new_i=rabinKarp(pattern,S[i:],m,len(S[i+1:]))
            if sub_res!='': 
                final_res=sub_res
                l=m+1
                S=S[i:]
                i=new_i
            else:
                r=m-1
            
        return final_res
<file_sep>/Queue Reconstruction By Height/solution.py
class Solution:
    def reconstructQueue(self, people: [[int]]) -> [[int]]:
        people=sorted(people,key=lambda x: x[0])
        sorted_people=[[-1,-1] for _ in range(len(people))]
        for x in people:
            i=x[1]
            j=0
            while i>0 or sorted_people[j][0]!=-1:
                if sorted_people[j][0]==-1 or sorted_people[j][0]==x[0]:
                    i-=1
                j+=1
                    
            sorted_people[j]=x
            
        return sorted_people
            
    def reconstructQueueBetter(self, people: [[int]]) -> [[int]]:
        people.sort(key = lambda person: (person[0], -person[1]))
        people.reverse()
        queue = []
        for person in people:
            queue.insert(person[1],person)
        return queue
<file_sep>/Trie/Trie.py
class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.key = ""
        self.children = []
        self.endOfWord = False
        

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        trie = self
        for s in word:
            flag=0
            for i in range(len(trie.children)):
                if (trie.children[i].key==s): 
                    trie = trie.children[i] 
                    flag=1
                    break
            if(flag==0):
                new_node = Trie()
                new_node.key=s
                trie.children.append(new_node)
                trie = new_node
        trie.endOfWord = True

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        trie = self
        for s in word:
            flag=0
            for i in range(len(trie.children)):
                if (trie.children[i].key==s): 
                    trie = trie.children[i] 
                    flag=1
                    break
            if (flag==0): return False
        
        return True if trie.endOfWord else False
                
        

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        trie = self
        for s in prefix:
            flag=0
            for i in range(len(trie.children)):
                if (trie.children[i].key==s): 
                    trie = trie.children[i] 
                    flag=1
                    break
            if (flag==0): return False
        return True        


# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)
<file_sep>/README.md
# leetcode solutions

contains solutions to leetcode problems
<file_sep>/Counting Bits/solution.py
class Solution:
    def countBits(self, num: int) -> [int]:
        import math
        l=[0]
        for i in range(1,num+1):
            l.append(1+l[-2**(math.floor(math.log(i,2)))])
        return l
<file_sep>/Perfect Squares/Solution.py
import math
class Solution:
    def numSquares(self, n: int) -> int:
        dp=[0,1,2,3]
        
        for i in range(4,n+1):
            dp.append(i)
            
            for x in range(1,int(math.ceil(math.sqrt(i)))+1):
                temp=x*x
                
                if(temp<=i):
                    dp[i]=min(dp[i],1+dp[i-temp])
                else:
                    break
                    
        return dp[n]
        
  ##########################################      
    def numSquaresBetter(self, n: int) -> int:
        while( n % 4 == 0 ):	# Reduction by factor of 4
            n /= 4
			
        if n % 8 == 7:			# If n = 8k + 7, returns 4
            return 4
			
        for a in range( int(sqrt(n))+1 ):	# Check if n = a^2 + b^2, return 0 / 1
            b = int(sqrt(n - a**2))
            if a**2 + b**2 == n:
                return (a>0) + (b>0)
				
        return 3
<file_sep>/Edit Distance/Readme.md
# Problem Statement

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.


You have the following 3 operations permitted on a word:


Insert a character

Delete a character

Replace a character
<file_sep>/Sum Root to Leaf Numbers  Solution/Readme.md
# Problem Statement

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.


An example is the root-to-leaf path 1->2->3 which represents the number 123.


Find the total sum of all root-to-leaf numbers.


Note: A leaf is a node with no children.

Input: [4,9,0,5,1]

Output: 1026

Explanation:

The root-to-leaf path 4->9->5 represents the number 495.

The root-to-leaf path 4->9->1 represents the number 491.

The root-to-leaf path 4->0 represents the number 40.

Therefore, sum = 495 + 491 + 40 = 1026.
<file_sep>/Odd Even Linked List/Readme.md
# Problem Statement
Given a singly linked list, group all odd nodes together followed by the even nodes. 
Please note here we are talking about the node number and not the value in the nodes.


You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Input: 2->1->3->5->6->4->7->NULL

Output: 2->3->6->7->1->5->4->NULL
<file_sep>/Edit Distance/Pythonic_Solution.py
from collections import deque

class Solution:  
    def minDistance(self, word1: str, word2: str) -> int:
        
        visited = set()
        q = deque([(word1, word2, 0)])
        
        while q:
            w1, w2, dist = q.popleft()
            
            if (w1, w2) not in visited:
                visited.add((w1, w2))

                if w1 == w2:
                    return dist

                while w1 and w2 and w1[0] == w2[0]:
                    w1 = w1[1:]
                    w2 = w2[1:]

                dist += 1
                q.extend([(
                    w1[1:], w2[1:], dist), 
                    (w1, w2[1:], dist), 
                    (w1[1:], w2, dist)])
<file_sep>/Count Square Submatrices with All Ones/Readme.md
# Problem Statement

Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.


Input: matrix =

[

  [0,1,1,1],
  
  [1,1,1,1],
  
  [0,1,1,1]
  
]

Output: 15
Explanation: 
There are 10 squares of side 1.
There are 4 squares of side 2.
There is  1 square of side 3.
Total number of squares = 10 + 4 + 1 = 15.
<file_sep>/contiguous array/solution.py
class Solution:
    def findMaxLength(self, nums: [int]) -> int:
        max_length=0
        length_map={}
        zero=0
        one=0
        
        for i in range(len(nums)):
            if(nums[i]==0): zero+=1
            else: one+=1
            diff=zero-one
            if(diff==0):
                max_length=i+1
            
            if(diff in length_map):
                if(max_length < i-length_map[diff]):
                    max_length = i-length_map[diff]
            else:
                length_map[diff] = i
        return max_length
<file_sep>/Stock Span/stockSpan.py
class StockSpanner:
    price_history=[]
    price_map=[]
    stack=[]
    def __init__(self):
        self.price_history=[]
        self.price_map=[]
        self.span=[]
        
    def next(self, price: int) -> int:
        j=len(self.price_history)-1
        while(j!=-1 and self.price_history[j]<=price):
            j=self.price_map[j]
        self.price_history.append(price)
        self.price_map.append(j)
        return len(self.price_history)-j-1
    
    def nextBetter(self, price: int) -> int:
        span = 1
        while self.stack and self.stack[-1][0] <= price:
            span += self.stack.pop()[1]
        self.stack.append((price, span)) 
        return span
<file_sep>/MajorityElement/MajorityElement.java
import java.io.IOException;

public class MajorityElement {
    
    public static int majorityElement(int[] nums) {
    	int e = 0;
    	int n = nums.length;
		return (majority(nums,(int) Math.floor(n/Math.pow(2,1)),(int) Math.floor(n/2),n,1));
    }
    
    private static int frequency(int[] nums,int n) {
		int count = 0;
		for(int i =0;i<nums.length;i++) {
			if(nums[i]==n) count+=1;
		}
		return count;
	}
    
    

	private static int majority(int[] nums,int n,int e,int m,int i) {
		if(frequency(nums,nums[n])>e) return nums[n];
		else {
			i = i+1;
			if(n==0 || n==m-1) return -1;
			if(n<=e) {
				int o = majority(nums,0+(int) Math.floor(m/Math.pow(2,i)),e,m,i);
				if (o!=-1) return o;
			}
			if(n>=e) {
				int o = majority(nums,n+(int) Math.floor(m/Math.pow(2,i)),e,m,i);
				if (o!=-1) return o;
			}
			return -1;
		}
	}
	
	
	
    public static int majorityElementBetter(int[] nums) {
        
        if (nums == null || nums.length == 0) {
            return 0;
        }
        return majorityElement(nums, 0);
    }
    private static int majorityElement(int[] nums, int start){
        int count = 1;
        int num = nums[start];
        for(int i = start+1;i<nums.length;i++){
            if(num == nums[i]) count++;
            else count--;
            if(count == 0) return majorityElement(nums,i+1);
        }
        return num;
    }
	
    
	public static void main(String[] args) throws IOException {
		int s[] = {2,2,1,3,1,1,4,1,1,5,1,1,6};
		System.out.println(majorityElement(s));
		System.out.println(majorityElementBetter(s));
	}
    
}
<file_sep>/Remove K Digits/RemoveKDigits.py
def removeKdigits(self, num: str, k: int)
    new_num=''
    i=len(num)-k
    j=0
    while(i>0):
        minm=j
        while(j<=len(num)-i):
            if(num[j]<num[minm]):minm=j
            j+=1
        new_num = new_num+num[minm]
        i=i-1
        j=minm+1
    return new_num.lstrip('0') or '0'

def removeKdigitsBetter(self, num: str, k: int) -> str:
    new_num=[]
    for n in num:
        while k and new_num and new_num[-1]>n:
            new_num.pop()
            k-=1
        new_num.append(n)
    new_num = new_num[:-k] if k else new_num
    return "".join(new_num).lstrip('0') or "0"
<file_sep>/Insert Delete GetRandom O(1)/Readme.md
# Problem Statement

Design a data structure that supports all following operations in average O(1) time.


insert(val): Inserts an item val to the set if not already present.

remove(val): Removes an item val from the set if present.

getRandom: Returns a random element from current set of elements. 
Each element must have the same probability of being returned.
<file_sep>/Possible Bipartition/solution.py
class Solution:
    def possibleBipartition(self, N: int, dislikes: [[int]]) -> bool:
        matrix=[[0]*N for _ in range(N)]
        for dislike in dislikes:
            matrix[dislike[0]-1][dislike[1]-1]=1
            matrix[dislike[1]-1][dislike[0]-1]=1
        queue=[0]
        color={}
        color[0]=1
        n=0
        while len(queue)>0:
            for i in range(len(matrix[0])):
                if matrix[queue[0]][i]==1:
                    if i not in color:
                        color[i]= 1 if color[queue[0]]==0 else 0
                        queue.append(i)
                    elif color[i]==color[queue[0]]:
                        return False
            queue=queue[1:]
            n+=1
            if(len(queue)==0 and n<N):
                queue.append(n)
                if (n not in color):
                    color[n]=1
        return True
                    
<file_sep>/Find All Anagrams/Readme.md
# Problem Statement

Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.


Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.


The order of output does not matter.

Input:

s: "cbaebabacd" p: "abc"


Output:

[0, 6]


Explanation:

The substring with start index = 0 is "cba", which is an anagram of "abc".

The substring with start index = 6 is "bac", which is an anagram of "abc".
<file_sep>/Maximum Sum Circular Subarray/maxSumCircularSubarray.py
class Solution:
    def maxSubarraySumCircular(self, arr: [int]) -> int:
        
        new_arr=arr.copy()
        new_arr.sort()
        max_sum=0
        
        if(new_arr[0]==new_arr[-1]):
            if(new_arr[0]>0): return new_arr[0]*len(new_arr)
            else: return new_arr[0]
        
        
        if(new_arr[0]>0):
            for x in new_arr:
                max_sum+=x
            return max_sum
                
        
        def maxSum(A) : 
            n=len(A)//2
#             included=[]
            included_so_far=[]
            max_sum=-30000*30
            max_so_far=0
            i=0
            j=0
#             print (A)
            for i in range(n):
                max_so_far+=A[i]
                
                if(max_so_far>=max_sum): 
                    max_sum=max_so_far
                    start=j
                    end=i
                if(max_so_far<0): 
                    max_so_far=0
                    j=i+1

            
            i=start
            j=start
            max_so_far=0
            while(i<2*n):
                if(i-j==n): 
                    max_so_far=0
                    i=i%n+1
                    j=i
                    continue
                max_so_far+=A[i]
                if(max_so_far>max_sum): 
                    max_sum=max_so_far
                        
                if(max_so_far<0): 
                    max_so_far=0
                    j=i+1
                i+=1
            
            
            return max_sum        
            
        new_arr = arr.copy()
        new_arr.extend(arr)

        return maxSum(new_arr)
<file_sep>/Course Schedule/Solution.py
class Solution:
    def canFinish(self, numCourses: int, prerequisites: [[int]]) -> bool:
        graph={}
        vertices=[0]*numCourses
        for edge in prerequisites:
            if edge[0] in graph:
                graph[edge[0]].append(edge[1])
            else:
                vertices[edge[0]]=1
                graph[edge[0]]=[edge[1]]

        
        visited=[0]*numCourses
        reVisited=[0]*numCourses
        
        def dfs(key):
            visited[key]=1
            reVisited[key]=1
            if vertices[key]==1:
                for req in graph[key]:
                    if reVisited[req]==1: return False
                    if dfs(req)==False: return False
            reVisited[key]=0
            return True
        
                
        for par in graph.keys():
            if visited[par]==0: flag=dfs(par)
            if flag==False: return False
                
        return True
    
    
    def canFinishBetter(self, numCourses: int, prerequisites: [[int]]) -> bool:
        graph = [[] for _ in range(numCourses)]
        visit = [0 for _ in range(numCourses)]

        for x, y in prerequisites:
            graph[x].append(y)

        for i in range(numCourses):
            if not self.dfs(i, visit, graph):
                return False

        return True

    def dfs(self, i, visit, graph):
        if visit[i] == -1:
            return False
        if visit[i] == 1:
            return True

        visit[i] = -1
        for j in graph[i]:
            if not self.dfs(j, visit, graph):
                return False
        visit[i] = 1

        return True
<file_sep>/Coin Change 2/solution.py
class Solution:
    def change(self, amount: int, coins: [int]) -> int:
        if amount==0: return 1
        dp=[]
        for _ in range(len(coins)+1):
            l=[1]
            l.extend([0]*amount)
            dp.append(l)
        dp[0][0]=0
        for i in range(1,len(coins)+1):
            for j in range(1,amount+1):
                dp[i][j]=dp[i-1][j]+ (0 if j<coins[i-1] else dp[i][j-coins[i-1]])
        return dp[-1][-1]
    
    
    def changeBetter(self, amount: int, coins: [int]) -> int:
        changes = [0] * (amount + 1)
        changes[0] = 1 
        for coin in coins:
            for i in range(0, amount - coin + 1):
                if changes[i]:
                    changes[i + coin] += changes[i]
        return changes[amount]
        
<file_sep>/FloodFill/floodFill.py
def floodFill(self, image: [[int]], sr: int, sc: int, newColor: int) -> [[int]]:
    def fill(image,x,y,color,newColor,checked):
        checked.append([sr,sc])
        if(image[x][y]!=color or image[x][y]==newColor): 
            return image
        else:
            image[x][y]=newColor
            if(y+1<len(image[0]) and [x,y+1] not in checked): #x,y+1
                image = fill(image,x,y+1,color,newColor)
            if(y-1>=0 and [x,y-1] not in checked): #x,y-1
                image = fill(image,x,y-1,color,newColor)
            if(x+1<len(image) and [x+1,y] not in checked): #x+1,y
                image = fill(image,x+1,y,color,newColor)
            if(x-1>=0 and [x-1,y] not in checked): #x-1,y
                image = fill(image,x-1,y,color,newColor)
            return image
    checked=[]
    return fill(image,sr,sc,image[sr][sc],newColor,checked)
<file_sep>/FirstUniqueCharacter/FirstUniqueCharacter.py
def firstUniqChar(s):
    for i in range(len(s)):
        if s[i]=='1': continue
        if(i==s.rfind(s[i])): return i
        else: s=s.replace(s[i],'1')
    return -1
<file_sep>/Single Element in a Sorted Array/singleNonDuplicate.py
def singleNonDuplicate(self, nums: [int]) -> int:
    if(len(nums)==1): return nums[0]
    def check(nums,x,y):
        m=(x+y)//2
        if(m==0): return nums[m]
        if(m==len(nums)-1): return nums[m]
        if(nums[m-1]!=nums[m] and nums[m+1]!=nums[m]): 
            return nums[m]
        elif (nums[m-1]==nums[m] and m%2==0):
            return check(nums,x,m)
        elif (nums[m+1]==nums[m] and m%2==0):
            return check(nums,m,y)
        elif (nums[m-1]==nums[m] and m%2!=0):
            return check(nums,m+1,y)
        elif (nums[m+1]==nums[m] and m%2!=0):
            return check(nums,x,m-1)

        return check(nums,0,len(nums)-1)
<file_sep>/K closest points/readme.md
# Problem Statement

We have a list of points on the plane.  Find the K closest points to the origin (0, 0).


(Here, the distance between two points on a plane is the Euclidean distance.)


You may return the answer in any order.  The answer is guaranteed to be unique (except for the order that it is in.)

Input: points = [[3,3],[5,-1],[-2,4]], K = 2

Output: [[3,3],[-2,4]]

(The answer [[-2,4],[3,3]] would also be accepted.)
<file_sep>/Sort Colors/solution.py
class Solution:
    def sortColors(self, nums: [int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        x,y=0,len(nums)-1
        i=0
        while(i<=y):
            if(nums[i]==2):  
                nums[i]=nums[y]
                nums[y]=2
                y=y-1
            elif(nums[i]==0):
                nums[i]=nums[x]
                nums[x]=0
                x=x+1
                i=i+1
            else: i=i+1
<file_sep>/Permutation Sequence/Solution.py
class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        if n==1: return str(n)  
        def factorial(x):
            factorial=1
            for i in range(1,x+1):
                factorial*=i
            return factorial
        
        n_perm=[factorial(i) for i in range(n-1,0,-1)]
        n_list=[_ for _ in range(1,n+1,1)]
        
        perm=''
        i=0
        while (i<n):
            if (k==0):
                for x in range(len(n_list)-1,-1,-1):
                    perm=perm+str(n_list[x])
                break
            else:
                index=k//n_perm[i]+ (1 if k%n_perm[i]>0 else 0)
                perm=perm+str(n_list[index-1])
                n_list.remove(n_list[index-1])
                k=k-(k//n_perm[i])*n_perm[i]
            i+=1
        
        return perm
        
        
<file_sep>/K closest points/solution.py
class Solution:
    def kClosest(self, points: [[int]], K: int) -> [[int]]:
        dist_map={}
        dist_list=[]
        selected=[]
        for point in points:
            dist=point[0]*point[0]+point[1]*point[1]
            dist_list.append(dist)
            if dist in dist_map.keys():
                dist_map[dist].append(point)
            else: dist_map[dist]=[point]
            
        dist_list.sort()
        
        i=0
        while(len(selected)<K):
            selected.extend(dist_map[dist_list[i]])
            i+=1
            
        return selected
            
 # more pythonic way of doing it....
     def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
        
        def _euclidean(p):
            return math.sqrt(p[0]*p[0] + p[1] * p[1])
        
        return sorted(points, key=_euclidean)[0:K]
<file_sep>/Construct BST/Readme.md
Return the root node of a binary search tree that matches the given preorder traversal.


It's guaranteed that for the given test cases there is always possible to find a binary search tree with the given requirements.

Input: [8,5,1,7,10,12]

Output: [8,5,10,1,7,null,12]

Constraints:

1 <= preorder.length <= 100

1 <= preorder[i] <= 10^8

The values of preorder are distinct.
<file_sep>/PerfectSquare/Readme.md
# Problem Statement

Given a positive integer num, write a function which returns True if num is a perfect square else False.


Note: Do not use any built-in library function such as sqrt.

Input: 16

Output: true

Input: 14

Output: false
<file_sep>/Dungeon/Solution.py
class Solution:
    def calculateMinimumHP(self, dungeon: [[int]]) -> int:
        dp=[[float(inf)]*(len(dungeon[0])+1) for _ in range(len(dungeon)+1)]
        
        for i in range(len(dungeon)-1,-1,-1):
            for j in range(len(dungeon[0])-1,-1,-1):
                if(i==len(dungeon)-1 and j==len(dungeon[0])-1):
                    dp[i][j]=abs(dungeon[-1][-1]) if dungeon[-1][-1]<0 else 0
                else: 
                    update=min(dp[i+1][j],dp[i][j+1])
                
                    if(dungeon[i][j]-update>=0): dp[i][j]=0
                    else: dp[i][j] = abs(dungeon[i][j]-update)
                                       
        return dp[0][0]+1
                    
        
<file_sep>/FirstUniqueCharacter/Readme.md
 # Problem Statement - 
 
Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.

s = "leetcode"

return 0.

s = "loveleetcode"

return 2.
<file_sep>/Trie/Readme.md
# Trie (Prefix Tree)

https://www.cs.bu.edu/teaching/c/tree/trie/

https://en.wikipedia.org/wiki/Trie
<file_sep>/Sum Root to Leaf Numbers  Solution/Solution.py
class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        if(not root):return 0
        
        stack_val=''
        s=0
        
        def dfs(node,stack_val,s):
            if(not node): 
                return stack_val,s
            
            stack_val=stack_val+str(node.val)
            
            if(not node.left and not node.right): 
                s+=int(stack_val)
                
            stack_val,s=dfs(node.left,stack_val,s)
            stack_val,s=dfs(node.right,stack_val,s)
            stack_val=stack_val[0:len(stack_val)-1]
            return stack_val,s
        
        
        _,s=dfs(root,stack_val,s)
        return s
<file_sep>/Edit Distance/Solution.py
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        dp=[[0]*(len(word2)+1) for _ in range(len(word1)+1)]
        
        for i in range(len(word1)+1):
            for j in range(len(word2)+1):
                if i==0: dp[i][j]=j
                    
                elif j==0: dp[i][j]=i
                   
                elif word1[i-1]==word2[j-1]: dp[i][j] = dp[i-1][j-1]
                    
                else: dp[i][j]=1+min(dp[i-1][j-1],
                                    dp[i-1][j],
                                    dp[i][j-1])
        return dp[-1][-1]
                
<file_sep>/Invert Binary Tree/Readme.md
# Problem Statement

Invert a binary tree.


Input: 4,2,7,1,3,6,9

Output: 4,7,2,9,6,3,1

<file_sep>/Counting Bits/Readme.md
# Problem Statement

Given a non negative integer number num. 
For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.

Input: 5

Output: [0,1,1,2,1,2]
<file_sep>/Single Element in a Sorted Array/Readme.md
# Problem Statement

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. 
Find this single element that appears only once.

Input: [1,1,2,3,3,4,4,8,8]

Output: 2

<file_sep>/Cousins in Binary Tree/Cousins.py
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
        
leaf5 = TreeNode(val=5)
leaf4 = TreeNode(val=4)
node2 = TreeNode(val=2,left=None,right=leaf4)
node3 = TreeNode(val=3,left=None,right=leaf5)
root = TreeNode(val=1,left=node2,right=node3)


def cousins(root,x,i,parent=None):
    j=-1
    if(root.val==x):
        return i,parent
    if(root.left):
        j,parent=cousins(root.left,x,i+1,root.val)
    if(j!=-1):
        return j,parent
    if(root.right):
        j,parent=cousins(root.right,x,i+1,root.val)
    if(j!=-1):
        return j,parent
    return -1,-1
    
    
x_i,x_parent=cousins(root,4,0)
y_i,y_parent=cousins(root,5,0)
print (x_i,x_parent)
print (y_i,y_parent)
if(x_i==y_i and x_parent!=y_parent):
    print ('cousins')
<file_sep>/Surrounded Regions/solution.py
class Solution:
    def solve(self, board: [[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        row=len(board)
        if row==0: return
        col=len(board[0])
                    
        for i in range(row):
            for j in range(col):
                
                if board[i][j]=='O': board[i][j]='-'
            
        def floodFill(a,b):    
            board[a][b]='O'
            l,r,u,d=b-1,b+1,a-1,a+1
            if l>=0 and board[a][l]=='-': floodFill(a,l)
                
            if r<col and board[a][r]=='-': floodFill(a,r)
                
            if u>=0 and board[u][b]=='-': floodFill(u,b)
                
            if d<row and board[d][b]=='-': floodFill(d,b)
            
        for i in [0,row-1]:
             for j in range(col):
                if board[i][j]=='-': floodFill(i,j)           
                
        for i in range(1,row-1):
            for j in [0,col-1]:  
                
                if board[i][j]=='-': floodFill(i,j)
                    
        
        for i in range(row):
            for j in range(col):           
                if board[i][j]=='-': board[i][j]='X'
<file_sep>/Kth Smallest Element in a BST/kthSmallestElement.py
# Definition for a binary tree node.

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        self.k=k
        def inorder(root):
            inorder_list=[]
            if(root.left and self.k>0):
                inorder_list.extend(inorder(root.left))
            if(self.k>0):
                inorder_list.append(root.val)
                self.k-=1
            if(root.right and self.k>0):
                inorder_list.extend(inorder(root.right))
            return inorder_list
        
        return inorder(root)[-1]
    
    def kthSmallest1(self, root: TreeNode, k: int) -> int:
        def inorder(root):
            inorder_list=[]
            if(root.left): 
                inorder_list.extend(inorder(root.left))
            inorder_list.append(root.val)
            if(root.right):
                inorder_list.extend(inorder(root.right))
            return inorder_list
        
        return inorder(root)[k-1]
<file_sep>/Cheapest flights within K stops/Readme.md
# Problem Statement

There are n cities connected by m flights. Each flight starts from city u and arrives at v with a price w.


Now given all the cities and flights, together with starting city src and the destination dst, 
your task is to find the cheapest price from src to dst with up to k stops. If there is no such route, output -1.

Example 1:

Input: 

n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]

src = 0, dst = 2, k = 1

Output: 200
<file_sep>/Check Straight Line/checkStraightLine.py
def checkStraightLine(coordinates) -> bool:
    def check(coordinates,m=None,b=None,c=None):
        if(c==None):
            for x in coordinates:
                if(x[1]-x[0]*m!=b):
                    return False
        elif (c=='x'):
            for x in coordinates:
                if(x[0]!=m):
                    return False
        elif(c=='y'):
            for x in coordinates:
                if(x[1]!=m):
                    return False
        return True
    if (coordinates[1][1]-coordinates[0][1]==0):
        return check(coordinates,m=coordinates[1][1],c='y')
    elif (coordinates[1][0]-coordinates[0][0]==0):
        return check(coordinates,m=coordinates[1][0],c='x')
    else:
        m = (coordinates[1][1]-coordinates[0][1])/(coordinates[1][0]-coordinates[0][0])
        b = coordinates[0][1]-coordinates[0][0]*m
        return check(coordinates,m=m,b=b)
   
c = [[-7,-3],[-7,-1],[-2,-2],[0,-8],[2,-2],[5,-6],[5,-5],[1,7]]
checkStraightLine(c)
<file_sep>/contiguous array/Readme.md
# Problem Statement


Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

Input: [0,1,0]

Output: 2

Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.
<file_sep>/Interval List Intersections/intervalIntersection.py
class Solution:
    def intervalIntersection(self, A: [[int]], B: [[int]]) -> [[int]]:
        out=[]
        i=0
        for a in A:
            while(i<len(B)):
                if(B[i][0]>a[1]): break
                if(a[0]>B[i][1]): 
                    i+=1
                    continue
                out.append([max(a[0],B[i][0]),min(a[1],B[i][1])])
                if(B[i][1]>a[1]): 
                    break
                i+=1
        return out
<file_sep>/Queue Reconstruction By Height/Readme.md
# Problem Statement

Suppose you have a random list of people standing in a queue. 
Each person is described by a pair of integers (h, k), where h is the height of the person and k is the 
number of people in front of this person who have a height greater than or equal to h. 
Write an algorithm to reconstruct the queue.

Input:

[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]


Output:

[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
<file_sep>/Surrounded Regions/Readme.md
# Problem Statement

Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.


A region is captured by flipping all 'O's into 'X's in that surrounded region.

Input:

X X X X

X O O X

X X O X

X O X X

Output:

X X X X

X X X X

X X X X

X O X X

Surrounded regions shouldn’t be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. 
Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. 
Two cells are connected if they are adjacent cells connected horizontally or vertically.
