Problem # Given an m x n matrix, return all elements of the matrix in spiral order. Example: # Input: [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ] Output: [1, 2, 3, 6, 9, 8, 7, 4, 5] Input: [ [1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12] ] Output: [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7] ...
Problem # You are given n jobs where each job consists of a start time, end time, and a profit. You can choose to perform these jobs such that no two jobs overlap. Find the maximum profit you can achieve by scheduling these jobs. Example: # Input: jobs = [(1, 3, 50), (2, 5, 20), (4, 6, 70), (6, 7, 30)] Output: 120 Explanation: The optimal job schedule is to do the job from 1 to 3 and then the job from 4 to 6. ...
Problem # Given a network of n cities and a list of roads connecting these cities, find the maximum number of cities that can be connected directly or indirectly via these roads. You can assume that the roads are bidirectional and that each pair of cities has at most one direct road connecting them. Example: # Input: n = 4, roads = [[0, 1], [0, 2], [1, 2], [1, 3]] Output: 4 Explanation: All cities can be connected directly or indirectly by the given roads. ...
Problem # You are given an array nums of integers. Write a function to determine if the array can be partitioned into two subsets such that the sum of elements in both subsets is the same. Example: # Input: nums = [1, 5, 11, 5] Output: True Explanation: The array can be partitioned as [1, 5, 5] and [11]. Solution # The problem is a variation of the “Subset Sum” problem, which is a classic dynamic programming issue. ...
Problem # Given the root of a binary tree, find the length of the longest consecutive sequence path. The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path needs to be from parent to child (cannot be the reverse). Example: # 1 \ 3 / \ 2 4 \ 5 Longest consecutive sequence path is 3-4-5, so return 3. ...
Problem # Given a m x n grid filled with non-negative numbers, find a path from the top left corner to the bottom right corner which minimizes the sum of all numbers along its path. You can only move either down or right at any point in time. Some cells might be obstacles where the robot cannot enter. These cells are marked with a -1. Other cells contain integers representing the cost of passing through them. ...
Problem # Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis, forms a container, such that the container contains the most water. You may not slant the container. Example: Input: [1,8,6,2,5,4,8,3,7] Output: 49 Explanation: The max area of water the container can contain is 49. ...
Problem # Given a binary tree (not a binary search tree) and two nodes values, find the lowest common ancestor (LCA) of the two nodes in the tree. The lowest common ancestor is defined between two nodes p and q as the lowest node in the tree that has both p and q as descendants (where we allow a node to be a descendant of itself). Example # Input: Root of the Binary Tree, p = 5, q = 1 3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4 Output: 3 Explanation: The LCA of nodes 5 and 1 is 3. ...
Problem # Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph. Example: # Input: n = 5, edges = [[0, 1], [1, 2], [3, 4]] Output: 2 Explanation: There are two connected components: 0-1-2 and 3-4. Solution # Algorithm: Depth-First Search (DFS) ...
Problem # Given a string containing only digits, find the minimum number of characters to be inserted to make it a palindrome. Solution # To solve this problem, we need to find the longest palindromic subsequence in the given string. The minimum number of characters to be inserted to make the string a palindrome is equal to the length of the string minus the length of the longest palindromic subsequence. ...
Problem # Given an array of integers, where each element appears either once or twice, find all elements that appear twice in the array. The solution should achieve O(n) time complexity and O(1) extra space. Example: Input: [4,3,2,7,8,2,3,1] Output: [2,3] Explanation: The numbers 2 and 3 appear twice in the array. Input: [1,1,2] Output: [1] Explanation: The number 1 appears twice. Solution Approach # The solution involves using the array itself for hashing by marking visited numbers. ...
Problem: # Design a class to find the kth largest element in a stream of numbers. The class should have the following two methods: add(num): Adds the number num to the stream. getKthLargest(): Returns the kth largest element in the stream. Example: Initialize an instance with k=3 and the stream stream = [4, 5, 8, 2]. getKthLargest() should return 4. After adding 3, 5, 10, and 9 to the stream, getKthLargest() should return 5. ...
Problem # You are given an array of k linked lists, each containing nodes of sorted integers. Merge all the linked lists into one sorted linked list and return its head. Solution Approach # Divide: Recursively divide the list of lists into two halves until each sublist contains only one or zero lists. Conquer: Merge each pair of sublists using a merge function that combines two sorted lists into a single sorted list. ...
Problem # Given a string s, find the longest palindromic substring in s. Example: Input: s = "babad" Output: One of "bab" or "aba" (since both are valid longest palindromic substrings). Solution # Solution Approach # Algorithm: Expand Around Center This approach involves expanding around every possible center of a palindrome in the string. A palindrome can be centered around one letter (for odd length) or two letters (for even length). ...
Problem: # You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise). You have to rotate the image in-place, which means you have to modify the input 2D matrix directly without using another 2D matrix. Example: # Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [[7,4,1],[8,5,2],[9,6,3]] Solution: # Algorithm: Transpose and Reverse The algorithm works in two steps. First, transpose the matrix (swap rows with columns), and then reverse each row. ...
Problem # Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element. Example: # Input: nums = [3,2,1,5,6,4], k = 2 Output: 5 Solution # Algorithm: Quickselect This approach is based on the QuickSort algorithm. In QuickSort, we pick a pivot and partition the array around the pivot. The idea of Quickselect is similar, but instead of recursively doing both sides of the pivot, as in QuickSort, Quickselect only recurses into one side – the side with the element it is searching for. ...
Problem # Given a string s, find the longest palindromic substring in s. Example: Input: s = "babad" Output: One of "bab" or "aba" (since both are valid longest palindromic substrings). Solution # Algorithm Used: # Dynamic Programming Solution Approach: # The approach is to build a table that represents substrings of the given string. The table will be filled in a way that table[i][j] will be true if the substring from index i to j is a palindrome. ...
Problem # Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). Find the minimum element. The array may contain duplicates. Example: Input: [3,4,5,1,2] Output: 1 Solution # Algorithm: Modified Binary Search Solution Approach:** # - The idea is to use binary search. However, due to the rotation, a standard binary search won't work directly. - The strategy is to find the inflection point where the order of the array changes. ...
Problem # Given a directed graph, write a function to detect whether the graph contains a cycle. Example: Input: Graph with edges [[0, 1], [1, 2], [2, 0]] Output: True (There is a cycle 0 -> 1 -> 2 -> 0) Solution # Algorithm: Depth-First Search (DFS) Use DFS to detect the presence of a cycle in the graph. The idea is to traverse the graph along a particular path and if during the traversal we revisit a node, then there is a cycle in the graph. ...
Problem # Given an integer array nums, find the contiguous subarray within the array which has the largest product, and return its product. The subarray must contain at least one number. Example: Input: nums = [2, 3, -2, 4] Output: 6 Explanation: The subarray [2, 3] has the largest product = 6. Solution # Algorithm: Dynamic Programming The key to this problem is to handle the negative numbers. A product of two negative numbers turns positive, and this could potentially be larger than a currently known maximum product. ...
Problem # Design a circular queue using arrays. The user should be able to enqueue and dequeue elements. The queue should dynamically adjust its size to accommodate more elements when it’s full. Solution: # Designing a circular queue using arrays involves implementing a data structure that utilizes an array to store elements in a first-in-first-out (FIFO) manner, with the ability to wrap around to the beginning of the array when the end is reached. ...
Problem # Given an array of integers, find the pair of numbers that has the closest sum to a given target value, without exceeding it. Return the pair of numbers. Solution: # Algorithm: Two Pointers Time Complexity: O(n log n) due to sorting Space Complexity: O(1) or O(n) depending on sorting algorithm Steps: Sort the array: Sort the array of integers in ascending order. Initialize pointers: Create two pointers, left and right, pointing to the beginning and end of the array, respectively. ...
Problem # Given a binary tree, determine if it is height-balanced. In this context, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differs by more than one. Example: # Consider the following binary tree: 3 / \ 9 20 / \ 15 7 Output: True Explanation: This binary tree is balanced as the heights of the left and right subtrees of every node differ by no more than 1. ...
Problem # Given a string s, find the length of the longest substring without repeating characters. Example 1: Input: s = “abcabcbb” Output: 3 Explanation: The answer is “abc”, with the length of 3. Example 2: Input: s = “bbbbb” Output: 1 Explanation: The answer is “b”, with the length of 1. Example 3: Input: s = “pwwkew” Output: 3 Explanation: The answer is “wke”, with the length of 3. ...
Problem # find the maximum sum of values in a binary tree where each node has a value and two children. The goal is to find the maximum sum of values that can be obtained by traveling upwards from a leaf to the root. Solution # Here’s the Python code to design an efficient algorithm that finds the maximum sum of values from a leaf to the root in a binary tree: ...
Problem # Given a string containing three types of parentheses ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’, write an algorithm to check if the input string is valid. A string is valid if open brackets are closed by the same type of brackets, and open brackets must be closed in the correct order. Solution # Here’s the Python code for checking if a string containing different types of parentheses is valid: ...
Problem # You are given a string encoded with a simple shift cipher where each letter is shifted by a certain number of places. Write an algorithm to decode this string given the number of places each letter is shifted. Solution # Here’s the Python code to decode a string that has been encoded using a simple shift cipher: def decodeShiftCipher(text, shift): """ Decode a string that was encoded using a simple shift cipher. ...
Problem # Given an array of integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining. Solution # Here’s the Python code for solving the problem of computing how much water can be trapped after raining, given an array of integers representing an elevation map: def trapRainWater(heights): """ Compute how much water can be trapped after raining in an elevation map. ...
Problem # Given an array of integers heights representing the histogram’s bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram. Solution # Here’s the Python code for solving the problem of finding the area of the largest rectangle in a histogram: def largestRectangleArea(heights): """ Calculate the area of the largest rectangle in the histogram. Args: heights (List[int]): List of integers representing the heights of the bars in the histogram. ...
Problem # Given a binary tree, partition it into two subtrees such that the sum of values in the left subtree is equal to the sum of values in the right subtree. If multiple answers exist, return any one. If no answer exists, return NULL. Solution # class TreeNode: def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = right def partition_tree(root): if not root: return None, None # Calculate sum of all nodes in the tree total_sum = sum_tree(root) # Find the target sum for the left subtree target_sum = total_sum // 2 # Search for the target sum in the tree left_subtree, right_subtree = find_target_subtree(root, target_sum) # Check if a valid partition exists if left_subtree and sum_tree(left_subtree) == target_sum: return left_subtree, right_subtree return None, None def sum_tree(root): if not root: return 0 return root. ...
Problem # Design a circular deque (double-ended queue) with ‘addFront’, ‘addRear’, ‘deleteFront’, and ‘deleteRear’ operations. The circular deque should support these methods in O(1) time complexity. Solution # Here’s the Python code for the CircularDeque class: class CircularDeque: def __init__(self, size): self.size = size self.count = 0 self.front = -1 self.rear = 0 self.deque = [None] * size def isFull(self): return self.count == self.size def isEmpty(self): return self.count == 0 def addFront(self, value): if self. ...
Problem # You are given an array nums of n positive integers. You can perform two types of operations on any element of the array any number of times: If the element is even, divide it by 2. If the element is odd, multiply it by 2. The deviation of the array is the maximum difference between any two elements in the array. Find the minimum deviation the array can have after performing some number of operations. ...
Problem # Given two DNA strings, strand1 and strand2, return the minimum number of genetic mutations needed to change strand1 into strand2. A genetic mutation is defined as changing one character (i.e., ‘A’, ‘T’, ‘C’, or ‘G’) into another character. Solution # If the lengths of strand1 and strand2 can be different, the problem becomes a bit more complex. We need to consider not only mutations (changing one character into another) but also insertions and deletions to transform one strand into the other. ...
Problem # Given a 2D grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. Solution 1 # Here’s the Python code to count the number of islands in a 2D grid map, where ‘1’s represent land and ‘0’s represent water: def numIslands(grid): if not grid: return 0 rows, cols = len(grid), len(grid[0]) visited = set() islands = 0 def dfs(r, c): # If the current cell is out of bounds, water, or already visited, return if (r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0' or (r, c) in visited): return # Mark the cell as visited visited. ...
Problem # Given two sequences, find the length of their longest common subsequence (LCS). A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. Solution # Here is the Python code for finding the length of the longest common subsequence (LCS) between two sequences: def lcs_length(X, Y): m = len(X) n = len(Y) # Create a 2D array to store lengths of LCS of subproblems L = [[0] * (n + 1) for i in range(m + 1)] # Fill L[m+1][n+1] in bottom up fashion for i in range(m + 1): for j in range(n + 1): if i == 0 or j == 0: L[i][j] = 0 elif X[i - 1] == Y[j - 1]: L[i][j] = L[i - 1][j - 1] + 1 else: L[i][j] = max(L[i - 1][j], L[i][j - 1]) # L[m][n] contains the length of LCS for X[0. ...
Problem # Given two strings s and t, return the minimum window in s which will contain all the characters in t. If there is no such window in s that covers all characters in t, return the empty string. Solution # The Python function min_window successfully finds the minimum window in the string s that contains all the characters of the string t. In the provided example with s = "ADOBECODEBANC" and t = "ABC", the function returned "BANC" as the smallest substring of s that includes all the characters in t. ...
Problem # Given a list of integers S and a target number k, write a function that returns a subset of S that adds up to k. If such a subset cannot be made, then return null. Integers can appear more than once in the list. You may assume all numbers in the list are positive. Solution 1 # Here is a Python solution using recursion and backtracking: def find_subset(candidates, target): def _find_subset(idx, target, path): if target == 0: return [path] if idx == len(candidates) or target < 0: return [] # Without the current number. ...
Problem # In a given grid, each cell can have one of three values: 0 (empty), 1 (fresh orange), or 2 (rotten orange). Every minute, any fresh orange that is adjacent to a rotten orange becomes rotten. Find the minimum number of minutes that must elapse until no cell has a fresh orange. Solution # To solve this problem, we can use the Breadth-First Search (BFS) algorithm. The idea is to iteratively spread the rot from the rotten oranges to the adjacent fresh oranges and track the time taken for all fresh oranges to become rotten. ...
Problem # Given the availability time slots arrays slots1 and slots2 of two people and a meeting duration, return the earliest time slot that works for both of them and is of duration. Solution # To solve this problem, we need to find a common time slot between two schedules (slots1 and slots2) that is at least as long as the given meeting duration. A practical approach is to sort both schedules based on start times and then iterate through them to find overlapping intervals that can accommodate the meeting duration. ...
Problem # Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals to k. Solution # To solve the problem of finding the total number of continuous subarrays whose sum equals a given integer k, a common and efficient approach is to use a cumulative sum combined with a hash table. This method allows us to efficiently track the sum of subarrays and check for the existence of the required sum. ...
Problem # You are given a grid filled with non-negative numbers. Find a path from the top left to the bottom right, which minimizes the sum of all numbers along its path. Solution # To solve this problem, a typical approach is to use dynamic programming. The idea is to create a 2D array (or modify the given grid in place, if mutation is acceptable) where each cell contains the minimum sum required to reach that cell from the top-left corner. ...
Problem # Given an unsorted array of integers, find the length of the longest consecutive elements sequence. Solution # To solve the problem of finding the length of the longest consecutive elements sequence in an unsorted array of integers, we can use a hash set for efficient lookups. The algorithm involves iterating through the array and dynamically checking for consecutive sequences. Here’s how we can implement it in Python: ...
Problem # Design an algorithm to serialize a binary tree into a string and deserialize that string back into the original tree structure. Solution # To solve the problem of serializing and deserializing a binary tree, we can use a preorder traversal to serialize the tree. During serialization, we’ll represent null nodes as a specific marker (e.g., ‘X’). For deserialization, we can use the serialized string and rebuild the tree by following the order of elements. ...
Problem # Given a set of closed intervals, find the smallest set of numbers that covers all the intervals. If there are multiple smallest sets, return any of them. For example, given the intervals [0, 3], [2, 6], [3, 4], [6, 9], one set of numbers that covers all these intervals is {3, 6}. Solution # Here is the Python code to find the smallest set of numbers that covers all the given intervals: ...
Problem # You are given an array of pairs representing the start and end times of various meetings. Given an integer K, a person can attend at most K meetings. Find the optimal meeting points that allow the person to attend the maximum number of meetings. Solution # The problem is about finding the maximum number of non-overlapping meetings a person can attend, given a limit on the total number of meetings they can attend (K). ...
Problem # Given a weighted undirected graph, find a minimum spanning tree that connects all nodes while minimizing the total weight of the edges Solution # Below is the complete Python code that finds a minimum spanning tree (MST) for a given weighted undirected graph using a variant of Prim’s algorithm: import heapq def minimum_spanning_tree(graph): # Assuming the graph is represented as an adjacency list where each entry is # a tuple of (node, weight), and graph is a dictionary # Initialize variables start_node = next(iter(graph)) # Starting from the first node in the graph mst = set() # To store the edges of the Minimum Spanning Tree visited = set([start_node]) edges = [(weight, start_node, to) for to, weight in graph[start_node]] heapq. ...
Problem # Given two words, find the shortest chain of words you can create by changing only one letter at a time, such that each word in the chain is a valid English word. You can use a dictionary or online database to check word validity. Solution # Solving the “Word Ladder” problem in Python typically involves using a breadth-first search (BFS) algorithm to traverse through word transformations. Here’s the general idea of the solution: ...
Problem # Given a mathematical expression represented as a string (e.g., “(2 + 3) * 4 / 2”), design an algorithm to evaluate the expression and return the result. Solution # import operator def evaluate_expression(expression): def apply_operator(ops, values): # Apply the operator to the top two values in the values stack operator = ops.pop() right = values.pop() left = values.pop() values.append(operations[operator](left, right)) operations = {'+': operator.add, '-': operator.sub, '*': operator. ...
Problem # Place N queens on an N x N chessboard such that no two queens can attack each other. Solution # The Python code for solving the “N Queens” problem is provided below. This problem involves placing N queens on an N x N chessboard such that no two queens can attack each other. A solution to the problem means that no two queens share the same row, column, or diagonal. ...
Problem # Given a set of coin denominations and a target amount, find the minimum number of coins needed to make that amount. Solution # Here’s the Python code for finding the minimum number of coins needed to make a target amount, given a set of coin denominations: def min_coins(coins, amount): # Create a table to store the minimum number of coins for each amount dp = [float('inf')] * (amount + 1) dp[0] = 0 # Base case: 0 coins are needed to make amount 0 for i in range(1, amount + 1): for coin in coins: if i - coin >= 0: dp[i] = min(dp[i], dp[i - coin] + 1) return dp[amount] if dp[amount] ! ...