Neetcode2E

Cheatsheet Content

1. Final Array State After K Multiplication Operations I Description: Given an array $nums$ and an integer $k$, apply $k$ operations. In each operation, choose an index $i$, and replace $nums[i]$ with $nums[i] \times 2$. The goal is to maximize the final sum of the array. Approach: To maximize the sum, always multiply the largest element by 2. This is a greedy approach. Use a max-heap (priority queue) to efficiently get and update the largest element. import heapq def finalArrayState(nums, k): max_heap = [-num for num in nums] # Python's heapq is a min-heap heapq.heapify(max_heap) for _ in range(k): largest = -heapq.heappop(max_heap) heapq.heappush(max_heap, -(largest * 2)) return -sum(max_heap) 2. Take Gifts From the Richest Pile Description: Given an integer array $gifts$ representing the amount of gifts in each pile, and an integer $k$. In one operation, you can choose a pile with the maximum number of gifts, take the floor of its square root, and replace the pile with this new amount. Repeat $k$ times. Return the sum of gifts remaining after $k$ operations. Approach: Similar to the previous problem, this also involves repeatedly modifying the largest element. A max-heap is ideal for this. Calculate the square root and push the new value back to the heap. import heapq import math def takeGifts(gifts, k): max_heap = [-g for g in gifts] heapq.heapify(max_heap) for _ in range(k): largest = -heapq.heappop(max_heap) new_val = math.floor(math.sqrt(largest)) heapq.heappush(max_heap, -new_val) return -sum(max_heap) 3. Last Stone Weight Description: You are given an array of integers $stones$ where $stones[i]$ is the weight of the $i$-th stone. In each turn, we choose the two heaviest stones and smash them. If $x == y$, both stones are destroyed. If $x \neq y$, the stone of weight $x$ is destroyed, and the stone of weight $y$ has new weight $y-x$. Return the weight of the last remaining stone, or 0 if no stones are left. Approach: This is a classic max-heap problem. Repeatedly extract the two largest elements, perform the operation, and insert the result back if it's non-zero. The heap maintains the order efficiently. import heapq def lastStoneWeight(stones): max_heap = [-s for s in stones] heapq.heapify(max_heap) while len(max_heap) > 1: y = -heapq.heappop(max_heap) x = -heapq.heappop(max_heap) if y > x: heapq.heappush(max_heap, -(y - x)) return -max_heap[0] if max_heap else 0 4. Sum of All Subset XOR Totals Description: The XOR total of an array is the bitwise XOR of all its elements. If the array is empty, the XOR total is 0. Given an array $nums$, return the sum of all XOR totals for every subset of $nums$. Approach: For each bit position, if at least one number in $nums$ has that bit set, then half of the subsets will have that bit set in their XOR total. This means if $N$ is the length of $nums$, each bit set in any number will contribute $2^{N-1}$ to the total sum. A more direct approach is to use recursion/backtracking to generate all subsets and calculate their XOR totals. def subsetXORSum(nums): total_sum = 0 n = len(nums) for i in range(1 > j) & 1: # Check if j-th element is in the current subset current_xor ^= nums[j] total_sum += current_xor return total_sum # Alternative (more mathematical) approach: def subsetXORSum_math(nums): ans = 0 # For each bit position, if any number has that bit set, # then half of the subsets will have that bit set in their XOR total. # The sum will be (2^(n-1)) * (OR of all numbers) # This is incorrect logic for sum of XOR totals. # The correct logic is to sum up all subset XORs. # The bitwise OR of all elements is not directly useful for the sum. # The recursive/iterative generation is the most straightforward. # Corrected Mathematical Insight (if numbers are small enough for bit manipulation): # If a bit is set in any number of the array, it will be set in exactly 2^(N-1) subset XOR sums. # So, the sum is (OR of all numbers) * (2^(N-1)). # This is a known property for XOR sum of all subsets. # Let's re-verify this property: # Example: nums = [1,2,3] # Subsets: [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3] # XORs: 0, 1, 2, 3, 3, 2, 1, 0 # Sum: 0+1+2+3+3+2+1+0 = 12 # OR of all numbers: 1 | 2 | 3 = 3 # 2^(N-1) = 2^(3-1) = 2^2 = 4 # (OR of all numbers) * (2^(N-1)) = 3 * 4 = 12. This property holds. xor_of_all_elements = 0 for num in nums: xor_of_all_elements |= num return xor_of_all_elements * (1 0 else 0 5. Count Prefix and Suffix Pairs I Description: Given an array of strings $words$. A pair of indices $(i, j)$ is a prefix-suffix pair if $i Approach: Iterate through all possible pairs $(i, j)$ with $i def countPrefixSuffixPairs(words): count = 0 n = len(words) for i in range(n): for j in range(i + 1, n): if words[j].startswith(words[i]) and words[j].endswith(words[i]): count += 1 return count 6. Counting Words With a Given Prefix Description: Given an array of strings $words$ and a string $pref$. Return the number of strings in $words$ that have $pref$ as a prefix. Approach: Iterate through each word in the array and use the string method $startswith()$ to check if the word begins with the given prefix. def countWordsWithPrefix(words, pref): count = 0 for word in words: if word.startswith(pref): count += 1 return count 7. Flood Fill Description: An image is represented by an $m \times n$ integer grid $image$ where $image[i][j]$ represents the pixel value. Given a starting pixel $(sr, sc)$ and a $newColor$, perform a flood fill. A flood fill starts from the given pixel and changes all connected pixels of the same color to $newColor$. Connected pixels are those sharing a side (up, down, left, right). Approach: This is a classic graph traversal problem, solvable with Breadth-First Search (BFS) or Depth-First Search (DFS). Start at $(sr, sc)$, get its original color, and then recursively/iteratively explore its neighbors. Only change pixels with the original color and within bounds. def floodFill(image, sr, sc, newColor): rows, cols = len(image), len(image[0]) original_color = image[sr][sc] if original_color == newColor: return image def dfs(r, c): if r = rows or c = cols or image[r][c] != original_color: return image[r][c] = newColor dfs(r + 1, c) dfs(r - 1, c) dfs(r, c + 1) dfs(r, c - 1) dfs(sr, sc) return image 8. Find the Town Judge Description: In a town of $N$ people, labeled $1$ to $N$. There is a town judge if: 1) The town judge trusts nobody. 2) Everybody (except for the town judge himself) trusts the town judge. 3) There is exactly one person that satisfies properties 1 and 2. Given $N$ and an array $trust$ where $trust[i] = [a, b]$ represents that person $a$ trusts person $b$. Return the label of the town judge if the town judge exists and can be identified, otherwise return $-1$. Approach: We can keep track of two counts for each person: how many people they trust (out-degree) and how many people trust them (in-degree). A town judge will have an out-degree of 0 and an in-degree of $N-1$. def findJudge(N, trust): # in_degree[i] = number of people trusting person i # out_degree[i] = number of people person i trusts in_degree = [0] * (N + 1) out_degree = [0] * (N + 1) for a, b in trust: out_degree[a] += 1 in_degree[b] += 1 for i in range(1, N + 1): if out_degree[i] == 0 and in_degree[i] == N - 1: return i return -1 9. Verifying an Alien Dictionary Description: In an alien language, surprisingly, they also use English lowercase letters, but possibly in a different order. The order of the letters is given by a string $order$. Given a sequence of $words$, check if they are sorted lexicographically in this alien language. Approach: Convert the $order$ string into a mapping from character to its rank. Then, compare adjacent words. To compare two words, iterate through them character by character. If characters differ, compare their ranks. If one word is a prefix of another (e.g., "apple", "app"), the longer word must come after the shorter one. def isAlienSorted(words, order): char_map = {char: i for i, char in enumerate(order)} def compare(word1, word2): n1, n2 = len(word1), len(word2) for i in range(min(n1, n2)): char1_rank = char_map[word1[i]] char2_rank = char_map[word2[i]] if char1_rank char2_rank: return False # word1 comes after word2 return n1 10. Island Perimeter Description: You are given a $row \times col$ grid representing a map where $grid[i][j] = 1$ represents land and $grid[i][j] = 0$ represents water. Grid cells are connected horizontally/vertically. There is exactly one island, and it has no lakes. Calculate the perimeter of the island. Approach: Iterate through each cell of the grid. If a cell is land ($1$), it contributes 4 to the perimeter initially. Then, for each land cell, subtract 1 for every adjacent land cell (up, down, left, right), as that side is shared and not part of the perimeter. Be careful not to double count shared sides. def islandPerimeter(grid): rows, cols = len(grid), len(grid[0]) perimeter = 0 for r in range(rows): for c in range(cols): if grid[r][c] == 1: perimeter += 4 # Each land cell initially contributes 4 sides # Check neighbors and subtract 1 for each shared land side if r > 0 and grid[r-1][c] == 1: # Up perimeter -= 2 # Subtract 2 because both current and neighbor cell # will count this shared edge if c > 0 and grid[r][c-1] == 1: # Left perimeter -= 2 return perimeter # A simpler way to think about it: # For each land cell, add 1 for each adjacent water cell or boundary. def islandPerimeter_v2(grid): rows, cols = len(grid), len(grid[0]) perimeter = 0 for r in range(rows): for c in range(cols): if grid[r][c] == 1: # Check top if r == 0 or grid[r-1][c] == 0: perimeter += 1 # Check bottom if r == rows - 1 or grid[r+1][c] == 0: perimeter += 1 # Check left if c == 0 or grid[r][c-1] == 0: perimeter += 1 # Check right if c == cols - 1 or grid[r][c+1] == 0: perimeter += 1 return perimeter 11. N-th Tribonacci Number Description: The Tribonacci sequence $T_n$ is defined as: $T_0 = 0, T_1 = 1, T_2 = 1$, and $T_{n+3} = T_n + T_{n+1} + T_{n+2}$ for $n \ge 0$. Given $n$, return the value of $T_n$. Approach: This is a dynamic programming problem. Store previously calculated Tribonacci numbers to avoid redundant computations. Iteratively calculate values from $T_0$ up to $T_n$. def tribonacci(n): if n == 0: return 0 if n == 1 or n == 2: return 1 dp = [0] * (n + 1) dp[0] = 0 dp[1] = 1 dp[2] = 1 for i in range(3, n + 1): dp[i] = dp[i-1] + dp[i-2] + dp[i-3] return dp[n] # Optimized space solution def tribonacci_optimized(n): if n == 0: return 0 if n == 1 or n == 2: return 1 a, b, c = 0, 1, 1 # T_0, T_1, T_2 for _ in range(3, n + 1): next_t = a + b + c a = b b = c c = next_t return c 12. Check If One String Swap Can Make Strings Equal Description: Given two strings $s1$ and $s2$ of equal length. You can choose to swap at most one pair of characters in $s1$. Return $true$ if you can make $s1$ and $s2$ equal, otherwise return $false$. Approach: Compare $s1$ and $s2$ character by character. Collect all indices where characters differ. - If there are 0 differences, they are already equal ($true$). - If there are 2 differences, check if swapping the characters at these two differing positions in $s1$ makes them equal to $s2$. - If there are any other number of differences (1, or $>2$), it's impossible to make them equal with at most one swap ($false$). def areAlmostEqual(s1, s2): diff_indices = [] for i in range(len(s1)): if s1[i] != s2[i]: diff_indices.append(i) if not diff_indices: # 0 differences return True if len(diff_indices) == 2: # 2 differences idx1, idx2 = diff_indices[0], diff_indices[1] # Check if swapping s1[idx1] and s1[idx2] makes them match s2 return s1[idx1] == s2[idx2] and s1[idx2] == s2[idx1] return False # 1 or >2 differences 13. Maximum Nesting Depth of the Parentheses Description: A string is a Valid Parentheses String (VPS) if it is empty, or $(A)$ where $A$ is a VPS, or $A+B$ where $A$ and $B$ are VPSs. The nesting depth of a VPS is defined. Given a VPS $s$, return its maximum nesting depth. Approach: Iterate through the string. Maintain a counter for the current depth. Increment for '(' and decrement for ')'. Keep track of the maximum value the counter reaches. def maxDepth(s): max_depth = 0 current_depth = 0 for char in s: if char == '(': current_depth += 1 max_depth = max(max_depth, current_depth) elif char == ')': current_depth -= 1 return max_depth 14. Maximum Odd Binary Number Description: Given a binary string $s$, rearrange its digits to form the largest possible odd binary number that can be created from this combination. Return the string representing the maximum odd binary number. Approach: To make a binary number odd, its last digit must be '1'. To make it the largest, the leading digits should be as many '1's as possible, followed by '0's. Count the number of '1's and '0's. Place one '1' at the end. Place all remaining '1's at the beginning, followed by all '0's. def maximumOddBinaryNumber(s): count_ones = s.count('1') count_zeros = s.count('0') if count_ones == 0: return "0" * count_zeros # No '1's, cannot form odd number, but problem implies '1's exist # Place (count_ones - 1) ones, then all zeros, then one '1' at the end result = '1' * (count_ones - 1) + '0' * count_zeros + '1' return result 15. Minimum Number of Moves to Seat Everyone Description: Given two arrays $seats$ and $students$ of the same length, where $seats[i]$ is the position of the $i$-th seat and $students[j]$ is the position of the $j$-th student. You want to move each student to a seat such that the total number of moves is minimized. Each student must be moved to a unique seat. Return the minimum total number of moves. Approach: To minimize the total moves, sort both arrays. Then, pair the $i$-th smallest seat with the $i$-th smallest student. The total moves will be the sum of absolute differences of these pairs. def minMovesToSeat(seats, students): seats.sort() students.sort() total_moves = 0 for i in range(len(seats)): total_moves += abs(seats[i] - students[i]) return total_moves 16. Lemonade Change Description: At a lemonade stand, each lemonade costs $5. Customers pay with $5, $10, or $20 bills. You must provide correct change. You start with no money. Return $true$ if you can provide change for every customer, or $false$ otherwise. Approach: Greedily manage the count of $5 and $10 bills you have. When a customer pays: - $5: Increment count of $5 bills. - $10: Decrement count of $5 bills (must have at least one), then increment count of $10 bills. If no $5 bill, return $false$. - $20: Try to give change using one $10 and one $5. If not possible, try using three $5 bills. If neither is possible, return $false$. Decrement counts accordingly. def lemonadeChange(bills): fives = 0 tens = 0 for bill in bills: if bill == 5: fives += 1 elif bill == 10: if fives == 0: return False fives -= 1 tens += 1 elif bill == 20: if tens >= 1 and fives >= 1: # Prefer to use $10 and $5 for change tens -= 1 fives -= 1 elif fives >= 3: # Otherwise, use three $5s fives -= 3 else: # Not enough change return False return True 17. Buy Two Chocolates Description: You are given an integer array $prices$ representing the prices of chocolates, and an integer $money$. You want to buy exactly two chocolates. Return the amount of money you will have left after buying the two cheapest chocolates. If you cannot afford two chocolates, return $money$. Approach: Find the two cheapest chocolates. This can be done by sorting the prices array or by iterating through it twice (or once, keeping track of the two smallest values found so far). def buyChocolates(prices, money): # Find the two smallest prices min1 = float('inf') min2 = float('inf') for price in prices: if price = cost: return money - cost else: return money 18. Make Two Arrays Equal by Reversing Subarrays Description: Given two integer arrays $target$ and $arr$ of the same length. You can perform the operation of reversing any non-empty sub-array of $arr$ any number of times. Return $true$ if you can make $arr$ equal to $target$, or $false$ otherwise. Approach: If you can reverse any subarray any number of times, it means you can effectively reorder the elements of $arr$ in any way. Therefore, the problem reduces to checking if $arr$ and $target$ contain the same elements with the same frequencies. Sorting both arrays and comparing them, or using hash maps to count frequencies, will work. def canBeEqual(target, arr): # Option 1: Sort and compare target.sort() arr.sort() return target == arr # Option 2: Using frequency counts (hash maps) # from collections import Counter # return Counter(target) == Counter(arr) 19. Largest Local Values in a Matrix Description: Given an $n \times n$ integer matrix $grid$. Generate a new matrix $maxLocal$ of size $(n-2) \times (n-2)$ where $maxLocal[i][j]$ is the largest value in the $3 \times 3$ submatrix centered at $(i+1, j+1)$ in the original matrix. Approach: Iterate through the indices $(i, j)$ for the $maxLocal$ matrix. For each $(i, j)$, find the maximum value in the $3 \times 3$ submatrix in $grid$ starting at $(i, j)$ and ending at $(i+2, j+2)$. def largestLocal(grid): n = len(grid) max_local_n = n - 2 maxLocal = [[0] * max_local_n for _ in range(max_local_n)] for r in range(max_local_n): for c in range(max_local_n): # Find max in the 3x3 submatrix starting at (r, c) in original grid current_max = 0 for i in range(r, r + 3): for j in range(c, c + 3): current_max = max(current_max, grid[i][j]) maxLocal[r][c] = current_max return maxLocal 20. Water Bottles Description: Given $numBottles$ (number of full water bottles you have) and $numExchange$ (number of empty bottles required to exchange for a full one). You can drink all full bottles, and then exchange empty ones. Return the maximum number of water bottles you can drink. Approach: Simulate the process. Start with $numBottles$ full bottles. Drink them all. Calculate how many new bottles you can get from the empty ones, and how many empty bottles are left over. Repeat until no more exchanges can be made. def numWaterBottles(numBottles, numExchange): total_drunk = 0 empty_bottles = 0 while numBottles > 0: total_drunk += numBottles empty_bottles += numBottles numBottles = empty_bottles // numExchange empty_bottles %= numExchange return total_drunk 21. Count of Matches in Tournament Description: You are given an integer $n$, the number of teams in a tournament that has a strange format: - If current teams is even, each team is paired with another team. $n/2$ matches are played, $n/2$ teams advance. - If current teams is odd, one team randomly advances, and the rest are paired. $(n-1)/2$ matches are played, $(n-1)/2 + 1$ teams advance. Return the total number of matches played until a winner is decided. Approach: Notice that in any match, exactly one team is eliminated. To get one winner from $n$ teams, exactly $n-1$ teams must be eliminated. Each match eliminates one team. Therefore, $n-1$ matches must be played. This is a common pattern for single-elimination tournaments. def numberOfMatches(n): # Each match eliminates one team. To have one winner from N teams, # N-1 teams must be eliminated. So, N-1 matches are played. return n - 1 # If you want to simulate: def numberOfMatches_simulate(n): total_matches = 0 while n > 1: if n % 2 == 0: matches_this_round = n // 2 teams_advance = n // 2 else: matches_this_round = (n - 1) // 2 teams_advance = (n - 1) // 2 + 1 total_matches += matches_this_round n = teams_advance return total_matches 22. Image Smoother Description: Given an $m \times n$ integer matrix $img$ representing a grayscale image. You need to return an image smoother, where each cell in the new image is the average of all the cells in the $3 \times 3$ surrounding submatrix (including itself). If a cell is at the border, its neighbors outside the image are not considered. Approach: Create a new matrix of the same dimensions. For each cell $(r, c)$ in the original image, iterate through its $3 \times 3$ neighborhood (from $(r-1, c-1)$ to $(r+1, c+1)$). Sum up the valid neighbor values and count them. Then calculate the average (integer division). def imageSmoother(img): rows, cols = len(img), len(img[0]) result = [[0] * cols for _ in range(rows)] for r in range(rows): for c in range(cols): total_sum = 0 count = 0 # Iterate through the 3x3 neighborhood for dr in [-1, 0, 1]: for dc in [-1, 0, 1]: nr, nc = r + dr, c + dc if 0 23. Transpose Matrix Description: Given a 2D integer array $matrix$, return the transpose of $matrix$. The transpose of a matrix is the matrix flipped over its main diagonal, switching the row and column indices of the matrix. Approach: If the original matrix is $m \times n$, its transpose will be $n \times m$. Create a new matrix of the transposed dimensions. Then, for each element $matrix[i][j]$, assign it to $transpose[j][i]$. def transpose(matrix): rows, cols = len(matrix), len(matrix[0]) transposed_matrix = [[0] * rows for _ in range(cols)] for r in range(rows): for c in range(cols): transposed_matrix[c][r] = matrix[r][c] return transposed_matrix 24. Largest Odd Number in String Description: Given a string $num$ representing a large integer, return the largest-valued odd integer (as a string) that is a non-empty substring of $num$. If no odd integer can be formed, return an empty string. Approach: An integer is odd if its last digit is odd. To find the largest-valued odd integer as a substring, we want the longest possible substring that ends with an odd digit. Iterate from the rightmost digit towards the left. The first odd digit encountered means that the substring from the beginning of $num$ up to this digit is the largest odd number possible. def largestOddNumber(num): for i in range(len(num) - 1, -1, -1): # Iterate from right to left digit = int(num[i]) if digit % 2 != 0: # If the digit is odd return num[:i+1] # Return the substring from start to this digit return "" # No odd digit found 25. Calculate Money in Leetcode Bank Description: Hercy wants to save money for his first car. He puts $1 on Monday, $2 on Tuesday, $3 on Wednesday, $4 on Thursday, $5 on Friday, $6 on Saturday, and $7 on Sunday. On the second week, he puts $2 on Monday, $3 on Tuesday, and so on. Given $n$ (number of days), return the total money he will have in the bank. Approach: Simulate the process week by week. Keep track of the current day's deposit amount, which increases by 1 each day and resets to $1 + (week\_num - 1)$ on Monday of the new week. def totalMoney(n): total_money = 0 current_week_start_deposit = 1 # Amount deposited on Monday of current week day_in_week = 0 # 0 for Monday, 1 for Tuesday, ... for _ in range(n): total_money += current_week_start_deposit + day_in_week day_in_week += 1 if day_in_week == 7: # End of the week day_in_week = 0 current_week_start_deposit += 1 return total_money # More mathematical approach: def totalMoney_math(n): weeks = n // 7 remaining_days = n % 7 # Calculate sum for full weeks # Week 1: 1+2+3+4+5+6+7 = 28 # Week 2: 2+3+4+5+6+7+8 = 35 # Week k: (k) + (k+1) + ... + (k+6) = 7k + 21 # Sum of first 'weeks' full weeks: # Sum[(7k + 21) for k from 1 to weeks] = 7 * Sum[k] + 21 * Sum[1] # = 7 * (weeks * (weeks + 1) / 2) + 21 * weeks total = 0 # Sum for full weeks total += 7 * (weeks * (weeks + 1) // 2) + 21 * weeks # Sum for remaining days # On the (weeks + 1)-th week, Monday deposit starts at (weeks + 1) for i in range(remaining_days): total += (weeks + 1) + i return total 26. Matrix Diagonal Sum Description: Given a square matrix $mat$, return the sum of the matrix diagonals. Only include the sum of all the elements on the primary diagonal and all the elements on the secondary diagonal that are not part of the primary diagonal. Approach: Iterate through the matrix. For an element $mat[i][j]$: - It's on the primary diagonal if $i == j$. - It's on the secondary diagonal if $i + j == n - 1$ (where $n$ is the matrix size). Sum these elements. If $n$ is odd, the center element ($mat[n/2][n/2]$) will be counted twice (once for primary, once for secondary). Subtract it once in this case. def diagonalSum(mat): n = len(mat) total_sum = 0 for i in range(n): # Primary diagonal total_sum += mat[i][i] # Secondary diagonal # Make sure it's not the same element as primary diagonal for odd n if i != n - 1 - i: total_sum += mat[i][n - 1 - i] return total_sum 27. Count Odd Numbers in an Interval Range Description: Given two non-negative integers, $low$ and $high$. Return the count of odd numbers between $low$ and $high$ (inclusive). Approach: - If $low$ is odd, then $low, low+2, \dots$ are odd. - If $low$ is even, then $low+1, low+3, \dots$ are odd. The number of odd numbers in a range $[L, R]$ is $(R - L + 1) / 2$ if $L$ and $R$ have different parities. If both are odd, it's $(R - L) / 2 + 1$. If both are even, it's $(R - L) / 2$. A simpler way is to count all numbers ($high - low + 1$). Approximately half are odd. If either $low$ or $high$ is odd, increment the count for exactness if needed. Another simple formula: $(high + 1) // 2 - low // 2$. This formula correctly counts odd numbers. For example, $[3, 7]$: $(7+1)//2 - 3//2 = 8//2 - 1 = 4 - 1 = 3$. (3, 5, 7 are 3 odds) For example, $[2, 8]$: $(8+1)//2 - 2//2 = 9//2 - 1 = 4 - 1 = 3$. (3, 5, 7 are 3 odds) def countOdds(low, high): # If low is odd, we start counting from low. # If low is even, we start counting from low+1. # The count will be (high - (low if low is odd else low+1)) / 2 + 1 # A more robust and cleaner formula: # (high + 1) // 2 gives count of odd numbers from 1 to high (inclusive) # low // 2 gives count of odd numbers from 1 to low-1 (inclusive) # Subtracting them gives count of odd numbers from low to high return (high + 1) // 2 - low // 2 28. Greatest Common Divisor of Strings Description: For two strings $s$ and $t$, we say "$t$ divides $s$" if $s$ can be formed by concatenating $t$ with itself one or more times. Given two strings $str1$ and $str2$, return the largest string $x$ such that $x$ divides both $str1$ and $str2$. Approach: If $x$ divides both $str1$ and $str2$, then $str1 + str2$ must be equal to $str2 + str1$. If they are not equal, no such $x$ exists. If they are equal, the length of $x$ must be the greatest common divisor (GCD) of $len(str1)$ and $len(str2)$. The string $x$ itself would then be the prefix of $str1$ (or $str2$) with that GCD length. import math def gcdOfStrings(str1, str2): # Check if a common divisor string exists if str1 + str2 != str2 + str1: return "" # The length of the GCD string must be gcd(len(str1), len(str2)) gcd_len = math.gcd(len(str1), len(str2)) # The GCD string is the prefix of str1 (or str2) of that length return str1[:gcd_len] 29. Excel Sheet Column Title Description: Given an integer $columnNumber$, return its corresponding column title as it appears in an Excel sheet. (e.g., 1 -> 'A', 2 -> 'B', ..., 26 -> 'Z', 27 -> 'AA', 28 -> 'AB'). Approach: This is a base-26 conversion problem, but with a twist: 'A' is 1, not 0. This means it's a 1-indexed system. The standard base conversion algorithm for a 0-indexed system (like decimal to binary) would be to take $n \pmod{base}$ and $n = n // base$. For a 1-indexed system, the trick is to first decrement $columnNumber$ by 1. Then, repeat: 1. Get the remainder $r = (columnNumber - 1) \pmod{26}$. 2. Convert $r$ to a character ('A' + $r$). 3. Update $columnNumber = (columnNumber - 1) // 26$. Prepend the characters to build the result string. def convertToTitle(columnNumber): result = [] while columnNumber > 0: columnNumber -= 1 # Adjust for 1-indexed system (A=1, not A=0) remainder = columnNumber % 26 result.append(chr(ord('A') + remainder)) columnNumber //= 26 return "".join(result[::-1]) # Reverse to get the correct order 30. Widest Vertical Area Between Two Points Containing No Points Description: Given $n$ points on a 2D plane, find the widest vertical area between two points such that no points are inside the area. A vertical area is defined by two vertical lines, $x=a$ and $x=b$ with $a Approach: The vertical area is defined by x-coordinates. The y-coordinates do not matter. To maximize the width, we need to find the maximum difference between consecutive sorted x-coordinates. So, extract all x-coordinates, sort them, and find the maximum difference between adjacent elements. def maxWidthOfVerticalArea(points): x_coordinates = sorted([p[0] for p in points]) max_width = 0 for i in range(1, len(x_coordinates)): max_width = max(max_width, x_coordinates[i] - x_coordinates[i-1]) return max_width 31. Roman to Integer Description: Given a Roman numeral string $s$, convert it to an integer. Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is IV, five is V, etc. (subtractive rule for 4, 9, 40, 90, 400, 900). Approach: Create a mapping for Roman characters to integer values. Iterate through the string from left to right. If a character's value is less than the next character's value (e.g., 'I' before 'V'), subtract its value. Otherwise, add its value. def romanToInt(s): roman_map = { 'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000 } total = 0 n = len(s) for i in range(n): current_val = roman_map[s[i]] # Check for subtractive cases if i + 1 32. Shift 2D Grid Description: Given an $m \times n$ 2D grid of integers and an integer $k$. You need to shift the grid $k$ times. In one shift operation: 1. $grid[i][j]$ moves to $grid[i][j+1]$. 2. $grid[i][n-1]$ moves to $grid[i+1][0]$. 3. $grid[m-1][n-1]$ moves to $grid[0][0]$. Return the 2D grid after shifting it $k$ times. Approach: The shifts effectively treat the 2D grid as a 1D array. Convert the 2D grid into a 1D list, perform the conceptual shift on the 1D list by $k$ positions (using modulo operator to handle $k$ larger than the total number of elements), and then convert it back to a 2D grid. def shiftGrid(grid, k): rows, cols = len(grid), len(grid[0]) total_elements = rows * cols # Flatten the grid into a 1D list flat_grid = [] for r in range(rows): for c in range(cols): flat_grid.append(grid[r][c]) # Calculate effective shift k %= total_elements # Perform the shift on the 1D list # The new_flat_grid[i] will be the element from flat_grid[(i - k + total_elements) % total_elements] # Or, more simply, slice and concatenate: shifted_flat_grid = flat_grid[-k:] + flat_grid[:-k] # Convert back to 2D grid shifted_grid = [[0] * cols for _ in range(rows)] for i in range(total_elements): r = i // cols c = i % cols shifted_grid[r][c] = shifted_flat_grid[i] return shifted_grid 33. Convert 1D Array Into 2D Array Description: You are given a 0-indexed 1D integer array $original$, and two integers $m$ and $n$. You want to construct a 2D array with $m$ rows and $n$ columns using all elements from $original$. Return the 2D array. If it's impossible, return an empty 2D array. Approach: Check if the length of $original$ is equal to $m \times n$. If not, it's impossible. Otherwise, iterate through the $original$ array and fill the 2D array row by row, column by column. def construct2DArray(original, m, n): if len(original) != m * n: return [] # Impossible to form the 2D array result_2d = [[0] * n for _ in range(m)] for i in range(len(original)): r = i // n # Determine row index c = i % n # Determine column index result_2d[r][c] = original[i] return result_2d 34. Ugly Number Description: An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5. Given an integer $n$, return $true$ if $n$ is an ugly number, otherwise return $false$. Approach: Repeatedly divide $n$ by 2, 3, and 5 as long as it's divisible. If, after all these divisions, $n$ becomes 1, then it's an ugly number. Handle edge cases like $n \le 0$. def isUgly(n): if n 35. Plus One Description: Given a large integer represented as an integer array $digits$, where each $digits[i]$ is the $i$-th digit of the integer. The digits are ordered from most significant to least significant. Increment the large integer by one and return the resulting array of digits. Approach: Iterate from the rightmost digit. Add 1 to the last digit. If there's a carry, propagate it to the left. If a carry remains after processing the leftmost digit, prepend a '1' to the array. def plusOne(digits): n = len(digits) for i in range(n - 1, -1, -1): # Iterate from right to left if digits[i] 36. Lucky Numbers in a Matrix Description: Given an $m \times n$ matrix of distinct numbers, return all lucky numbers in the matrix. A lucky number is an element that is the minimum element in its row and the maximum element in its column. Approach: 1. Find the minimum element in each row and store these minimums along with their column indices. 2. For each of these row minimums, check if it's also the maximum in its respective column. A more efficient way: 1. Precompute all row minimums. 2. Precompute all column maximums. 3. Iterate through the matrix. If $matrix[r][c]$ is equal to $min\_row[r]$ AND $max\_col[c]$, it's a lucky number. def luckyNumbers(matrix): rows, cols = len(matrix), len(matrix[0]) row_mins = [float('inf')] * rows col_maxs = [float('-inf')] * cols # Calculate row minimums for r in range(rows): for c in range(cols): row_mins[r] = min(row_mins[r], matrix[r][c]) # Calculate column maximums for c in range(cols): for r in range(rows): col_maxs[c] = max(col_maxs[c], matrix[r][c]) lucky_nums = [] for r in range(rows): for c in range(cols): if matrix[r][c] == row_mins[r] and matrix[r][c] == col_maxs[c]: lucky_nums.append(matrix[r][c]) return lucky_nums 37. Power of Four Description: Given an integer $n$, return $true$ if it is a power of four. Otherwise, return $false$. An integer $n$ is a power of four, if there exists an integer $x$ such that $n = 4^x$. Approach: 1. Handle $n \le 0$ (not powers of four). 2. Repeatedly divide $n$ by 4 as long as it's divisible. If $n$ becomes 1, it's a power of four. 3. Bit manipulation approach: A power of four is also a power of two, so $n > 0$ and $(n \text{ & } (n-1)) == 0$. Additionally, the set bit must be in an even position (0-indexed from right). This means $n$ must have a 1 only in positions $0, 2, 4, \dots$. This can be checked by $(n \text{ & } 0x55555555) \ne 0$, where $0x55555555$ is a bitmask with 1s at all even positions. def isPowerOfFour(n): if n 0 and (n & (n-1)) == 0) # 2. The single set bit is at an even position (0-indexed from right) # This can be checked by n & 0xAAAAAAAA (all odd bits are 1) == 0, OR # n & 0x55555555 (all even bits are 1) != 0 def isPowerOfFour_bit(n): # Check if n is positive and a power of 2 if n 38. Power of Two Description: Given an integer $n$, return $true$ if it is a power of two. Otherwise, return $false$. An integer $n$ is a power of two, if there exists an integer $x$ such that $n = 2^x$. Approach: 1. Handle $n \le 0$ (not powers of two). 2. Repeatedly divide $n$ by 2 as long as it's divisible. If $n$ becomes 1, it's a power of two. 3. Bit manipulation approach: A positive integer $n$ is a power of two if and only if it has exactly one bit set in its binary representation. This can be checked efficiently using the property: $n > 0$ and $(n \text{ & } (n-1)) == 0$. def isPowerOfTwo(n): if n 0 and (n & (n - 1)) == 0 39. Find the Difference Description: You are given two strings $s$ and $t$. String $t$ is generated by randomly shuffling string $s$ and then adding one more letter at a random position. Return the letter that was added to $t$. Approach: 1. Using character counts: Count character frequencies in $s$ and $t$. The character with a higher frequency in $t$ (or a frequency of 1 in $t$ if not present in $s$) is the added one. 2. Using XOR: XOR all characters in $s$ and all characters in $t$. Since all characters in $s$ appear once in $t$ and are XORed twice, they cancel out. The remaining XOR sum will be the ASCII value of the added character. 3. Sum of ASCII values: Sum ASCII values of characters in $s$ and $t$. The difference will be the ASCII value of the added character. def findTheDifference(s, t): # Approach 1: Using character counts # from collections import Counter # s_counts = Counter(s) # t_counts = Counter(t) # for char, count in t_counts.items(): # if char not in s_counts or s_counts[char] 40. Add to Array-Form of Integer Description: The array-form of an integer $num$ is an array representing its digits. Given the array-form $num$ of a non-negative integer, and an integer $k$, return the array-form of the integer $num + k$. Approach: Convert $num$ (array-form) to an integer, add $k$, then convert the result back to an array-form. Be cautious of potential large numbers, Python handles large integers automatically. For languages like C++/Java, a manual digit-by-digit addition similar to "Plus One" (problem 35) is needed, starting from the rightmost digit of $num$ and $k$. def addToArrayForm(num, k): # Pythonic approach: Convert to int, add, convert back num_int = 0 for digit in num: num_int = num_int * 10 + digit sum_val = num_int + k # Convert sum_val back to array-form if sum_val == 0: # Edge case for sum being 0 return [0] result = [] while sum_val > 0: result.append(sum_val % 10) sum_val //= 10 return result[::-1] # Reverse to get correct order # Manual digit-by-digit addition (more generalizable to other languages) def addToArrayForm_manual(num, k): result = [] i = len(num) - 1 carry = 0 while i >= 0 or k > 0 or carry > 0: digit_num = num[i] if i >= 0 else 0 digit_k = k % 10 current_sum = digit_num + digit_k + carry result.append(current_sum % 10) carry = current_sum // 10 i -= 1 k //= 10 return result[::-1] 41. Shuffle the Array Description: Given the array $nums$ consisting of $2n$ elements in the form $[x_1, x_2, \dots, x_n, y_1, y_2, \dots, y_n]$. Return the array in the form $[x_1, y_1, x_2, y_2, \dots, x_n, y_n]$. Approach: Iterate from $i=0$ to $n-1$. For each $i$, append $nums[i]$ (which is $x_{i+1}$) and then $nums[i+n]$ (which is $y_{i+1}$) to a new result array. def shuffle(nums, n): result = [] for i in range(n): result.append(nums[i]) # x_i result.append(nums[i + n]) # y_i return result 42. Missing Number Description: Given an array $nums$ containing $n$ distinct numbers in the range $[0, n]$, return the only number in the range that is missing from the array. Approach: 1. Summation: Calculate the sum of numbers from $0$ to $n$ using the formula $n(n+1)/2$. Calculate the sum of elements in $nums$. The difference is the missing number. 2. XOR: XOR all numbers from $0$ to $n$. XOR all numbers in $nums$. The result of XORing these two sums is the missing number. This works because $a \oplus a = 0$ and $a \oplus 0 = a$. 3. Sorting: Sort the array and iterate, checking if $nums[i] == i$. The first mismatch or the number $n$ if all match reveals the missing number. def missingNumber(nums): n = len(nums) # Approach 1: Summation expected_sum = n * (n + 1) // 2 actual_sum = sum(nums) return expected_sum - actual_sum # Approach 2: XOR # missing = n # for i in range(n): # missing ^= i # missing ^= nums[i] # return missing 43. Minimum Bit Flips to Convert Number Description: Given two integers $start$ and $goal$, return the minimum number of bit flips to convert $start$ to $goal$. A bit flip changes a 0 to 1, or a 1 to 0. Approach: The number of bit flips needed is simply the number of differing bits between $start$ and $goal$. This can be found by calculating the XOR of $start$ and $goal$ ($start \oplus goal$), and then counting the number of set bits (1s) in the result. This is known as the Hamming distance. def minBitFlips(start, goal): xor_result = start ^ goal # Count set bits (Brian Kernighan's algorithm) count = 0 while xor_result > 0: xor_result &= (xor_result - 1) # Clears the least significant set bit count += 1 return count # Python's built-in bit_count (for Python 3.10+) # return (start ^ goal).bit_count() 44. Add Binary Description: Given two binary strings $a$ and $b$, return their sum as a binary string. Approach: Simulate binary addition. Iterate from the rightmost digits of both strings. Maintain a carry. Add corresponding digits and the carry. The sum's last bit is the result digit, and the carry is passed to the next position. Pad shorter strings with leading zeros if necessary. def addBinary(a, b): result = [] i, j = len(a) - 1, len(b) - 1 carry = 0 while i >= 0 or j >= 0 or carry: digit_a = int(a[i]) if i >= 0 else 0 digit_b = int(b[j]) if j >= 0 else 0 current_sum = digit_a + digit_b + carry result.append(str(current_sum % 2)) carry = current_sum // 2 i -= 1 j -= 1 return "".join(result[::-1]) # Reverse and join to form the string 45. Sleep Description: Given a positive integer $millis$. Write an async function that sleeps for $millis$ milliseconds. It can resolve any value. Approach: JavaScript uses `setTimeout` for asynchronous delays. Wrap it in a `Promise` to make it `await`able. // Javascript solution async function sleep(millis) { return new Promise(resolve => setTimeout(resolve, millis)); } 46. Allow One Function Call Description: Given a function $fn$, return a new function that is identical to the original function but can only be called once. If the function is called more than once, it should return $undefined$. Approach: Use a closure to maintain a state variable (e.g., `hasBeenCalled`) that tracks whether the function has been invoked. Store the result of the first call. Subsequent calls check this flag. // Javascript solution function once(fn) { let hasBeenCalled = false; let result; return function(...args) { if (!hasBeenCalled) { hasBeenCalled = true; result = fn(...args); return result; } else { return undefined; } }; } 47. Function Composition Description: Given an array of functions $functions$, return a new function $fn$ that is the function composition of the array of functions. When called, $fn(x)$ should return $f_n(f_{n-1}(\dots(f_1(x))\dots))$. Approach: The composition means applying functions from right to left. Iterate through the functions in reverse order, applying each function to the accumulated result. // Javascript solution function compose(functions) { return function(x) { if (functions.length === 0) { return x; } let result = x; for (let i = functions.length - 1; i >= 0; i--) { result = functions[i](result); } return result; }; } 48. Array Reduce Transformation Description: Given an integer array $nums$, a reducer function $fn$, and an initial value $init$. Return the final result of the reduction. The reducer function $fn(accum, curr)$ is applied to each element. $accum$ is the accumulated value, $curr$ is the current element. Approach: Initialize an accumulator with $init$. Iterate through the array, updating the accumulator with the result of $fn(accumulator, current\_element)$ for each element. // Javascript solution function reduce(nums, fn, init) { let accum = init; for (let i = 0; i 49. Filter Elements from Array Description: Given an integer array $arr$ and a filtering function $fn$. Return a new array with only the elements for which $fn(arr[i], i)$ returns a truthy value. $i$ is the index of the element. Approach: Initialize an empty result array. Iterate through the input array. For each element, call the filtering function. If it returns a truthy value, add the element to the result array. // Javascript solution function filter(arr, fn) { const result = []; for (let i = 0; i 50. Apply Transform Over Each Element in Array Description: Given an integer array $arr$ and a mapping function $fn$. Return a new array with each element transformed by $fn(arr[i], i)$. $i$ is the index of the element. Approach: Initialize a new array. Iterate through the input array. For each element, apply the mapping function and store the result in the new array at the corresponding index. // Javascript solution function map(arr, fn) { const transformedArr = new Array(arr.length); for (let i = 0; i 51. Counter II Description: Write a function $createCounter$. It accepts an initial integer $init$. It should return an object with three functions: - $increment()$ increases the current value by 1. - $decrement()$ decreases the current value by 1. - $reset()$ resets the current value to $init$. Approach: Use a closure to store the current value and the initial value. Each returned function will operate on this closed-over `count` variable. // Javascript solution function createCounter(init) { let count = init; return { increment: function() { count++; return count; }, decrement: function() { count--; return count; }, reset: function() { count = init; return count; } }; } 52. Counter Description: Given an integer $n$, return a counter function. This counter function initially returns $n$, then returns $n + 1$, then $n + 2$, and so on. Approach: Use a closure to store the current value of the counter. Each time the returned function is called, increment the closed-over variable and return its previous value. // Javascript solution function createCounter(n) { let count = n; return function() { return count++; }; } 53. Create Hello World Function Description: Write a function $createHelloWorld$. It should return a new function that always returns "Hello World". Approach: Define an outer function that returns an inner function. The inner function simply returns the desired string. // Javascript solution function createHelloWorld() { return function(...args) { return "Hello World"; }; } 54. Generate Fibonacci Sequence Description: Write a generator function that returns a sequence of Fibonacci numbers. The first two Fibonacci numbers are $0$ and $1$. Approach: In a generator function, `yield` is used to produce values. Keep track of the last two Fibonacci numbers and yield the next one in each iteration. // Javascript solution function* fibGenerator() { let a = 0; let b = 1; while (true) { yield a; [a, b] = [b, a + b]; // Update a and b for the next iteration } } 55. Array Wrapper Description: Create a class $ArrayWrapper$ that accepts an array of integers $nums$. It should have two methods: - $valueOf()$ returns the sum of all elements in $nums$. - $toString()$ returns a string representation of the array in the format "$[el1,el2,\dots]$". Approach: Define a class with a constructor that stores the input array. Implement the `valueOf` and `toString` methods as specified. `valueOf` is implicitly called when an object is used in a numeric context, and `toString` when used in a string context. // Javascript solution class ArrayWrapper { constructor(nums) { this.nums = nums; } valueOf() { return this.nums.reduce((sum, num) => sum + num, 0); } toString() { return `[${this.nums.join(',')}]`; } } 56. Array Prototype Last Description: Augment the $Array.prototype$ with a method $last()$ that returns the last element of the array. If the array is empty, it should return $-1$. Approach: Modify `Array.prototype` directly. The `this` keyword inside the method will refer to the array instance it's called on. Check `this.length` to determine if the array is empty. // Javascript solution Array.prototype.last = function() { if (this.length === 0) { return -1; } return this[this.length - 1]; }; 57. Chunk Array Description: Given an array $arr$ and a chunk size $size$, return a chunked array. A chunked array contains the original elements in $arr$, but split into subarrays of length $size$. The last subarray may be of length less than $size$ if $arr.length$ is not evenly divisible by $size$. Approach: Iterate through the array. In each step, take a slice of length $size$ from the current position and add it to the result. Increment the current position by $size$. // Javascript solution function chunk(arr, size) { const chunkedArr = []; let index = 0; while (index