anchitarnav

# Given a combination of digits e.g. 23
# Generate all possible combinations of alphabets it can create on an old telephone
# e.g. 23 ==> ["ad","ae","af","bd","be","bf","cd","ce","cf"]

# Done Using Backtracking Approach in Python


class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        mappings = {

anchitarnav

# Given a string s, count the total number of all unique characters in all the substrings of s
#e.g. ABCA => A[1] + B[1] + C[1] + A[1] + AB[2] + BC[2] + CA[2] + ABC[3] + BCA[3] + ABCA[3]) = 19

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        total_count = 0
        
        dp = defaultdict(int)
        char_last_seen = dict() # If not seen -> 0
        

anchitarnav

# LeetCode : 152
# PROBLEM: Given an integer array nums, 
# find a contiguous non-empty subarray within the array that has the largest product, and return the product.

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        # Similar to Kadane's Algorithm.
        # When to discard a temp array -> If product becomes 0
        
        # Problem arises if a subarray (with no zeros) has odd number of -ve numbers

anchitarnav

# Selection Sort --> Python Implementation

# The smallest element from the UNSORTED array shall always be on the right of the SORTED array
# This is similar to heap sort where the smallest element comes out everytime.

def selection_sort(array: list):
    for smallest_unsorted in range(0, len(array)):

        smallest_index = smallest_unsorted
        smallest_element = array[smallest_index]

anchitarnav

# Merge Sort -> Python implementation
# Time Complexity: O(nlogn)
# Space Complexity: O(n)

def merge_sort(array: list) -> list:
    def _merge(_array1: list, _array2: list) -> list:
        new_array = []
        ptr1 = ptr2 = 0

        while ptr1 < len(_array1) and ptr2 < len(_array2):

anchitarnav

# Bubble Sort -> Python Implementation
# Time Complexity: O(n^2)
# Space Complexity: O(1)

def bubble_sort(array: list) -> list:
    def swap(index1, index2):
        nonlocal array
        array[index1], array[index2] = array[index2], array[index1]

    for _end in range(len(array) - 1, 0, -1):

anchitarnav

# Sliding Windows

x = [1,2,3,4,5,6,7,8]

# Maintain a window of size n (e.g. 3) such that the window can slide to the other end
# 3,2,1 --> 2,1,8 --> 1,8,7 --> 8,7,6

win_size = 3
start = win_size
end = len(x)

anchitarnav

# Hierholzer’s Algorithm for directed graph
# Eulers Circuit
# Eulers Path
# Find if a graph has a Euler Path/Circuit -> O(V + E)
# Print the graphs Euler Path/Circuit

# Python Implementation

from collections import defaultdict
from enum import Enum, auto

anchitarnav

# Krushkal's Algorithm for Minimum Spanning Tree (MST)
# Python Implementation

from collections import defaultdict
from heapq import heappop, heappush


class Graph:
    def __init__(self):
        self.edge_heap = list()

anchitarnav

# Prim's Algo for Minimum Spanning Tree (MST)
# Python implementation

from collections import defaultdict
from heapq import heappop, heappush


class Graph:
    def __init__(self):
        self.graph = defaultdict(list)