Title: LeetCode
Tags: neetcode150 medium array blind75 grind75 grokking easy depth-first-search hash-table string dynamic-programming breadth-first-search hard sorting binary-tree tree two-pointers heap matrix binary-search graph math backtracking greedy linked-list stack union-find bit-manipulation design sliding-window

Q: Contains Duplicate
Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.
A: Solution
Trade-off between better time complexity (hash table) and space complexity (sorting). See editorial.
Data Structure
Hash Table
Complexity
Runtime: \(O(n)\)
Space: \(O(n)\)

Q: Valid Anagram
Given two strings s and t, return true if t is an anagram of s, and false otherwise.
A: Solution
Trade-off between better time complexity (hash table) and space complexity (sorting). See editorial.
Data Structure
Hash Table
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: Two Sum
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
A: Solution
While inserting elements into the hash table, we can also check to see if the current element's complement already exists. See editorial.
Data Structure
Hash Table
Complexity
Runtime: \(O(n)\)
Space: \(O(n)\)

Q: Group Anagrams
Given an array of strings strs, group the anagrams together.
A: Solution
Two strings are anagrams if and only if their sorted strings are equal. See editorial.
Data Structure
Hash Table
Complexity
Runtime: \(O(n⋅k⋅log k)\)
Space: \(O(n⋅k)\)

Q: Top K Frequent Elements
Given an integer array nums and an integer k, return the k most frequent elements.
A: Solution
Build a frequency hash table and then insert the elements into a max-heap of size k. See editorial.
Data Structure
Heap
Complexity
Runtime: \(O(n⋅log k)\)
Space: \(O(n+k)\)

Q: Encode and Decode Strings
Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings. Implement the encode and decode methods.
A: Solution
Use chunked transfer encoding to send data in self-contained chunks, accompanying each chunk with the chunk size. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n)\)
Space: \(O(k)\)

Q: Product of Array Except Self
Given an integer array nums, return a new array answer such that answer[i] is equal to the product of all the elements of nums except nums[i]. Don't use the division operation.
A: Solution
Make a forward pass multiplying all the numbers to the left of the element, and then a backwards pass for the numbers to the right. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: Valid Sudoku
Determine if a 9 x 9 Sudoku board is valid.
A: Solution
Add rows, columns and boxes to `groups` and check that each group doesn't contain duplicates. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n^2)\)
Space: \(O(n^2)\)

Q: Longest Consecutive Sequence
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
A: Solution
Add all the numbers to a set and iterate through, finding starts of consecutive sequences and counting their lengths. See editorial.
Data Structure
Hash Table
Complexity
Runtime: \(O(n)\)
Space: \(O(n)\)

Q: Ransom Note
Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.
A: Solution
Put magazine into a hash table, and subtract characters from ransomNote from the hash table. See editorial.
Data Structure
Hash Table
Complexity
Runtime: \(O(m)\)
Space: \(O(1)\)

Q: Longest Palindrome
Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters.
A: Solution
Take the maximum number of even occurrences of each character and one of the odd occurences. See editorial.
Data Structure
Hash Table
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: Majority Element
Given an array nums of size n, return the majority element.
A: Solution
Use Boyer-Moore Voting Algorithm and keep a count of the current candidate, switching candidates when the count is 0. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: String to Integer (atoi)
Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer.
A: Solution
Iterate over the input string using an index pointer and use the given rules to validate it. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: Find All Duplicates in an Array
Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice, return an array of all the integers that appears twice.
A: Solution
Use Cycle Sort to sort the array in-place and in constant time. Tterate through the sorted array; all incorrectly positioned elements are duplicates. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: Valid Palindrome
Given a string s, return true if it is a palindrome, or false otherwise.
A: Solution
Initialise two pointers at each end of the string and move them towards each other, skipping over non-alphanumeric characters. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: Two Sum II - Input Array Is Sorted
Given an array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number.
A: Solution
Initialise two pointers at each end of the string. If the sum is less than target, increment the left pointer, if the sum is greater than target, decrement the right pointer. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: 3Sum
Given an integer array nums, return all the triplets that sum to 0.
A: Solution
Sort the array, then iterate through each element, using Two Sum to find pairs that sum to the negative of the current element using only elements to its right. Skip duplicates and stop early if the current element is positive. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n^2)\)
Space: \(O(n)\)

Q: Container With Most Water
Given an integer array height of length n, what is the maximum amount of water that can be stored in a container bounded by two heights together with the x-axis?
A: Solution
Since the area formed between the lines will always be limited by the height of the shorter line, we set two pointers at either end and move them towards each other, always moving the shorter line, and keeping tracking of the max area seen so far. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: Trapping Rain Water
Given 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.
A: Solution
The two-pointer approach calculates trapped water by moving pointers from both ends towards the center, updating maximum heights and summing trapped water based on the shorter side's maximum height when a pointer is moved. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: Sort Colors
Given an array nums with n objects colored red (0), white (1), or blue (2), sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.
A: Solution
Maintain two pointers at the boundary of the color segments and use another pointer to iterate through the array. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: Remove Duplicates from Sorted Array
Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.
A: Solution
Iterate through the sorted array, placing each unique element at the position of the running count of unique elements. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: Squares of a Sorted Array
Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.
A: Solution
Maintain two pointers at either end of the array and compare the absolute values of the (negative) numbers on the left with the numbers on the right, appending the larger number to the output array. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: Best Time to Buy and Sell Stock
You are given an array prices where prices[i] is the price of a given stock on the i-th day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction.
A: Solution
In one pass, keep track of the minimum price seen so far and calculate the profit from the current price. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: Longest Substring Without Repeating Characters
Given a string s, find the length of the longest substring without repeating characters.
A: Solution
Maintain a hash table to record the index of each character in the current substring, skipping ahead when we find a repeated character. See editorial.
Data Structure
Hash Table
Complexity
Runtime: \(O(n)\)
Space: \(O(min(m,n))\)

Q: Longest Repeating Character Replacement
You are given a string s and an integer k. You can choose any character of the string and change it to any other English character. You can perform this operation at most k times. Return the length of the longest same-letter substring you can get after performing the above operations.
A: Solution
Use a sliding window to maintain the longest substring where the most frequent character can be replaced up to k times to form a valid window, adjusting the window size dynamically based on validity. Keep track of max_frequency (there's no need to decrease it to keep it up-to-date. See editorial.
Data Structure
Hash Table
Complexity
Runtime: \(O(n)\)
Space: \(O(m)\)

Q: Permutation in String
Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.
A: Solution
Generate a hash table for s1 and maintain a hash table for the sliding window over s2. See editorial.
Data Structure
Hash Table
Complexity
Runtime: \(O(l_1+26⋅(l_2-l_1)) \)
Space: \(O(1)\)

Q: Minimum Window Substring
Given two strings s and t, return the minimum window substring of s such that every character in t is included in the window.
A: Solution
Keep expanding the window. When the window has all the desired characters, contract and save the smallest window till now. Optimise by filtering out all the characters not present in keep track of indexes. See editorial.
Data Structure
Hash Table
Complexity
Runtime: \(O(|S|+|T|)\)
Space: \(O(|S|+|T|)\)

Q: Sliding Window Maximum
You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. Return the max sliding window.
A: Solution
To find the maximum value in each sliding window efficiently, use a monotonic queue (deque) to keep track of useful elements, popping off earlier, smaller elements from the queue since they won't be used. See editorial.
Data Structure
Deque
Complexity
Runtime: \(O(n)\)
Space: \(O(k)\)

Q: Find All Anagrams in a String
Given two strings s and p, return an array of all the start indices of p's anagrams in s.
A: Solution
Use a sliding window with 2 counters, one for the reference string and the other for the sliding window. See editorial.
Data Structure
Hash Table
Complexity
Runtime: \(O(n_s)\)
Space: \(O(1)\)

Q: Maximum Sum of Distinct Subarrays With Length K
You are given an integer array nums and an integer k. Find the maximum subarray sum of all the subarrays of nums.
A: Solution
Use a sliding window with a set to maintain unique elements, adjusting the window size dynamically to find the maximum sum of all distinct subarrays of length kkk. See editorial.
Data Structure
Hash Table
Complexity
Runtime: \(O(n)\)
Space: \(O(k)\)

Q: Minimum Size Subarray Sum
Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target.
A: Solution
Using a sliding window, shrink the window until the condition is met. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: Longest Substring with At Most K Distinct Characters
Given a string s and an integer k, return the length of the longest substring of s that contains at most k distinct characters.
A: Solution
Using a sliding window, shrink the window until the condition is met. See editorial.
Data Structure
Hash Table
Complexity
Runtime: \(O(n)\)
Space: \(O(k)\)

Q: Valid Parentheses
Given a string s containing just the characters (, ), {, }, [ and ], determine if the input string is valid.
A: Solution
Use a stack to process the parentheses, adding opening parentheses to the stack and popping closing parentheses off the stack. See editorial.
Data Structure
Stack
Complexity
Runtime: \(O(n)\)
Space: \(O(n)\)

Q: Min Stack
Implement the MinStack class that supports the push, pop, top and getMin functions.
A: Solution
Since getMin() only retrieves the element, we can use an extra stack to keep track of the minimum. We should only push an item to the min stack if it is a new minimum. See editorial.
Data Structure
Stack
Complexity
Runtime: \(O(1)\)
Space: \(O(n)\)

Q: Evaluate Reverse Polish Notation
Given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation, return an integer that represents the value of the expression.
A: Solution
Evaluate using a stack, pushing operands onto the stack and popping operands off the stack when an operator is encountered. See editorial.
Data Structure
Stack
Complexity
Runtime: \(O(n)\)
Space: \(O(n)\)

Q: Generate Parentheses
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
A: Solution
Use backtracking to recursively build strings of length 2n, using left/right parentheses counts to only generate valid strings. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(4^n/\sqrt(n))\)
Space: \(O(n)\)

Q: Daily Temperatures
Given an array of integers temperatures that represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the i-th day to get a warmer temperature.
A: Solution
Use a monotonic stack to keep track of days colder than today. When a hot day comes, pop all the colder days off the stack and assign their answers. See editorial.
Data Structure
Stack
Complexity
Runtime: \(O(n)\)
Space: \(O(n)\)

Q: Car Fleet
There are n cars at given miles away from the starting mile 0, traveling to reach the mile target. You are given two integer array position and speed that represent the starting mile and speed of a collection of cars. A car cannot pass another car, but it can catch up and then travel next to it at the speed of the slower car. A car fleet is a car or cars driving next to each other. The speed of the car fleet is the minimum speed of any car in the fleet. Return the number of car fleets that will arrive at the destination.
A: Solution
Sort the cars by position and then add the time to target for each car onto a monotonic stack only if it takes longer than the previous car on the stack. The size of the stack is the number of fleets. See editorial.
Data Structure
Stack
Complexity
Runtime: \(O(n)\)
Space: \(O(n)\)

Q: Largest Rectangle in Histogram
Given an array of heights representing the histogram's bar height, where the width of each bar is 1, what is the area of the largest rectangle in the histogram?
A: Solution
Use a monotonic stack (with sentinel value -1) and keep pushing the current bar's index onto the stack until we get a descending number. Every time we pop, we calculate the area of the rectangle using the popped element as the height and the difference between the current index and the index of the new top of the stack as the width. See editorial.
Data Structure
Stack
Complexity
Runtime: \(O(n)\)
Space: \(O(n)\)

Q: Implement Queue using Stacks
Implement the Queue class using only two stacks that supports the push, peek, pop and empty functions.
A: Solution
Push: move elements from s1 to s2, add on top of s1, move elements back from s2 to s1; Pop: pop from s1; Empty: check if s1 and s2 are empty; Peek: peek from s2. See editorial.
Data Structure
Stack
Complexity
Runtime: \(—\)
Space: \(—\)

Q: Basic Calculator
Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.
A: Solution
Use a stack with no string reveral by using the - operator as the magnitude for the right operand so solve the problem of associativity. See editorial.
Data Structure
Stack
Complexity
Runtime: \(O(n)\)
Space: \(O(n)\)

Q: Next Greater Element I
The next greater element of some element x in an array is the first greater element that is to the right of x in the same array. You are given two integer arrays nums1 and nums2, where nums1 is a subset of nums2. For each element in nums1, find the next greater element in nums2.
A: Solution
Use a monotonic stack to efficiently map each element in nums2 to its next greater element and then construct the result for nums1 based on this mapping. See editorial.
Data Structure
Stack
Complexity
Runtime: \(O(n)\)
Space: \(O(n)\)

Q: Binary Search
Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums.
A: Solution
Execute a binary search on the sorted list. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(log n)\)
Space: \(O(1)\)

Q: Search a 2D Matrix
You are given an m x n integer matrix matrix with the following two properties: (a) each row is sorted in non-decreasing order; and (ii) the first integer of each row is greater than the last integer of the previous row. Given an integer target, return true if target is in matrix or false otherwise.
A: Solution
Execute a binary search on the sorted matrix, using divmod to index into the matrix. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(log m⋅n)\)
Space: \(O(1)\)

Q: Koko Eating Bananas
Koko loves to eat bananas. There are n piles of bananas. The guards have gone and will come back in h hours. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour. Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return. Return the minimum integer k such that she can eat all the bananas within h hours.
A: Solution
Execute a binary search to find the index of first occurrence (minimum) of k that is less than or equal to h. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n⋅log m)\)
Space: \(O(1)\)

Q: Find Minimum in Rotated Sorted Array
A sorted integer array is rotated at an unknown pivot index. Given the array nums after the possible rotation, return the minimum element of this array.
A: Solution
Execute a binary search and compare mid with left or right to choose the correct half to focus on. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(log n)\)
Space: \(O(1)\)

Q: Search in Rotated Sorted Array
A sorted integer array is rotated at an unknown pivot index. Given the array nums after the possible rotation and an integer target, return the index of target.
A: Solution
Execute a binary search to locate the target. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(log n)\)
Space: \(O(1)\)

Q: Time Based Key-Value Store
Design 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.
A: Solution
Since all timestamps are strictly increasing, use an array to store timestamp-value pairs and get them using binary search. See editorial.
Data Structure
Array
Complexity
Runtime: \(—\)
Space: \(—\)

Q: Median of Two Sorted Arrays
Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
A: Solution
Find the median by using binary search to efficiently partition the arrays into halves that contain the median. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(log min(m+n))\)
Space: \(O(1)\)

Q: First Bad Version
Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad. You are given an API isBadVersion(version) -> bool which returns whether version is bad. Implement a function to find the first bad version, minimizing the number of calls to the API.
A: Solution
Use binary search to find the index of first occurrence of a key See editorial.
Data Structure
Array
Complexity
Runtime: \(O(log n)\)
Space: \(O(1)\)

Q: Find Smallest Letter Greater Than Target
You are given an array of characters letters that is sorted in non-decreasing order, and a character target. Return the smallest character in letters that is lexicographically greater than target.
A: Solution
Use binary search to find the index of least element greater than key See editorial.
Data Structure
Array
Complexity
Runtime: \(O(log n)\)
Space: \(O(1)\)

Q: Reverse Linked List
Given the head of a singly linked list, reverse the list, and return the reversed list.
A: Solution
Set prev to None curr to head. While traversing the list, change the current node's next pointer to point to its previous element. Watch out for the order if using multiple assignment. See editorial.
Data Structure
Linked List
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: Reverse Linked List II
Given the head of a singly linked list and two integers left and right, reverse the nodes of the list from position left to position right, and return the reversed list.
A: Solution
Using prev and curr, iterate through the left nodes, then reverse the nodes up to right. Be careful when joining the connections. See editorial.
Data Structure
Linked List
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: Merge Two Sorted Lists
You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted list by splicing together the nodes of the first two lists.
A: Solution
Recursively define the merge operation as the smaller of the two lists' heads plus the result of a merge on the rest of the elements. See editorial.
Data Structure
Linked List
Complexity
Runtime: \(O(n+m)\)
Space: \(O(n+m)\)

Q: Reorder List
Reorder a singly linked-list by folding the list back on itself, interleaving the elements.
A: Solution
Find middle node, reverse second part of linked list and merge two lists. See editorial.
Data Structure
Linked List
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: Remove Nth Node From End of List
Given the head of a linked list, remove the n-th node from the end of the list and return its head.
A: Solution
Using two pointers, traverse the list with the first pointer until n is reached, then traverse both pointers together. Remove the node at the second pointer. See editorial.
Data Structure
Linked List
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: Copy List with Random Pointer
A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null. Construct a deep copy of the list and return the head of the copied linked list.
A: Solution
On the first pass, create all the nodes and put them in a hash table. On the second pass, create all the next and random links. See editorial.
Data Structure
Linked List
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: Add Two Numbers
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
A: Solution
Traverse the lists together digit-by-digit summing them and taking into account the carry. See editorial.
Data Structure
Linked List
Complexity
Runtime: \(O(max(m,n))\)
Space: \(O(1)\)

Q: Linked List Cycle
Given head, the head of a linked list, determine if the linked list has a cycle in it.
A: Solution
Use Floyd's Cycle Finding Algorithm to find a cycle. See editorial.
Data Structure
Linked List
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: Find the Duplicate Number
Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive and where there is only one repeated number, return this repeated number.
A: Solution
Use binary search to locate the point where the sum of elements smaller or equal to the element is greater than the element. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: LRU Cache
Implement the LRUCache class that supports the get and put functions.
A: Solution
Back the cache with an ordered dictionary. See editorial.
Data Structure
Hash Table
Complexity
Runtime: \(O(1)\)
Space: \(O(capacity)\)

Q: Merge k Sorted Lists
You are given an array of k linked-lists lists, with each linked-list sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.
A: Solution
Convert merge k lists problem to merge 2 lists (k-1) times. Alternatively, use a priority queue. See editorial.
Data Structure
Linked List
Complexity
Runtime: \(O(k⋅n)\)
Space: \(O(1)\)

Q: Reverse Nodes in k-Group
Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list. If the number of nodes is not a multiple of k then left-out nodes should remain as it is.
A: Solution
Iteratively reverse every k nodes in a linked list, maintaining connections with previous segments, while tracking the head and tail of each reversed group to ensure the result is properly linked. See editorial.
Data Structure
Linked List
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: Middle of the Linked List
Given the head of a singly linked list, return the middle node of the linked list. If there are two middle nodes, return the second middle node.
A: Solution
Traversing the list with a slow pointer and a pointer at double speed. When fast reaches the end of the list, slow must be in the middle. See editorial.
Data Structure
Linked List
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: Palindrome Linked List
Given the head of a singly linked list, return true if it is a palindrome or false otherwise.
A: Solution
Use a slow and a fast pointer, reverse the first half of the list as you traverse it. Then compare the reversed list with the second half of the list. See editorial.
Data Structure
Linked List
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: Invert Binary Tree
Given the root of a binary tree, invert the tree, and return its root.
A: Solution
Recursively swap the left and right subtrees. See editorial.
Data Structure
Binary Tree
Complexity
Runtime: \(O(n)\)
Space: \(O(n)\)

Q: Maximum Depth of Binary Tree
Given the root of a binary tree, return its maximum depth.
A: Solution
Recursively traverse the binary tree and taking the maximum depth of the left and right subtrees. See editorial.
Data Structure
Binary Tree
Complexity
Runtime: \(O(n)\)
Space: \(O(log n)\)

Q: Diameter of Binary Tree
Given the root of a binary tree, return the length of the diameter of the tree. The diameter is the length of the longest path between any two nodes in a tree, which may or may not pass through the root.
A: Solution
The longest path in the tree would consist of a node, its longest left branch, and its longest right branch. See editorial.
Data Structure
Binary Tree
Complexity
Runtime: \(O(n)\)
Space: \(O(n)\)

Q: Balanced Binary Tree
Given a binary tree, determine if it is height-balanced.
A: Solution
Use top-down recursion to ensure that the subtrees are balanced and their height differ by at most 1. See editorial.
Data Structure
Binary Tree
Complexity
Runtime: \(O(n)\)
Space: \(O(n)\)

Q: Same Tree
Given the roots of two binary trees p and q, write a function to check if they are the same or not.
A: Solution
Recursively check that p.val equals q.val and both subtrees are also equal. See editorial.
Data Structure
Binary Tree
Complexity
Runtime: \(O(n)\)
Space: \(O(n)\)

Q: Subtree of Another Tree
Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.
A: Solution
Serialise both trees with a unique marker for null nodes using pre-order (or post-order) traversal, then check if the serialised subtree string is a substring of the main tree's serialized string using a string-matching algorithm. See editorial.
Data Structure
Binary Tree
Complexity
Runtime:
Space:

Q: Lowest Common Ancestor of a Binary Search Tree
Given a binary search tree, find the lowest common ancestor node of two given nodes in the tree.
A: Solution
Recursively traverse the binary tree while the two given nodes lie on the same subtree. See editorial.
Data Structure
Binary Tree
Complexity
Runtime: \(O(n)\)
Space: \(O(n)\)

Q: Binary Tree Level Order Traversal
Given the root of a binary tree, return the level order traversal of its nodes' values, i.e., from left-to-right, level-by-level.
A: Solution
While keeping track of the current level, recursively append nodes to a levels defaultdict. See editorial.
Data Structure
Binary Tree
Complexity
Runtime: \(O(n)\)
Space: \(O(n)\)

Q: Binary Tree Right Side View
Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top-to-bottom.
A: Solution
While keeping track of the current level, recursively assign nodes to a levels hash table. See editorial.
Data Structure
Binary Tree
Complexity
Runtime: \(O(n)\)
Space: \(O(d)\)

Q: Binary Tree Level Order Traversal II
Given the root of a binary tree, return the bottom-up level order traversal of its nodes' values. (i.e., from left-to-right, level-by-level from leaf-to-root).
A: Solution
While keeping track of the current level, recursively append nodes to a levels defaultdict, then reverse the result. See editorial.
Data Structure
Binary Tree
Complexity
Runtime: \(O(n)\)
Space: \(O(n)\)

Q: Binary Tree Zigzag Level Order Traversal
Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left-to-right, then right-to-left for the next level and alternate between).
A: Solution
While keeping track of the current level, recursively prepend/append nodes to a levels defaultdict, depending on whether the level is odd or even. See editorial.
Data Structure
Binary Tree
Complexity
Runtime: \(O(n)\)
Space: \(O(n)\)

Q: Count Good Nodes in Binary Tree
Given a binary tree root, a node X in the tree is good if in the path from the root to X there are no nodes with a value greater than X. Return the number of good nodes in the binary tree.
A: Solution
Recursively traverse the binary tree, keeping track of num_good_nodes and max_so_far. See editorial.
Data Structure
Binary Tree
Complexity
Runtime: \(O(n)\)
Space: \(O(n)\)

Q: Validate Binary Search Tree
Given the root of a binary tree, determine if it is a valid binary search tree.
A: Solution
Recursively traverse the tree keeping the set of valid ranges. See editorial.
Data Structure
Binary Tree
Complexity
Runtime: \(O(n)\)
Space: \(O(n)\)

Q: Kth Smallest Element in a BST
Given the root of a binary search tree and an integer k, return the k-th smallest value of all the values of the nodes in the tree.
A: Solution
Iteratively traverse the binary search tree in-order and decrement k as each element is encountered. See editorial.
Data Structure
Binary Tree
Complexity
Runtime: \(O(H+k)\)
Space: \(O(H)\)

Q: Construct Binary Tree from Preorder and Inorder Traversal
Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.
A: Solution
Recursively build the tree using the preorder value as the root and use it to index into the inorder array to find the size of the subtree. See editorial.
Data Structure
Binary Tree
Complexity
Runtime: \(O(n)\)
Space: \(O(n)\)

Q: Binary Tree Maximum Path Sum
The path sum of a path is the sum of the node's values in the path. Given the root of a binary tree, return the maximum path sum of any non-empty path.
A: Solution
Recursively traverse the tree to calculate the maximum path sum by determining the gain from each subtree (including a node only if it increases the path sum). See editorial.
Data Structure
Binary Tree
Complexity
Runtime: \(O(n)\)
Space: \(O(n)\)

Q: Serialize and Deserialize Binary Tree
Design an algorithm to serialize and deserialize a binary tree.
A: Solution
Use level-order traversal (BFS) with a queue to handle node values and nulls. See editorial.
Data Structure
Binary Tree
Complexity
Runtime: \(O(n)\)
Space: \(O(n)\)

Q: Lowest Common Ancestor of a Binary Tree
Given a binary tree, find the lowest common ancestor of two given nodes in the tree.
A: Solution
Traverse the tree with depth-first search, using boolean flags to track if nodes p and q are found, and identify the lowest common ancestor as the node where any two of the flags (left, right, or mid) are true. See editorial.
Data Structure
Binary Tree
Complexity
Runtime: \(O(n)\)
Space: \(O(n)\)

Q: Path Sum
Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.
A: Solution
If node is not a leaf, recursively call hasPathSum for its children with targetSum decremented by the current node value. If node is a leaf, check if targetSum is zero. See editorial.
Data Structure
Binary Tree
Complexity
Runtime: \(O(n)\)
Space: \(O(n)\)

Q: Path Sum II
Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum.
A: Solution
If node is not a leaf, recursively call hasPathSum for its children with targetSum decremented by the current node value. If node is a leaf, check if targetSum is zero. Keep track of the node path using backtracking. See editorial.
Data Structure
Binary Tree
Complexity
Runtime: \(O(n^2)\)
Space: \(O(n)\)

Q: Path Sum III
Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum. The path does not need to start or end at the root or a leaf, but it must go downwards.
A: Solution
Recursively travese the binary tree using a hash table to track prefix sums, accounting for 2 situations: continuous subarray starts from the beginning or continuous subarray starts from the middle (check if currentSum - targetSum is in the hash table). See editorial.
Data Structure
Binary Tree
Complexity
Runtime: \(O(n)\)
Space: \(O(n)\)

Q: Kth Largest Element in a Stream
Implement the KthLargest class that supports the add function.
A: Solution
Use a min-heap to keep track of the k largest elements, throwing away any additional elements over k. The k-th largest element is the min of the heap. See editorial.
Data Structure
Heap
Complexity
Runtime: \(O(N⋅log N+M⋅log k)\)
Space: \(O(N)\)

Q: Last Stone Weight
You are given an array of integers stones where stones[i] is the weight of the i-th stone. We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights x and y with x <= y. The result of this smash is: (a) if x == y, both stones are destroyed; and (ii) if x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x. At the end of the game, there is at most one stone left. Return the weight of the last remaining stone.
A: Solution
Simulate using a heap. See editorial.
Data Structure
Heap
Complexity
Runtime: \(O(n⋅log n)\)
Space: \(O(n)\)

Q: K Closest Points to Origin
Given an array of points and an integer k, return the k closest points to the origin (0, 0).
A: Solution
Keep track of the k-closest points in a max heap, throwing away extra elements. Better methods include binary search to find the cut-off distance and QuickSelect. See editorial.
Data Structure
Heap
Complexity
Runtime: \(O(n⋅log k)\)
Space: \(O(k)\)

Q: Kth Largest Element in an Array
Given an integer array nums and an integer k, return the k-th largest element in the array.
A: Solution
Keep track of the k-largest elements in a min heap by throwing away extra elements. See editorial.
Data Structure
Heap
Complexity
Runtime: \(O(n⋅log k)\)
Space: \(O(k)\)

Q: Task Scheduler
You are given an array of CPU tasks, each represented by letters A to Z, and a cooling time, n. Each cycle or interval allows the completion of one task. Tasks can be completed in any order, but there's a constraint: identical tasks must be separated by at least n intervals due to cooling time. Return the minimum number of intervals required to complete all tasks.
A: Solution
Organise the most frequent tasks first, then fill in the gaps with other tasks or idle time. See editorial.
Data Structure
Heap
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: Design Twitter
Design a simplified version of Twitter where users can post tweets, follow/unfollow another user, and is able to see the 10 most recent tweets in the user's news feed.
A: Solution
Use a min-heap to track and retrieve the 10 most recent tweets by timestamp using a tuple. See editorial.
Data Structure
Heap
Complexity
Runtime: \(O(n⋅log k)\)
Space: \(O(k)\)

Q: Find Median from Data Stream
Implement the MedianFinder class that supports the addNum and findMedian functions.
A: Solution
Use two heaps to keep track of the middle elements, balancing the size of the heaps by moving items between them when necessary. See editorial.
Data Structure
Heap
Complexity
Runtime: \(O(log n)\)
Space: \(O(n)\)

Q: Sliding Window Median
You are given an integer array nums and an integer k. There is a sliding window of size k which is moving from the very left of the array to the very right. Return the median array for each window in the original array.
A: Solution
Maintain two balanced sorted lists, `lo` and `hi`, to efficiently track the smallest and largest halves of the current window. See editorial.
Data Structure
Heap
Complexity
Runtime: \(O(n⋅log k)\)
Space: \(O(k)\)

Q: IPO
You are given n projects where the i-th project has a pure profit profits[i] and a minimum capital of capital[i] is needed to start it. Initially, you have w capital. When you finish a project, you will obtain its pure profit and the profit will be added to your total capital. Pick a list of at most k distinct projects from given projects to maximize your final capital, and return the final maximized capital.
A: Solution
Sort projects by capital and add them to a max-heap as they become unlocked. Greedily choose the project with the highest profit each time. See editorial.
Data Structure
Heap
Complexity
Runtime: \(O(n⋅log n)\)
Space: \(O(n)\)

Q: Kth Smallest Element in a Sorted Matrix
Given an n x n matrix where each of the rows and columns is sorted in ascending order, return the k-th smallest element in the matrix.
A: Solution
Interpret the problem as solving n lists (either the rows or the columns) and keep track of the n pointers and their values in a min-heap, popping from the heap until k is reached. See editorial.
Data Structure
Heap
Complexity
Runtime: \(O(X + k⋅log X)\)
Space: \(O(X)\)

Q: Smallest Range Covering Elements from K Lists
You have k lists of sorted integers in non-decreasing order. Find the smallest range that includes at least one number from each of the k lists.
A: Solution
Get the smallest range using the first element of each list and then incrementally update the range by increasing the smallest element, using a heap to keep track. See editorial.
Data Structure
Heap
Complexity
Runtime: \(O(n⋅log m)\)
Space: \(O(m)\)

Q: Subsets
Given an integer array nums of unique elements, return all possible subsets (the power set).
A: Solution
Use backtracking to recursively build solutions. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n⋅2^n)\)
Space: \(O(n)\)

Q: Combination Sum
Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target.
A: Solution
Use backtracking to incrementally build the combination, and once we find the current combination is not valid, we backtrack and try another option. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(N^(T/M+1))\)
Space: \(O(T/M)\)

Q: Permutations
Given an array nums of distinct integers, return all the possible permutations.
A: Solution
Use backtracking to incrementally build the solution. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n⋅n!)\)
Space: \(O(n)\)

Q: Subsets II
Given an integer array nums that may contain duplicates, return all possible subsets (the power set).
A: Solution
Use backtracking to incrementally build the solution. Duplicates are avoided by skipping over consecutive identical elements in the sorted list. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n⋅2^n)\)
Space: \(O(n)\)

Q: Combination Sum II
Given an array of integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target.
A: Solution
Use backtracking to incrementally build the solution. Duplicates are avoided by skipping over consecutive identical elements in the sorted list. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(2^n)\)
Space: \(O(n)\)

Q: Word Search
Given an m x n grid of characters board and a string word, return true if word exists in the grid.
A: Solution
Use backtracking to walk around the grid, marking the choice at each step before continuing. At the end of each step, revert the mark to try another direction. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(3^L⋅n)\)
Space: \(O(L)\)

Q: Palindrome Partitioning
Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.
A: Solution
Use backtracking to incrementally build the solution, checking for valid palindromes before adding them. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n⋅2^n)\)
Space: \(O(n)\)

Q: Letter Combinations of a Phone Number
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.
A: Solution
Use backtracking to incrementally build letter combinations. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(4^n⋅n)\)
Space: \(O(n)\)

Q: N-Queens
The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other. Given an integer n, return all distinct solutions to the n-queens puzzle.
A: Solution
Use backtracking to place queens on an `n x n` board, ensuring that each queen is safe by checking for conflicts in columns, diagonals, and anti-diagonals, and recursively building solutions row by row until all queens are placed. Queens are placed row-by-row, using the board and row number as the state. The backtracking function maintains sets of columns, diagonals (row + column = constant), and anti-diagonals (row - column = constant) already occupied by queens for efficient conflict checking. See editorial.
Data Structure
Matrix
Complexity
Runtime: \(O(n!)\)
Space: \(O(n^2)\)

Q: Sudoku Solver
Write a program to solve a Sudoku puzzle by filling the empty cells.
A: Solution
Use backtracking to fill each empty cell in the Sudoku board by trying all valid numbers, pruning invalid choices based on the current row, column, and 3x3 sub-grid until the board is completely solved. Use the board and cell number as the state. The Sudoku board is complete when the last cell number is reached. See editorial.
Data Structure
Matrix
Complexity
Runtime: \(O(n!^9)\)
Space: \(O(1)\)

Q: Implement Trie (Prefix Tree)
Implement the Trie class that supports insert, search and startsWith functions.
A: Solution
Insert: iterate through the word, creating TrieNodes (consisting of a children dict and a terminal token as a key in the dict) if necessary and marking the end as a terminal; Search: iterate through the Trie, checking if terminal is present; startsWith: iterate through the Trie, checking if TrieNode exists. See editorial.
Data Structure
Trie
Complexity
Runtime: \(—\)
Space: \(—\)

Q: Design Add And Search Words Data Structure
Implement the WordDictionary class that supports the addWord and search functions.
A: Solution
Use a Trie, using a hash table for the child nodes and a special token in the hash table to indicate that a node is terminal. See editorial.
Data Structure
Trie
Complexity
Runtime: \(—\)
Space: \(—\)

Q: Word Search II
Given an m x n board of characters and a list of strings words, return all words on the board.
A: Solution
Uses a Trie for fast prefix matching and starting at each cell, backtrack to explore potential word paths. See editorial.
Data Structure
Trie
Complexity
Runtime: \(O(M(4⋅3^{L−1}))\)
Space: \(O(n)\)

Q: Longest Common Prefix
Write a function to find the longest common prefix string amongst an array of strings.
A: Solution
Use binary search to find the last index where all strings are equal. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(s⋅log m)\)
Space: \(O(1)\)

Q: Number of Islands
Given an m x n 2D binary grid grid which represents a map of 1s (land) and 0s (water), return the number of islands.
A: Solution
Iterate through the matrix, flood filling any island encountered, while incrementing the count. See editorial.
Data Structure
Union-Find
Complexity
Runtime: \(O(m⋅n)\)
Space: \(O(m⋅n)\)

Q: Max Area of Island
You are given an m x n binary matrix grid. An island is a group of 1s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water. The area of an island is the number of cells with a value 1 in the island. Return the maximum area of an island in grid.
A: Solution
Iterate through the matrix, flood filling any island encountered, while incrementing keeping track of the max area. See editorial.
Data Structure
Matrix
Complexity
Runtime: \(O(r⋅c)\)
Space: \(O(r⋅c)\)

Q: Clone Graph
Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph.
A: Solution
Traverse all the nodes, using a visited hash table to avoid cycles. See editorial.
Data Structure
Hash Table
Complexity
Runtime: \(O(m+n)\)
Space: \(O(n)\)

Q: Walls and Gates
You are given an m x n grid rooms initialized with these three possible values: -1 a wall; 0 a gate; or INF an empty room. Fill each empty room with the distance to its nearest gate.
A: Solution
Uses breadth-first search to propagate the shortest distance from each gate to all reachable empty rooms by spreading out level-by-level. See editorial.
Data Structure
Matrix
Complexity
Runtime: \(O(m⋅n)\)
Space: \(O(m⋅n)\)

Q: Rotting Oranges
You are given an m x n grid where each cell can have one of three values: 0 representing an empty cell; 1 representing a fresh orange; or 2 representing a rotten orange. Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten. Return the minimum number of minutes that must elapse until no cell has a fresh orange.
A: Solution
Use breadth-first search to simulate the spread of rot from initially rotten oranges, tracking the time until no fresh oranges remain, or determining if some will never rot by decrementing the fresh_count during the search. See editorial.
Data Structure
Matrix
Complexity
Runtime: \(O(m⋅n)\)
Space: \(O(m⋅n)\)

Q: Pacific Atlantic Water Flow
There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges. The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c). The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is less than or equal to the current cell's height. Water can flow from any cell adjacent to an ocean into the ocean. Return a 2D list of grid coordinates result where result[i] = [ri, ci] denotes that rain water can flow from cell (ri, ci) to both the Pacific and Atlantic oceans.
A: Solution
Use breadth-first search to find all cells that can be reached from the Pacific and Atlantic Oceans. The answer is the intersection of the two sets. See editorial.
Data Structure
Matrix
Complexity
Runtime: \(O(m⋅n)\)
Space: \(O(m⋅n)\)

Q: Surrounded Regions
You are given an m x n matrix board containing letters X and O, capture regions that are surrounded. A surrounded region is captured by replacing all Os with Xs in the input matrix board.
A: Solution
Use Union-Find to group connected 'O's, as well as all border 'O's. Flip all 'O's that are not connected to the border 'O's to 'X'. See editorial.
Data Structure
Union-Find
Complexity
Runtime: \(O(m⋅n)\)
Space: \(O(m⋅n)\)

Q: Course Schedule
There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [a_i, b_i] indicates that you must take course b_i first if you want to take course a_i. Return true if you can finish all courses. Otherwise, return false.
A: Solution
Use topological sort to check for cycles. See editorial.
Data Structure
Graph
Complexity
Runtime: \(O(V+E)\)
Space: \(O(V+E)\)

Q: Course Schedule II
There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [a_i, b_i] indicates that you must take course b_i first if you want to take course a_i. Return the ordering of courses you should take to finish all courses.
A: Solution
Use topological sort to determine ordering. See editorial.
Data Structure
Graph
Complexity
Runtime: \(O(V+E)\)
Space: \(O(V+E)\)

Q: Graph Valid Tree
You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [a_i, b_i] indicates that there is an undirected edge between nodes a_i and b_i in the graph. Return true if the edges of the given graph make up a valid tree, and false otherwise.
A: Solution
A graph is a tree if and only if it is fully-connected and it contains no cycles. Use Union-Find to check whether it is fully-connected. Number of edges must be one less than the number of nodes to contain no cycles. See editorial.
Data Structure
Union-Find
Complexity
Runtime: \(O(n⋅α(n))\)
Space: \(O(n)\)

Q: Number of Connected Components in an Undirected Graph
You have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [a_i, b_i] indicates that there is an edge between a_i and b_i in the graph. Return the number of connected components in the graph.
A: Solution
Use the Union-Find data structure to count number of connected components. See editorial.
Data Structure
Union-Find
Complexity
Runtime: \(O(V+E⋅α(n))\)
Space: \(O(V)\)

Q: Redundant Connection
You are given a graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The graph is represented as an array edges of length n where edges[i] = [a_i, b_i] indicates that there is an edge between nodes a_i and b_i in the graph. Return an edge that can be removed so that the resulting graph is a tree of n nodes.
A: Solution
Use the Union-Find data structure to check if edges are connected before adding them. The redundant connection is the edge that is already connected. See editorial.
Data Structure
Union-Find
Complexity
Runtime: \(O(n)\)
Space: \(O(n)\)

Q: Word Ladder
Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord such that every adjacent pair of words differs by a single letter.
A: Solution
Pre-process the nodes to find all possible intermediate states and use breadth-first search. See editorial.
Data Structure
Complexity
Runtime: \(O(m^2⋅n)\)
Space: \(O(m^2⋅n)\)

Q: Flood Fill
An image is represented by an m x n integer grid image where image[i][j] represents the pixel value of the image. You are also given three integers sr, sc, and color. Perform a flood fill on the image starting from the pixel image[sr][sc] and return the modified image after performing the flood fill.
A: Solution
Use a stack to perform depth-first search flood filling. Remember to check that the starting colour and replacement colour are different. See editorial.
Data Structure
Matrix
Complexity
Runtime: \(O(n)\)
Space: \(O(n)\)

Q: Number of Provinces
A province is a group of directly or indirectly connected cities and no other cities outside of the group. Given an n x n matrix isConnected, return the total number of provinces.
A: Solution
Use the Union-Find data structure to count number of provinces. See editorial.
Data Structure
Union-Find
Complexity
Runtime: \(O(n^2)\)
Space: \(O(n)\)

Q: Is Graph Bipartite?
A graph is bipartite if the nodes can be partitioned into two independent sets A and B such that every edge in the graph connects a node in set A and a node in set B. Given a 2D array graph where graph[u] is an array of nodes that node u is adjacent to, return true if and only if it is bipartite.
A: Solution
Use the Union-Find data structure ensure each edge is unconnected, while unioning together all the neighbours of each node. See editorial.
Data Structure
Union-Find
Complexity
Runtime: \(O(n)\)
Space: \(O(n)\)

Q: Reconstruct Itinerary
You are given a list of airline tickets where tickets[i] = [from_i, to_i] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it assuming all the tickets belong to a man who departs from JFK.
A: Solution
Use Hierholzer's Algorithm to find the Eulerian Circuit. See editorial.
Data Structure
Graph
Complexity
Runtime: \(O(E⋅log V/E​)\)
Space: \(O(V+E)\)

Q: Min Cost to Connect All Points
You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [x_i, y_i]. Return the minimum cost (measured in Manhattan Distance) to make all points connected.
A: Solution
Use the Union-Find data structure to find the minimum spanning tree using Kruskal's Algorithm. See editorial.
Data Structure
Union-Find
Complexity
Runtime: \(O(n^2⋅log n)\)
Space: \(O(n^2)\)

Q: Network Delay Time
You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (u_i, v_i, w_i), where u_i is the source node, v_i is the target node, and w_i is the time it takes for a signal to travel from source to target. We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal.
A: Solution
Use Djikstra's algorithm. See editorial.
Data Structure
Graph
Complexity
Runtime: \(O(N+E⋅log N)\)
Space: \(O(N+E)\)

Q: Swim in Rising Water
You are given an n x n integer matrix grid where each value grid[i][j] represents the elevation at that point (i, j). The rain starts to fall. At time t, the depth of the water everywhere is t. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at most t. You can swim infinite distances in zero time. Of course, you must stay within the boundaries of the grid during your swim. Return the least time until you can reach the bottom-right square (n - 1, n - 1) if you start at the top-left square (0, 0).
A: Solution
Put all depths in a sorted list and use binary search to find the first depth that can find a path from top-left to bottom-right using depth-first search. See editorial.
Data Structure
Graph
Complexity
Runtime: \(O(n^2⋅log n)\)
Space: \(O(n^2)\)

Q: Alien Dictionary
There is a new alien language that uses the English alphabet. However, the order of the letters is unknown to you. You are given a list of strings words from the alien language's dictionary. Now it is claimed that the strings in words are sorted lexicographically by the rules of this new language. If this claim is incorrect, and the given arrangement of string in words cannot correspond to any order of letters, return "". Otherwise, return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language's rules.
A: Solution
Construct a graph based on the order of characters in adjacent words, then uses topological sorting to determine a valid character order. See editorial.
Data Structure
Graph
Complexity
Runtime: \(O(C)\)
Space: \(O(1)\)

Q: Cheapest Flights Within K Stops
There are n cities connected by some number of flights. You are given an array flights where flights[i] = [from_i, to_i, price_i] indicates that there is a flight from city from_i to city to_i with cost price_i. You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops.
A: Solution
Use Djikstra's algorithm. See editorial.
Data Structure
Graph
Complexity
Runtime: \(O((N+E)⋅K)\)
Space: \(O(N)\)

Q: Minimum Height Trees
Given a tree of n nodes labelled from 0 to n - 1, and an array of n - 1 edges where edges[i] = [a_i, b_i] indicates that there is an undirected edge between the two nodes a_i and b_i in the tree, you can choose any node of the tree as the root. Return the root labels of all minimum height trees.
A: Solution
Iteratively remove the leaves of the graph until we converge towards the central (1 or 2) nodes, which are the roots of the minimum height trees. See editorial.
Data Structure
Graph
Complexity
Runtime: \(O(|V|)\)
Space: \(O(|V|)\)

Q: Accounts Merge
Given a list of accounts where each element accounts[i] is a list of strings, where the first element accounts[i][0] is a name, and the rest of the elements are emails representing emails of the account. Merge the accounts by email, returning the accounts in the following format: the first element of each account is the name, and the rest of the elements are emails in sorted order.
A: Solution
Use Union-Find to group together accounts that share common emails, ensuring that all related accounts are merged into the same group. See editorial.
Data Structure
Union-Find
Complexity
Runtime: \(O(n⋅k⋅log n⋅k)\)
Space: \(O(n⋅k)\)

Q: Climbing Stairs
You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
A: Solution
Use Dynamic Programming to calculate the n-th Fibonnacci Number starting with 1 and 2. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: Min Cost Climbing Stairs
You are given an integer array cost where cost[i] is the cost of i-th step on a staircase. Once you pay the cost, you can either climb one or two steps. You can either start from the step with index 0, or the step with index 1. Return the minimum cost to reach the top of the floor.
A: Solution
Use Dynamic Programming to iteratively update the cost at each step to include the minimum cost of reaching that step, allowing us to find the minimum cost to reach the top by considering the last two steps. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: House Robber
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night. Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
A: Solution
Use Dynamic Programming to keep track of the maximum amount of money that can be robbed by either including or excluding each house, ensuring that no two adjacent houses are robbed. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: House Robber II
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night. Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
A: Solution
handles the circular nature of the problem by considering two cases—excluding either the first or the last house—and then using the original House Robber approach to find the maximum amount that can be robbed in each case. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: Longest Palindromic Substring
Given a string s, return the longest palindromic substring in s.
A: Solution
Iterate through each element and expand outwards. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n^2)\)
Space: \(O(1)\)

Q: Palindromic Substrings
Given a string s, return the number of palindromic substrings in it.
A: Solution
Iterate through each element and expand outwards, keeping tracking of the total count. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n^2)\)
Space: \(O(1)\)

Q: Decode Ways
You have intercepted a secret message encoded as a string of numbers. The message is decoded via the following mapping: 1 -> A, 2 -> B, ..., 25 -> Y, 26 -> Z. However, while decoding the message, you realize that there are many different ways you can decode the message because some codes are contained in other codes (2 and 5 vs 25). Given a string s containing only digits, return the number of ways to decode it.
A: Solution
Use top-down Dynamic Programming. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n)\)
Space: \(O(n)\)

Q: Coin Change
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money. Return the fewest number of coins that you need to make up that amount.
A: Solution
Before calculating F(i), compute all minimum counts for amounts up to i. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(S⋅n)\)
Space: \(O(S)\)

Q: Maximum Product Subarray
Given an integer array nums, find a subarray that has the largest product, and return the product.
A: Solution
Similar to the Maximum Subarray problem, track the maximum and minimum products up to each point, because a negative number can turn the smallest product into the largest, ensuring that the global maximum product is found even in the presence of negative numbers. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: Word Break
Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.
A: Solution
Use top-down Dynamic Programming, storing position i of the string as the state. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n⋅m⋅k)\)
Space: \(O(n)\)

Q: Longest Increasing Subsequence
Given an integer array nums, return the length of the longest strictly increasing subsequence.
A: Solution
Use bottom-up Dynamic Programming, using position i as the longest increasing subsequence up to that point in the list. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n^2)\)
Space: \(O(n)\)

Q: Partition Equal Subset Sum
Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.
A: Solution
Use bottom-up Dynamic Programming to see if it's possible to reach half the sum of the original array. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(m⋅n)\)
Space: \(O(m⋅n)\)

Q: Maximum Profit in Job Scheduling
We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i]. Given the startTime, endTime and profit arrays, return the maximum profit you can take such that there are no two jobs in the subset with overlapping time range.
A: Solution
Recursively choose between skipping or taking each job, using memoization to store intermediate results and binary search to efficiently find the next non-conflicting job. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n⋅log n)\)
Space: \(O(n)\)

Q: Unique Paths
There is a robot on an m x n grid. The robot is initially located at the top-left corner. The robot tries to move to the bottom-right corner. The robot can only move either down or right at any point in time. Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.
A: Solution
Use Dynamic Programming to sum up the possible paths above and to the left of the current cell. Solution can be optimised to use a 1-d array. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(m⋅n)\)
Space: \(O(m⋅n)\)

Q: Longest Common Subsequence
Given two strings text1 and text2, return the length of their longest common subsequence.
A: Solution
Use a Dynamic Programming grid to track the length of the subsequence at each step, comparing characters and choosing the optimal subsequence length based on previous computations. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(m⋅n)\)
Space: \(O(m⋅n)\)

Q: Best Time to Buy and Sell Stock with Cooldown
You are given an array prices where prices[i] is the price of a given stock on the i-th day. Find the maximum profit you can achieve, with the restriction that after you sell your stock, you cannot buy stock on the next day.
A: Solution
Use Dynamic Programming with memoization to explore all possible states (holding, selling, or resetting) at each day. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: Coin Change II
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money. Return the number of combinations that make up that amount.
A: Solution
Uses bottom-up Dynamic Programming to iteratively build up the number of ways to make each amount by adding the contributions of each coin. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n⋅amount)\)
Space: \(O(n⋅amount)\)

Q: Target Sum
You are given an integer array nums and an integer target. You want to build an expression out of nums by adding one of the symbols + and - before each integer in nums and then concatenate all the integers. Return the number of different expressions that you can build, which evaluates to target.
A: Solution
Use top-down Dynamic Programming to recursively exploring all possible sums at each step. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(t⋅n)\)
Space: \(O(t⋅n)\)

Q: Interleaving String
Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.
A: Solution
Use top-down Dynamic Programming to recursively validate each character's position. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(m⋅n)\)
Space: \(O(m⋅n)\)

Q: Longest Increasing Path in a Matrix
Given an m x n integers matrix, return the length of the longest increasing path in matrix.
A: Solution
Use Topological Sort to process nodes in order of dependencies, updating path lengths as it traverses through the matrix. See editorial.
Data Structure
Matrix
Complexity
Runtime: \(O(m⋅n)\)
Space: \(O(m⋅n)\)

Q: Distinct Subsequences
Given two strings s and t, return the number of distinct subsequences of s which equals t.
A: Solution
Use top-down Dynamic Programming to recursively explore and sum all valid matching paths. See editorial.
Data Structure
Matrix
Complexity
Runtime: \(O(m⋅n)\)
Space: \(O(m⋅n)\)

Q: Edit Distance
Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. The three permitted operations are: (i) insert a character; (ii) delete a character; and (iii) replace a character.
A: Solution
Use top-down Dynamic Programming to explore all possible edits (insert, delete, replace) and choose the most efficient path. See editorial.
Data Structure
Matrix
Complexity
Runtime: \(O(m⋅n)\)
Space: \(O(m⋅n)\)

Q: Burst Balloons
You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons. If you burst the i-th balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it. Return the maximum coins you can collect by bursting the balloons wisely.
A: Solution
Use top-down Dynamic Programming to recursively choose the last balloon to burst in each subrange. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n^3)\)
Space: \(O(n^2)\)

Q: Regular Express Matching
Given an input string s and a pattern p, implement regular expression matching with support for . and *.
A: Solution
Use top-down Dynamic Programming to recursively check if the string matches the pattern by calculating the first_match and then handling each character, including the Kleene star (*), to explore all valid ways the pattern can match the string. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(T⋅P)\)
Space: \(O(T⋅P)\)

Q: 01 Matrix
Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.
A: Solution
Use bottom-up Dynamic Programming from top-left, going right and down, then from bottom-right, going left and up. See editorial.
Data Structure
Matrix
Complexity
Runtime: \(O(m⋅n)\)
Space: \(O(m⋅n)\)

Q: Maximum Subarray
Given an integer array nums, find the subarray with the largest sum, and return its sum.
A: Solution
Use Kadane's Algorithm. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: Jump Game
You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position. Return true if you can reach the last index, or false otherwise.
A: Solution
Greedily track the farthest position reachable at each step, ensuring that the current index is always within reach. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: Jump Game II
You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0]. Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where: 0 <= j <= nums[i] and i + j < n. Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].
A: Solution
Greedily extend the farthest reachable point at each step, making a jump when necessary. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: Gas Station
There are n gas stations along a circular route, where the amount of gas at the i-th station is gas[i]. You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the i-th station to its next (i + 1)-th station. You begin the journey with an empty tank at one of the gas stations. Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1.
A: Solution
Track cumulative gas gains and, upon hitting a "valley" (negative cumulative gain), reset the starting point to the next station with zero initial gas, ensuring a potential circuit completion. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: Hand of Straights
Alice has some number of cards and she wants to rearrange the cards into groups so that each group is of size groupSize, and consists of groupSize consecutive cards. Given an integer array hand where hand[i] is the value written on the i-th card and an integer groupSize, return true if she can rearrange the cards, or false otherwise.
A: Solution
Find and validate the smallest possible starting point for each sequence, then form consecutive groups of the required size while decrementing the count for each card used. See editorial.
Data Structure
Hash Table
Complexity
Runtime: \(O(n)\)
Space: \(O(n)\)

Q: Merge Triplets to Form Target Triplet
You are given a 2D integer array triplets, where triplets[i] = [a_i, b_i, c_i] describes the i-th triplet. You are also given an integer array target = [x, y, z] that describes the triplet you want to obtain. To obtain target, you may apply the following operation on triplets any number of times (possibly zero): choose two indices (0-indexed) i and j (i != j) and update triplets[j] to become [max(a_i, a_j), max(b_i, b_j), max(c_i, c_j)]. Return true if it is possible to obtain the target triplet [x, y, z] as an element of triplets, or false otherwise.
A: Solution
Greedily check each triplet to see if contributes to any component of the target, and early exit once all components are matched. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: Partition Labels
You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part. Return a list of integers representing the size of these parts.
A: Solution
Track the farthest point a character must reach within its segment using a hash table, and whenever you reach this point in the string, partition and start a new segment. See editorial.
Data Structure
Hash Table
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: Valid Parenthesis String
Given a string s containing only three types of characters: (, ) and *, return true if s is valid. Note that * can be treated as a single right parenthesis ) or a single left parenthesis ( or an empty string.
A: Solution
Use top-down Dynamic Programming to recursively explore all possible ways to balance the brackets, using the bracket count and string position as state. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n^2)\)
Space: \(O(n^2)\)

Q: Insert Interval
You are given an array of non-overlapping intervals intervals where intervals[i] = [start_i, end_i] represent the start and the end of the i-th interval and intervals is sorted in ascending order by start_i. You are also given an interval newInterval = [start, end] that represents the start and end of another interval. Insert newInterval into intervals such that intervals is still sorted in ascending order by start_i and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary). Return intervals after the insertion.
A: Solution
Iterate through all the intervals in three phases: no overlaps before merging, overlapping and merging, and no overlapping after merging. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: Merge Intervals
Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
A: Solution
Sort the intervals by start value then merge them. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n⋅log n)\)
Space: \(O(n)\)

Q: Interval List Intersections
You are given two lists of closed intervals. Each list of intervals is pairwise disjoint and in sorted order. Return the intersection of these two interval lists.
A: Solution
Use two pointers to simultaneously iterate through the two sorted interval lists, adding the intersection of overlapping intervals to the result, and advancing the pointer of the list with the smaller endpoint. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(m+n)\)
Space: \(O(m+n)\)

Q: Non-overlapping Intervals
Given an array of intervals intervals where intervals[i] = [start_i, end_i], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
A: Solution
Sort intervals by their end times and greedily keep the interval with the earliest end time that doesn't overlap with the previous one. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n⋅log n)\)
Space: \(O(n)\)

Q: Meeting Rooms
Given an array of meeting time intervals where intervals[i] = [start_i, end_i], determine if a person could attend all meetings.
A: Solution
Compare the end of each interval with the start of the next to ensure no overlap. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n⋅log n)\)
Space: \(O(1)\)

Q: Meeting Rooms II
Given an array of meeting time intervals intervals where intervals[i] = [start_i, end_i], return the minimum number of conference rooms required.
A: Solution
Sort intervals by start time and use a min-heap to track the earliest ending meeting, ensuring rooms are reused when possible. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n⋅log n)\)
Space: \(O(n)\)

Q: Minimum Interval to Include Each Query
You are given a 2D integer array intervals, where intervals[i] = [left_i, right_i] describes the i-th interval starting at left_i and ending at right_i (inclusive). You are also given an integer array queries. The answer to the j-th query is the size of the smallest interval i such that left_i <= queries[j] <= right_i. If no such interval exists, the answer is -1. Return an array containing the answers to the queries.
A: Solution
Sort intervals and queries, then use a min-heap, which is only populated once, to track the smallest valid interval as it processes each query. See editorial.
Data Structure
Array
Complexity
Runtime: \(O((m+n) log m+n log n)\)
Space: \(O(m+n)\)

Q: Rotate Image
You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise) in-place.
A: Solution
To rotate a matrix clockwise, take the transpose and the (left-to-right) reflection. See editorial.
Data Structure
Matrix
Complexity
Runtime: \(O(M)\)
Space: \(O(1)\)

Q: Spiral Matrix
Given a m x n matrix, return all elements of the matrix in spiral order.
A: Solution
Progressively narrow the boundaries of the matrix while collecting elements. See editorial.
Data Structure
Matrix
Complexity
Runtime: \(O(m⋅n)\)
Space: \(O(1)\)

Q: Set Matrix Zeroes
Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0s.
A: Solution
Mark rows and columns that need to be zeroed using the first row and column, while using boolean flags to handle the first row and column separately to avoid conflicts with matrix[0][0], which cannot be used to mark both. See editorial.
Data Structure
Matrix
Complexity
Runtime: \(O(m⋅n)\)
Space: \(O(1)\)

Q: Happy Number
Write an algorithm to determine if a number n is happy. A happy number is a number defined by the following process: (a) starting with any positive integer, replace the number by the sum of the squares of its digits; (ii) repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1; and (c) those numbers for which this process ends in 1 are happy. Return true if n is a happy number, and false if not.
A: Solution
Use a cycle detection method (like in linked lists) to determine if a number eventually reaches 1 or falls into a cycle with a 1. Note that the sum of the square of a number's digits cannot increase unboundedly. See editorial.
Data Structure
Linked List
Complexity
Runtime: \(O(log n)\)
Space: \(O(1)\)

Q: Plus One
You are 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 in left-to-right order. The large integer does not contain any leading 0s. Increment the large integer by one and return the resulting array of digits.
A: Solution
Increment the number represented by the digits array from the least significant digit to the most significant digit, handling carries and returning early if there are no more carries. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: Pow(x, n)
Implement pow(x, n), which calculates x raised to the power n (i.e., x^n).
A: Solution
Repeatedly use binary exponentiation (square the base and halve the exponent) to efficiently compute the power of a number, allowing the calculation of x^n with a logarithmic number of multiplications. See editorial.
Data Structure
—
Complexity
Runtime: \(O(log n)\)
Space: \(O(log n)\)

Q: Multiply Strings
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.
A: Solution
Simulate digit-by-digit multiplication of two numbers by considering each digit's place value, accumulating the results, and converting the final sum to a string. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(m⋅n)\)
Space: \(O(m+n)\)

Q: Detect Squares
Implement the DetectSquares class that supports the add and count functions.
A: Solution
Use a hash table to keep track of the frequency of added points, and iterate through all points while checking for valid square formations when counting. See editorial.
Data Structure
Hash Table
Complexity
Runtime: \(O(P)\)
Space: \(O(P)\)

Q: Single Number
Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
A: Solution
Use the XOR operation to efficiently find the single number that appears only once in the list, as XORing a number with itself cancels out, leaving the unique number. See editorial.
Data Structure
—
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: Number of 1 Bits
Write a function that takes the binary representation of a positive integer and returns the number of set bits it has (also known as the Hamming weight).
A: Solution
Repeatedly divide the number by 2 and sum up the remainders. See editorial.
Data Structure
—
Complexity
Runtime: \(O(1)\)
Space: \(O(1)\)

Q: Counting Bits
Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1s in the binary representation of i.
A: Solution
Use bottom-up Dynamic Programming with bitwise operations to build the answer. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: Reverse Bits
Reverse bits of a given 32 bits unsigned integer.
A: Solution
Progressively swap adjacent bit pairs using bitwise operations and masks, achieving a full reversal in constant time. See editorial.
Data Structure
—
Complexity
Runtime: \(O(1)\)
Space: \(O(1)\)

Q: Missing Number
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.
A: Solution
Start with len(nums) (since the list is one short, we are missing index len(nums) when we iterate through the list indexes) and XOR each index and corresponding number, cancelling out all existing pairs, leaving only the missing number. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: Sum of Two Integers
Given two integers a and b, return the sum of the two integers without using the operators + and -.
A: Solution
XOR simulates addition without carry, and AND with shifting handles the carry, adjusting for sign and subtraction when necessary. See editorial.
Data Structure
—
Complexity
Runtime: \(O(1)\)
Space: \(O(1)\)

Q: Reverse Integer
Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-2^31, 2^31 - 1], then return 0.
A: Solution
Repeatedly extract and append the last digit, while handling the sign and ensuring the result stays within the 32-bit integer range. See editorial.
Data Structure
—
Complexity
Runtime: \(O(log x)\)
Space: \(O(1)\)

Q: Add Binary
Given two binary strings a and b, return their sum as a binary string.
A: Solution
Iterate from least significant bit to most, using divmod to handle both the sum and carry, and then reversing the result to produce the final binary sum. See editorial.
Data Structure
Array
Complexity
Runtime: \(O(n+m)\)
Space: \(O(max(n, m))\)

Q: Single Number II
Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.
A: Solution
Use two bitwise counters, `ones` and `twos`, to sequentially track and filter out bits that appear exactly once and twice, respectively, ensuring that after three occurrences, bits are removed, leaving only the unique number in ones. See editorial.
Data Structure
—
Complexity
Runtime: \(O(n)\)
Space: \(O(1)\)

Q: Complement of Base 10 Integer
The complement of an integer is the integer you get when you flip all the 0's to 1's and all the 1's to 0's in its binary representation. Given an integer n, return its complement.
A: Solution
Create a mask of all 1s that matches the bit length of the input number, then XOR it with the number to flip all its bits. See editorial.
Data Structure
—
Complexity
Runtime: \(O(1)\)
Space: \(O(1)\)