Blind Curated 74 Problems Flashcards
Two Sum
Store the array in a map. If Sum - arr[i] exists in the array, then return arr[i] and Sum - arr[i]
TC:
SC:
Longest Substring Without Repeating Characters
Window Expand — Until a repeated character is found.
Contract Window — i = Math.max(index(j), i);
if(indices[s.charAt(j)] != -1) {
i = Math.max(indices[s.charAt(j)] + 1, i);
}
maxLength = Math.max(maxLength, j - i + 1);
indices[s.charAt(j)] = j;
TC:
SC:
Longest Palindromic Substring
int len1 = expandAroundCenter(s, i, i);
int len2 = expandAroundCenter(s, i, i + 1);
int len = Math.max(len1, len2);
// Find the boundaries of the palindrome
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
TC:
SC:
Container With Most Water
https://leetcode.com/problems/container-with-most-water/
Two pointer approach. Move the pointer which has the minimum height between the two pointers forward
TC: O(N)
SC: O(1) -> No extra space.
3Sum
for every i find a pair in the array such that
Remove Nth Node From End of List
FirstNode = Head; SecondNode = Head
Advance the first node by N positions. Then move both pointers — first and second —until the first pointer reaches the end of the list.
TC:
SC:
Merge K Sorted Lists
https://leetcode.com/problems/merge-k-sorted-lists/
You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.
Input: lists = [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6] Explanation: The linked-lists are: [ 1->4->5, 1->3->4, 2->6 ] merging them into one sorted list: 1->1->2->3->4->4->5->6
Revisit the solution for Divide and Conquer Approach
https://www.youtube.com/watch?v=OaPaTaj0xYo&ab_channel=jayatitiwari
TC:
SC:
Search in Rotated Sorted Array
Find the pivot in the array — Smallest element in the array. Binary Search in right if the element is in the right half, else search in the left half of the array.
TC:
SC:
Combination Sum I
https://leetcode.com/problems/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. You may return the combinations in any order.
The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.
It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.
backtrack(int [] candidates,
LinkedList temp,
List> output,
int start,
int target) {
// Base case
for(int j = start; j < candidates.length; j++) {
temp.add(candidates[j]);
backtrack(candidates, temp, output, j, target - candidates[j]);
temp.removeLast();
}
}
TC:
SC:
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.
Each number in candidates may only be used once in the combination.
Note: The solution set must not contain duplicate combinations.
https://leetcode.com/problems/combination-sum-ii/
Input: candidates = [10,1,2,7,6,1,5], target = 8 Output: [ [1,1,6], [1,2,5], [1,7], [2,6] ]
for(int i = start; i < candidates.size(); i++) {
// Frequency
int[] currentCandidate = candidates.get(i);
int candidateValue = currentCandidate[0];
int frequency = currentCandidate[1];
if(frequency <= 0)
continue;
temp. add(candidateValue);
candidates. set(i, new int[]{candidateValue, frequency - 1});
// Continue exploration
backtrack(candidates, temp, output, remainingSum - candidateValue, i);
candidates.set(i, new int[]{candidateValue, frequency});
temp.removeLast();
}
Combination Sum ||| —Find all valid combinations of k numbers that sum up to n such that the following conditions are true:
Only numbers 1 through 9 are used.
Each number is used at most once.
Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.
https://leetcode.com/problems/combination-sum-iii/
Input: k = 3, n = 7 Output: [[1,2,4]] Explanation: 1 + 2 + 4 = 7 There are no other valid combinations.
Input: k = 3, n = 9 Output: [[1,2,6],[1,3,5],[2,3,4]] Explanation: 1 + 2 + 6 = 9 1 + 3 + 5 = 9 2 + 3 + 4 = 9 There are no other valid combinations.
Apply CombinationSum1 problem on the array [1,2,3,4,5,6,7,8,9].
Combination Sum IV — Dynamic programming
https://leetcode.com/problems/combination-sum-iv/solution/
Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.
The answer is guaranteed to fit in a 32-bit integer.
Input: nums = [1,2,3], target = 4 Output: 7 Explanation: The possible combination ways are: (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) Note that different sequences are counted as different combinations.
TBD
Given a reference of a node in a connected undirected graph.
Return a deep copy (clone) of the graph.
Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.
class Node {
public int val;
public List neighbors;
}
Test case format:
For simplicity, each node’s value is the same as the node’s index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list.
An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.
The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.
Q -> Data structure to store the nodes for which the clones aren’t created yet.
VisitedMa Nodes for which clones were created.
while(!q.isEmpty()) {
// Pop element from the queue
Node temp = q.remove();
for(Node neighbor: temp.neighbors) {
if(!visited.containsKey(neighbor)) {
// Clone the neighbor and add a mapping in the visited map.
visited.put(neighbor, new Node(neighbor.val, new ArrayList()));
q.add(neighbor);
}
// The clones of neighbors have just been created above. If the clone of temp has already
// been created, then create edges between the clone of temp and clone of neighbors of temp.
if(visited.containsKey(temp))
visited.get(temp).neighbors.add(visited.get(neighbor));
} }
TC: O(V + E)
SC: O(V)
V - Number of Vertices
E - Number of Edges.
Clone Graph DFS
public Node cloneGraphDFS(Node node) {
// Base case
if(node == null)
return node;
// If the node is already visited/ it's clone has been created before, then return the deep copy of the node.
if(visited.containsKey(node))
return visited.get(node);
// Create a clone of the node
Node nodeClone = new Node(node.val, new ArrayList());
// Mark the node as visited
visited.put(node, nodeClone);
// Recursively create clones of the neighbors of the node.
for(Node neighbor: node.neighbors) {
nodeClone.neighbors.add(cloneGraphDFS(neighbor));
}
return nodeClone; }
TC: O(V + E)
SC: O(V)
V - Number of Vertices
E - Number of Edges.
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] = [ai, bi] indicates that you must take course bi first if you want to take course ai.
For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
Return true if you can finish all courses. Otherwise, return false.
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.
- Build the Graph Adjacency List.
- Traverse the graph with each node of the graph as the starting node. Leaves breadcrumbs along the path and if you come across a node which has was visited before, then there exists a cycle in the graph.
For code: https://leetcode.com/problems/course-schedule/solution/
TC: E + V^2
SC: E + V
Course Schedule Topological Sort
https://leetcode.com/problems/course-schedule/
Two approaches:
1. DFS approach
a. With each node as the starting node, traverse the graph to check if a cycle exists in the graph.
b. Cycle detection using DFS:
isCycle(traversalPath, node, adjacency List) {
// Return false if the node isn’t present in the adjacency list.
// Return true if the node is visited already.
// Visit the node. traversalPath[node] = true;
// Recursively visit the neighboring nodes
// Set the node as node as unvisited while backtracking. traversalPath[node] == false;
} 2. Topological sort.
Number of Islands
https://leetcode.com/problems/number-of-islands/submissions/
Given an m x n 2D binary grid grid which represents a map of ‘1’s (land) and ‘0’s (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] Output: 1
- Iterate through the matrix
- If you encounter a one, then explore the island which the one is a part of. Mark the visited nodes as zero
- Counter the number of root nodes which that trigger DFS. Return this number after the exploration of the matrix.
Longest Consecutive Sequence
https://leetcode.com/problems/longest-consecutive-sequence/
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
You must write an algorithm that runs in O(n) time.
Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
- Store the elements in a HashSet
- Look for the minimum element arr[i] in the consecutive sequence
- Update the maximum length based on the length of the increasing subsequence recorded with arr[i] as the starting element.
Course Schedule
https://leetcode.com/problems/course-schedule/solution/
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] = [ai, bi] indicates that you must take course bi first if you want to take course ai.
For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
Return true if you can finish all courses. Otherwise, return false.
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.
- Identify nodes with InDegree == 0 — no prerquisites and add them to the global order.
- Remove the edges between such nodes and their dependencies.
- Repeat Step 1) until there are no nodes without prerequisites left.
- If there are still some left edges left in the graph, then there exists a cycle in the graph.
- Otherwise, all of the edges were removed from the graph, return the global
- Alien Dictionary
- Build the AdjacenyList and the IndegreeMap
Map> adjacenyList = new HashMap<>();
Map indegree = new HashMap<>(); - Compare the each word to the subsequent word and build out the character relations
- BFS
a. Add all nodes with indegree 0 to the queue
b. Pop the head from queue, let’s call it ‘node’ and append it to the output string.
c. Remove all the edges between the node and it’s adjacent elements
d. Repeat steps a through c until the queue is empty. - Return the output string.
- Number of Connected Components in an Undirected Graph
- Everyone is their own representative initially and the total families would be equal to the number of individuals.
- Iterate through the relationships of the family.
- For every relationship, determine if sub-families can be combined into a larger family, and combine if they can be.
- Decrement the total family count if a merge is made
- Return the total number of families after the merge.
Graph Valid Tree
https://leetcode.com/problems/graph-valid-tree/submissions/
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] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the graph.
Return true if the edges of the given graph make up a valid tree, and false otherwise.
Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output: true
Input: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
Output: false
Iterative DFS:
1. Build the Adjacency list
adjacencyList.get(edge[0]).add(edge[1]);
adjacencyList.get(edge[1]).add(edge[0]);
2. Add the node 0 to a stack
3. Pop the top of the stack, let’s call it node.
4. Check if the neighbors of the node are seen:
a. If the neighbor is seen, then return false.
b. If the neighbor is not seen, then add it to the seen set.
c. Remove the edge neighbor -> node
5. If the number of elements in the seen set is <= n, then the graph is not a tree — as it is not fully connected.
Union Find:
- Everyone is their own representative initially and the total families would be equal to the number of individuals.
- Iterate through the relationships of the family.
- For every relationship, determine if sub-families can be combined into a larger family, and combine if they can be.
- Decrement the total family count if a merge is made
- Return the total number of families after the merge.
Coin Change
https://leetcode.com/problems/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. If that amount of money cannot be made up by any combination of the coins, return -1.
You may assume that you have an infinite number of each kind of coin.
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Input: coins = [1], amount = 0
Output: 0
private int coinChangeBottomUp(int[] coins, int amount, int[] storage) {
int[] memory = new int[amount + 1];
// Fill the memory with default values
Arrays.fill(memory, amount + 1);
// Base case
memory[0] = 0;
for(int i = 0; i <= amount; i++) {
int minCoins = Integer.MAX_VALUE;
for(int coin: coins) {
if(i - coin >= 0) {
memory[i] = Math.min(memory[i], 1 + memory[i - coin]);
}
}
}
return memory[amount] > amount ? -1: memory[amount];
}
Given an integer array nums, return the length of the longest strictly increasing subsequence.
A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Input: nums = [0,1,0,3,2,3]
Output: 4
for(int i = 1; i < nums.length; i++) {
int result = 0;
for(int j = 0; j < i; j++) {
// Check if nums[i] > nums[j]
if(nums[i] > nums[j]) {
//dp[i] = Math.max(dp[i], 1 + dp[j]);
//result = Math.max(result, dp[i]);
result = Math.max(result, dp[j]);
}
dp[i] = 1 + result;
endResult = Math.max(endResult, dp[i]);
}
}
Reverse Linked List
https://leetcode.com/problems/reverse-linked-list/
Given the head of a singly linked list, reverse the list, and return the reversed list.
- Two pointers appraoch
- Recursive reversal
// Figure out the recursion for three elements:
reverse(LinkedList head) {
// Base case
if(head == null || head.next == null)
return head;
ListNode p = reverse(head.next);
head. next.next = head;
head. next = null;
return p
}
Linked List Cycle
https://leetcode.com/problems/linked-list-cycle/
Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked list. Otherwise, return false.
- Two pointers, pointer1 at x pace, pointer2 at 2x pace, if they ever meet then there is a cycle.
https://leetcode.com/problems/merge-two-sorted-lists/
1->2->3
4->5>6
temp->1->2->3->4->5->6
Merge k Sorted Lists
https://leetcode.com/problems/merge-k-sorted-lists/solution/
TC: O(KN)
SC: O(1)
ListNode output;
mergeKSortedLists() {
for(int i = 1…NthList)
ListNode output = mergeTwoSortedLists(output, i);
}
return output;
TC: O(Nlogk)
SC: O(1)
TBD
Remove Nth Node From End of List
https://leetcode.com/problems/remove-nth-node-from-end-of-list/
- Advances first pointer so that the gap between first and second is n nodes apart
- Move first to the end, maintaining the gap
https://leetcode.com/problems/reorder-list/
1. Find the middle node of the list // 1->2->3->4->5->6
- Reverse the second half of the list
- Merge the two halves.
Set Matrix Zeroes
Given an m x n matrix. If an element is 0, set its entire row and column to 0. Do it in-place.
- Traverse through each call in the matrix
a. If any of the cell contains a zero, then set the first element in the row and column to zero - Traverse the matrix and set the element to zero if the either the matrix[0][i] or matrix[i][0] is zero.
https://leetcode.com/problems/spiral-matrix/
Given an m x n matrix, return all elements of the matrix in spiral order.
- Add the top row to the output
- Add the right column to the output
- Add the bottom row to the output
- Add the left column to the output.
while(r1 <= r2 && c1 <= c2) {
// Add the top row to the output.
for(int c = c1; c <= c2; c++) output.add(matrix[r1][c]);
// Add the right column to the output.
for(int r = r1 + 1; r <= r2; r++) output.add(matrix[r][c2]);
if(r1 < r2 && c1 < c2) {
// Add the botton row to the output.
for(int c = c2 -1; c >= c1; c--) output.add(matrix[r2][c]);
// Add the left column to the output.
for(int r = r2 - 1; r > r1; r--) output.add(matrix[r][c1]);
}
r1++;
c1++;
r2--;
c2--;
}
