<jupyter_start><jupyter_text>Algorithms &copy;  [<NAME>](<EMAIL>)  Industrial and Enterprise Systems Engineering, The Grainger College of Engineering,  UIUC   1. Trapping Rain WaterGiven n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.<jupyter_code>def trap(height):
    # ans to store the trapped rain water
    ans = 0
    # curr_index finds the index of the bar whose height is greater than the stack's top 
    curr_index = 0
    # stack to store the indices of those bars whose heights are lesser than the stack's top
    st = list()
    # go through all indices until the end
    while curr_index<len(height):
        # while stack is not empty and height at current index is greater than the height at top index
        while len(st)!=0 and height[curr_index]>height[st[-1]]:
            print(f"Popping {st[-1]} from the stack")
            # get the stack's top
            top = st.pop()
            # if stack becomes empty, break the loop. 
            # this situation will come when ans has been updated and the previous bars need to be removed from stack
            if len(st)==0:
                break
            # distance is the width of the rectangle bounded between current index and the stack's top (new top+1)
            distance = curr_index-st[-1]-1
            print(f"distance is {distance}")
            # height of the rectangle bounded. 
            bounded_height = min(height[curr_index], height[st[-1]]) - height[top]
            print(f"Bounded height is {bounded_height}")
            # add the area of the rectangle to the ans
            ans += distance*bounded_height
            print(f"ans is {ans}")
        print(f"Current height is lesser than stack's top index")
        print(f"Appending {curr_index} to the stack")
        # append the current index to the stack
        st.append(curr_index)
        print(f"Incrementing {curr_index} to {curr_index + 1}")
        curr_index += 1
    
    return ans
height = [0,1,0,2,1,0,1,3,2,1,2,1]
trap(height)<jupyter_output>Current height is lesser than stack's top index
Appending 0 to the stack
Incrementing 0 to 1
Popping 0 from the stack
Current height is lesser than stack's top index
Appending 1 to the stack
Incrementing 1 to 2
Current height is lesser than stack's top index
Appending 2 to the stack
Incrementing 2 to 3
Popping 2 from the stack
distance is 1
Bounded height is 1
ans is 1
Popping 1 from the stack
Current height is lesser than stack's top index
Appending 3 to the stack
Incrementing 3 to 4
Current height is lesser than stack's top index
Appending 4 to the stack
Incrementing 4 to 5
Current height is lesser than stack's top index
Appending 5 to the stack
Incrementing 5 to 6
Popping 5 from the stack
distance is 1
Bounded height is 1
ans is 2
Current height is lesser than stack's top index
Appending 6 to the stack
Incrementing 6 to 7
Popping 6 from the stack
distance is 2
Bounded height is 0
ans is 2
Popping 4 from the stack
distance is 3
Bounded height is 1
ans is 5
Popping 3 from the stack
Cu[...]<jupyter_text>Longest Palindromic Substring | Set 1Given a string, find the longest substring which is palindrome.<jupyter_code>def longestSubStr(str):
    # n stores the length of the input string
    n = len(str)
    # table[i][j] will be true if str[i...j] is palindrome
    table = [[0 for i in range(n)] for j in range(n)]

    # palidnromes of size 1 
    for i in range(n):
        table[i][i] = True
    
    # stores the length of the longest palindrome
    maxLength = 1

    # check for substring of size 2
    start = 0  # stores the start index of the longest palindrome
    # go through all the indices, except the last one.
    for i in range(n-1):
        # if character at i is same as the next one
        if str[i] == str[i+1]:
            # update table
            table[i][i+1] = True
            # update start
            start = i
            maxLength = 2
    
    # check for substring of size k
    for k in range(3, n+1):
        # fix the starting index
        i = 0
        while i<n-k+1:
            # get the last index
            j = i+k-1
            # if the str[i+1 .... j-1] is palindrome and str[i]==str[j], then update table[i][j]
            if table[i+1][j-1] == True and str[i]==str[j]:
                table[i][j] = True
                # if k is greater than maxLength, update maxLength
                if k>maxLength:
                    start = i
                    maxLength = k
            i += 1
    print("Longest palindrome substring is: {}".format(str[start:start+maxLength]))
    return maxLength


st = "forgeeksskeegfor"
l = longestSubStr(st)
print(f"Length is {l}")<jupyter_output>Longest palindrome substring is: geeksskeeg
Length is 10<jupyter_text>3. Islands in a graph using BFSGiven a boolean 2D matrix, find the number of islands. A group of connected 1s forms an island. For example, the below matrix contains 5 islandsExample:  ```Input : mat[][] = {{1, 1, 0, 0, 0},                   {0, 1, 0, 0, 1},                   {1, 0, 0, 1, 1},                   {0, 0, 0, 0, 0},                   {1, 0, 1, 0, 1} Output : 5```<jupyter_code>from collections import deque
R = 5
C = 5
# A function to check if a given cell
# (u, v) can be included in DFS
def isSafe(mat, i, j, visited):
    return i>=0 and j>=0 and i<R and j<C and mat[i][j] and not visited[i][j]

# This function returns number islands (connected
# components) in a graph. It simply works as
# BFS for disconnected graph and returns count
# of BFS calls.
def countIslands(mat):
    # Mark all cells as not visited
    visited = [[False for i in range(C)] for j in range(R)]
    # Call BFS for every unvisited vertex
    # Whenever we see an univisted vertex,
    # we increment res (number of islands)
    # also.
    res = 0
    for i in range(R):
        for j in range(C):
            if mat[i][j] and not visited[i][j]:
                BFS(mat, visited, i, j)
                res += 1
    return res

def BFS(mat, visited, i, j):
    # These arrays are used to get row and
    # column numbers of 8 neighbours of
    # a given cell
    row = [-1, -1, -1, 0, 0, 1, 1, 1]
    col = [-1, 0, 1, -1, 1, -1, 0, 1]

    # Simple BFS first step, we enqueue
    # source and mark it as visited
    q = deque()
    q.append([i, j])
    visited[i][j] = True

    # Next step of BFS. We take out
    # items one by one from queue and
    # enqueue their univisited adjacent
    while len(q)>0:
        temp = q.popleft()
        i = temp[0]
        j = temp[1]

        # Go through all 8 adjacent
        for k in range(8):
            if isSafe(mat, i+row[k], j+col[k], visited):
                visited[i+row[k]][j+col[k]] = True
                q.append([i+row[k], j+col[k]])
# Driver code
if __name__ == '__main__':
     
    mat = [ [ 1, 1, 0, 0, 0 ],
            [ 0, 1, 0, 0, 1 ],
            [ 1, 0, 0, 1, 1 ],
            [ 0, 0, 0, 0, 0 ],
            [ 1, 0, 1, 0, 1 ]]
 
    print (countIslands(mat))<jupyter_output>5<jupyter_text>4. Median of two sorted arrays of same sizeThere are 2 sorted arrays A and B of size n each. Write an algorithm to find the median of the array obtained after merging the above 2 arrays(i.e. array of length 2n). The complexity should be O(log(n)).   5. Merge k Sorted ListsYou are given an array of `k` linked-lists `lists`, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.*  6. Merge IntervalsGiven an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input. ```Example 1:Input: intervals = [[1,3],[2,6],[8,10],[15,18]]Output: [[1,6],[8,10],[15,18]]Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].```  7. Minimum Number of Platforms Required for a Railway/Bus StationMinimum Number of Platforms Required for a Railway/Bus StationDifficulty Level : MediumLast Updated : 06 Aug, 2021Given the arrival and departure times of all trains that reach a railway station, the task is to find the minimum number of platforms required for the railway station so that no train waits. We are given two arrays that represent the arrival and departure times of trains that stop.```Examples: Input: arr[] = {9:00, 9:40, 9:50, 11:00, 15:00, 18:00} dep[] = {9:10, 12:00, 11:20, 11:30, 19:00, 20:00} Output: 3 Explanation: There are at-most three trains at a time (time between 11:00 to 11:20)Input: arr[] = {9:00, 9:40} dep[] = {9:10, 12:00} Output: 1 Explanation: Only one platform is needed. ```  8. Design a data structure that supports insert, delete, search and getRandom in constant time```Design a data structure that supports the following operations in Θ(1) time.insert(x): Inserts an item x to the data structure if not already present.remove(x): Removes item x from the data structure if present. search(x): Searches an item x in the data structure.getRandom(): Returns a random element from current set of elements ```  9. Iterative Letter Combinations of a Phone NumberGiven an integer array containing digits from [0, 9], the task is to print all possible letter combinations that the numbers could represent. A mapping of digit to letters (just like on the telephone buttons) is being followed. Note that 0 and 1 do not map to any letters. All the mapping are shown in the image below: ![image](https://media.geeksforgeeks.org/wp-content/cdn-uploads/Mobile-keypad-267x300.png)Example: Input: arr[] = {2, 3} Output: ad ae af bd be bf cd ce cfInput: arr[] = {9} Output: w x y z   10. Word Ladder (Length of shortest chain to reach a target word)Given a dictionary, and two words ‘start’ and ‘target’ (both of same length). Find length of the smallest chain from ‘start’ to ‘target’ if it exists, such that adjacent words in the chain only differ by one character and each word in the chain is a valid word i.e., it exists in the dictionary. It may be assumed that the ‘target’ word exists in dictionary and length of all dictionary words is same. ```Example: Input: Dictionary = {POON, PLEE, SAME, POIE, PLEA, PLIE, POIN}       start = TOON       target = PLEAOutput: 7TOON - POON - POIN - POIE - PLIE - PLEE - PLEAInput: Dictionary = {ABCD, EBAD, EBCD, XYZA}       Start = ABCV       End = EBADOutput: 4ABCV - ABCD - EBCD - EBAD```  11. Time Based Key-Value StoreDesign a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the key's value at a certain timestamp.Implement the TimeMap class:* TimeMap() Initializes the object of the data structure.* void set(String key, String value, int timestamp) Stores the key key with the value value at the given time timestamp.* String get(String key, int timestamp) Returns a value such that set was called previously, with timestamp_prev <= timestamp. If there are multiple such values, it returns the value associated with the largest timestamp_prev. If there are no values, it returns ""```Example 1:Input["TimeMap", "set", "get", "get", "set", "get", "get"][[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]Output[null, null, "bar", "bar", null, "bar2", "bar2"]ExplanationTimeMap timeMap = new TimeMap();timeMap.set("foo", "bar", 1);  // store the key "foo" and value "bar" along with timestamp = 1.timeMap.get("foo", 1);         // return "bar"timeMap.get("foo", 3);         // return "bar", since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 is "bar".timeMap.set("foo", "bar2", 4); // store the key "foo" and value "ba2r" along with timestamp = 4.timeMap.get("foo", 4);         // return "bar2"timeMap.get("foo", 5);         // return "bar2"```<jupyter_code>def floorkey(dictionary, key):
    if key in dictionary:
        return key
    return max(k for k in dictionary if k<key)

class TimeMap:
    def __init__(self):
        # initialize map as empty dictionary which stores (key: {timestamp: value})
        self.map = {}
    def set(self, key, value, timestamp):
        # if key is not in map, add (key, empty dictionary) to map
        if key not in self.map:
            self.map[key] = {}
        # get the dictionary stored at key and add timestamp-value pair to the map
        self.map.get(key)[timestamp] = value
    def get(self, key, timestamp):
        # get the dictionary stored at key
        dictionary = self.map.get(key)
        # if dictionary is not present, return None
        if len(dictionary)==0:
            return ""
        # get the floor key (key just less than or equal to timestamp)
        floorKey = floorkey(dictionary, timestamp)
        # if it is None, return None
        if floorKey is None:
            return ""
        # return the value stored at timestamp
        return dictionary.get(floorKey)

t = TimeMap()
t.set("foo", "bar", 1)
print(t.get("foo", 1))
print(t.get("foo", 3))
t.set("foo", "bar2", 4)
print(t.get("foo", 4))
print(t.get("foo", 5))<jupyter_output>bar
bar
bar2
bar2
{'fraction_non_alphanumeric': 0.09874476987447699, 'fraction_numerical': 0.025561049828832255, 'mean_word_length': 2.8778761061946905, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 20, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '256184', 'license': 'MIT', 'n_tokens_mistral': 4183, 'n_tokens_neox': 3879, 'n_words': 1795, 'path': 'algorithms/algorithms.ipynb', 'repo_name': 'OmkarMehta/ds-algo', 'size': '13163'}