LeetCode

File size
18.2KB
Lines of code
574

LeetCode

Ace the coding interview.

Common patterns

  1. Prefix Sum

  2. Query sum of elements in a subarray

def create_prefix_sum(inp_array):
    for i in range(1, len(inp_array)):
        inp_array[i] += inp_array[i-1]
    return inp_array

def is_palindrome(inp_string):
    start = 0 # pointer 1
    end = len(inp_string) - 1 # pointer 2
    while start < end:
        if inp_string[start] != inp_string[end]:
            return False
        else:
            start += 1
            end -= 1
    return True

def max_subarray_sum_sliding_window(inp_array, k):
    n = len(inp_array)
    window_sum = sum(inp_array[:k])
    max_sum = window_sum
    max_start_index = 0
    for i in range(n-k):
        window_sum = window_sum - inp_array[i] + inp_array[i+k]
        if window_sum > max_sum:
            max_sum = window_sum
            max_start_index = i + 1
    return inp_array[max_start_index:max_start_index+k], max_sum

def find_cycling_node(head_node):
    slow = head_node # slow pointer
    fast = head_node # fast pointer
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

def reverse_linked_list(head_node):
    prev = None
    current = head_node
    while current is not None:
        next = current.next
        current.next = prev
        prev = current
        current = next
    return prev

def next_greater_element(inp_array):
    n = len(inp_array)
    stack = []
    result = [-1] * n
    for i in range(n):
        while stack and inp_array[i] > inp_array[stack[-1]]:
            result[stack.pop()] = inp_array[i]
        stack.append(i)
    return result

def build_min_heap(arr, k):
    for i in range(k//2 - 1, -1, -1):
        heapify(arr, k, i)

def heapify(arr, n, i):
    smallest = i
    left = 2 * i + 1
    right = 2 * i + 2
    if left < n and arr[left] < arr[smallest]:
        smallest = left
    if right < n and arr[right] < arr[smallest]:
        smallest = right
    if smallest != i:
        arr[i], arr[smallest] = arr[smallest], arr[i]
        heapify(arr, n, smallest)

def find_Kth_Largest(nums, k):
    heap = nums[:k]
    build_min_heap(heap, k)
    for i in range(k, len(nums)):
        if nums[i] > heap[0]:
            heap[0] = nums[i]
            heapify(heap, k, 0)
    return heap[0]

def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = []
    for interval in intervals:
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)
        else:
            merged[-1][1] = max(merged[-1][1], interval[1])
    return merged

def modified_binary_search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

def preorder_traversal(root):
    if root:
        print(root.val)
        preorder_traversal(root.left)
        preorder_traversal(root.right)

def inorder_traversal(root):
    if root:
        inorder_traversal(root.left)
        print(root.val)
        inorder_traversal(root.right)

def postorder_traversal(root):
    if root:
        postorder_traversal(root.left)
        postorder_traversal(root.right)
        print(root.val)

def level_order_traversal(root): 
    """
    note the iterative approach is more 
    common for level order traversal of 
    a binary tree

    this recursive approach is less 
    commonly seen
    """
    def traverse_level(node, level):
        if node:
            if level == 1:
                print(node.val)
            elif level > 1:
                traverse_level(node.left, level - 1)
                traverse_level(node.right, level - 1)
    def height(node):
        if not node:
            return 0
        return 1 + max(height(node.left), height(node.right))
    h = height(root)
    for i in range(1, h + 1):
        traverse_level(root, i)

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    print(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

def bfs_recursive(graph, queue, visited):
    """
    note the iterative approach is more 
    common for bfs of a binary tree using
    a queue

    this recursive approach is less 
    commonly seen
    """
    if not queue:
        return
    node = queue.pop(0)
    print(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            visited.add(neighbor)
            queue.append(neighbor)
    bfs_recursive(graph, queue, visited)

def start_bfs(graph, start_node):
    visited = set([start_node])
    queue = [start_node]
    bfs_recursive(graph, queue, visited)

def floodFill(image, sr, sc, newColor):
    originalColor = image[sr][sc]
    if originalColor == newColor:
        return image
    def fill(r, c):
        if image[r][c] == originalColor:
            image[r][c] = newColor
            if r > 0:
                fill(r - 1, c)
            if r < len(image) - 1:
                fill(r + 1, c)
            if c > 0:
                fill(r, c - 1)
            if c < len(image[0]) - 1:
                fill(r, c + 1)
    fill(sr, sc)
    return image

def permute(nums):
    result = []
    def backtrack(path):
        if len(path) == len(nums):
            result.append(path)
            return
        for num in nums:
            if num not in path:
                backtrack(path + [num])
    backtrack([])
    return result

More on