Leetcode-Medium 🚧
Add Two Numbers
Linked ListMathRecursionInputs
class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { }}Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.
Input: l1 = [0], l2 = [0]
Output: [0]
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]
Process
Edge Cases
Longest Substring Without Repeating Characters
Hash TableStringSliding WindowInputs
class Solution { public int lengthOfLongestSubstring(String s) { }}Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
Process
Edge Cases
Unique Binary Search Trees
MathDynamic ProgrammingTreeBinary Search TreeBinary TreeInputs
class Solution { public int numTrees(int n) { }}Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST's:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
Input: n = 1
Output: 1
Sub problems
✅ Whether we can apply the DP here, can this be broken into further sub-problems.
✅ Can there be possibility that current result is based on the previous results.
✅ How many different combination can be formed using 1 Node, 2 Node, 3 Node, ..., n Node.
✅ Can you arrive any equation to solve the problem, based upon the previous points.
Edge Cases
Further Readings
✅ What is the Catalan Number?
The Catalan numbers are a sequence of natural numbers that occur in various counting problems,
often involving recursively defined objects.
C(n,k) = (n!) / [(n-k)! * k!] = [ n(n-1)(n-2)(n-3)....1 ] / [ (n-k)! * k! ]
Now (n-k)! factor get cancelled from Numerator and Denominator , and we got
C(n, k) = [ n(n-1)...( n-(k+1) ) ] / [ k*(k-1)*(k-2)....1 ].
= [ (n-1)/1 ] * [ ( n-2)/2 ] * [ (n-3) / 3 ].....[ (n - (k+1)) / k ]
The first Catalan numbers for n = 0, 1, 2, 3, ... are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, ...
Problems based on Catalan Number
✅Count the number of expressions containing n pairs of parentheses which are correctly matched. For n = 3, possible expressions are ((())), ()(()), ()()(), (())(), (()()).
✅Count the number of possible Binary Search Trees with n keys.
✅Count the number of full binary trees (A rooted binary tree is full if every vertex has either two children or no children) with n+1 leaves.
✅Given a number n, return the number of ways you can draw n chords in a circle with 2 x n points such that no 2 chords intersect.
Solution
class Solution { public int numTrees(int n) { long ans = 1; int k = n; n = 2*n; for(int i = 0 ; i < k ;i++){ ans *= (n-i); ans /= (i+1); } return (int)(ans/(k+1)); }}Binary Tree Level Order Traversal II
TreeBreadth-First SearchBinary TreeInputs
class Solution { public List<List<Integer>> levelOrderBottom(TreeNode root) { }}Input: root = [3,9,20,null,null,15,7]
Output: [[15,7],[9,20],[3]]
Input: root = [1]
Output: [[1]]
Input: root = []
Output: []
Sub-problems
✅ Will Recursion be a better solution? What is the complexity.
✅ If using Recursion, what will the helper method look like.
✅ Can you think of using Queue with some ArrayList to store the current level nodes.
Edge Cases
✅ Check for the root being null.
✅ Check if the root is the only node in the tree.
Further Readings
Solutions
Solution using Queue (DFS)
class Solution { public List<List<Integer>> levelOrderBottom(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if(root == null) return result; Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); while(!queue.isEmpty()){ int size = queue.size(); List<Integer> level = new ArrayList<>(); for(int i = 0; i < size; i++){ TreeNode node = queue.poll(); level.add(node.val); if(node.left != null) queue.add(node.left); if(node.right != null) queue.add(node.right); } result.add(0, level); } return result; }}Solution using DFS (Recursion)
public class Solution { public List<List<Integer>> levelOrderBottom(TreeNode root) { List<List<Integer>> wrapList = new LinkedList<List<Integer>>(); levelMaker(wrapList, root, 0); return wrapList; } public void levelMaker(List<List<Integer>> list, TreeNode root, int level) { if (root == null) return; if (level >= list.size()) { list.add(0, new LinkedList<Integer>()); } levelMaker(list, root.left, level + 1); levelMaker(list, root.right, level + 1); list.get(list.size() - level - 1).add(root.val); }}Convert Sorted List to Binary Search Tree
Linked ListDivide and ConquerTreeBinary Search TreeBinary TreeInputs
class Solution { public TreeNode sortedListToBST(ListNode head) { }}Sub-problems
✅ Can you apply the divide and conquer here?
✅ Can you find out the middle node in the linked list?
✅ The middle node will be treated as the Root of the BST.
✅ Can you find out the left and right sub-tree?
Edge Cases
✅ What if the List is empty?
✅ What if the List has only one node?
Snippets
Finding Middle node of LinkedList
public ListNode middleNode(ListNode head) { ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow;}Further Readings
Solution
class Solution { public TreeNode sortedListToBST(ListNode head) { return listToBST(head, null); } private TreeNode listToBST(ListNode head, ListNode tail) { if (head == null || head == tail) return null; ListNode mid = findMid(head, tail); TreeNode root = new TreeNode(mid.val); root.left = listToBST(head, mid); root.right = listToBST(mid.next, tail); return root; } private ListNode findMid(ListNode head, ListNode tail) { ListNode l1 = head, l2 = head; while (l2 != tail && l2.next != tail) { l1 = l1.next; l2 = l2.next.next; } return l1; }}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.
Each path should be returned as a list of the node values, not node references.
A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.
Inputs
class Solution { public List<List<Integer>> pathSum(TreeNode root, int targetSum) { }}Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22
Input: root = [1,2,3], targetSum = 5
Output: []
Input: root = [1,2], targetSum = 0
Output: []
Sub-problems
✅ Think about using Recursion. [Once you have figured it out using the Recursion, think about the parameters of the helper method that you will be using.]
✅ Moving from top - bottom with sub-tree root's value will be target minus the current root value.
✅ Once the targetSum or the RemainingSum is zero, you can hault the condtion. But is this all the cases that you need to check?
Edge Cases
✅ Check whether all the node's value are negative or positive.
✅ Check whether the root is null.
✅ If there is constraint like all the node's values are positive, and the input is targetSum<0, then you can return an empty list.
Further Readings
Solution
Solution using Recursion
class Solution { public List<List<Integer>> pathSum(TreeNode root, int targetSum) { List<List<Integer>> result = new ArrayList<>(); if(root == null) return result; helper(result, new ArrayList<>(), root, targetSum); return result; } private void helper(List<List<Integer>> result, List<Integer> list, TreeNode root, int targetSum) { if(root == null) return; list.add(root.val); if(root.left == null && root.right == null && targetSum == root.val) { result.add(new ArrayList<>(list)); } helper(result, list, root.left, targetSum - root.val); helper(result, list, root.right, targetSum - root.val); list.remove(list.size() - 1); }}Find K Pairs with Smallest Sums
ArrayHeap (Priority Queue)Inputs
class Solution { public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) { }}Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]]
Explanation: The first 3 pairs are returned from the sequence: [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
Input: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
Output: [[1,1],[1,1]]
Explanation: The first 2 pairs are returned from the sequence: [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]
Input: nums1 = [1,2], nums2 = [3], k = 3
Output: [[1,3],[2,3]]
Explanation: All possible pairs are returned from the sequence: [1,3],[2,3]
Sub-problems
✅ Using Priority Queue in such a manner that we don't have to produce nm(log(nm)) complexity solution. ✅ Adding only k items into the pq at any point of time. ✅ Which data-structure to use for storing the Pairs.
Edge Cases / Clarifications
✅ Checking if the input arrays are sorted. ✅ If anyone of the inputs given are null/0. Then return an empty list.
Further Readings
✅ Adding items to Priority Queue with Custom Comparator. ✅ Maintaining Priority Queue in a sorted manner and with Initial Capacity Constructor.
Solution
class Solution { public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) { int n = nums1.length; int m = nums2.length; List<List<Integer>> ans = new ArrayList(); if (n == 0 || m == 0) { return ans; } PriorityQueue<int[]> pq = new PriorityQueue(new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) { return (nums1[o1[0]] + nums2[o1[1]]) - (nums1[o2[0]] + nums2[o2[1]]); } }); for (int i = 0; i < Math.min(k, n); i++) { pq.add(new int[]{i, 0}); } int size = pq.size(); for (int i = 0; i < Math.min(k, n*m); i++) { int[] pair = pq.remove(); if (pair[1] < m - 1) { pq.add(new int[]{pair[0], pair[1]+1}); } List<Integer> subsolution = new ArrayList(); subsolution.add(nums1[pair[0]]); subsolution.add(nums2[pair[1]]); ans.add(subsolution); } return ans; }}//Time Complexity: ~O(k*log(k))//Space Complexity: ~O(k)Lexicographical Numbers
Depth-First SearchTrieInputs
class Solution { public List<Integer> lexicalOrder(int n) { }}Input: n = 13
Output: [1,10,11,12,13,2,3,4,5,6,7,8,9]
Input: n = 2
Output: [1,2]
Constraints:
1 <= n <= 5 * 104
Sub-problems
✅ Using Priority Queue using Custom Comparator (on Strings) but the problem is that it will be O(nlog(n)) complexity. ✅ How to compare the String respective of the Integer number. ✅ Can we use DFS to iterate from 1->9, add the value and its corresponding 10th multiplier. Like 1, 10, 11, 12, 13, etc., which is i*10+i.
Edge Cases
✅ If n is 0 or negative value. Then return an empty list. ✅ If n is 1. Then return [1].
Further Readings
✅ Using Priority Queue with Custom Comparator. ✅ Recursion and Sorting on the Collections.
Solution
Using DFS
public class Solution { public List<Integer> lexicalOrder(int n) { List<Integer> res = new ArrayList<>(); for(int i=1;i<10;++i){ dfs(i, n, res); } return res; } public void dfs(int cur, int n, List<Integer> res){ if(cur>n) return; else{ res.add(cur); for(int i=0;i<10;++i){ if(10*cur+i>n) return; dfs(10*cur+i, n, res); } } }}// Time Complexity: O(n)// Space Complexity: O(1)Using Sort on List
class Solution { public List<Integer> lexicalOrder(int n) { String[] strs = new String[n]; for(int i=1;i<=n;i++) strs[i-1] = Integer.toString(i); Arrays.sort(strs); List<Integer> op = new ArrayList<>(); for(String s: strs) op.add(Integer.parseInt(s)); return op; }}//Time Complexity: O(nlog(n))//Space Complexity: O(n)Using Stack
class Solution { public List<Integer> lexicalOrder(int n) { List<Integer> op = new ArrayList<>(); Stack<Integer> stack = new Stack<>(); for(int i=9;i>=1;i--) if(i<=n) stack.add(i); while(stack.size()!=0){ int cur = stack.pop(); op.add(cur); if(cur<n){ for(int i=9;i>=0;i--){ int next = cur*10+i; if(next<=n) stack.add(next); } } } return op; }}//Time Complexity: O(n)//Space Complexity: O(n)Rotate Function
ArrayMathDynamic ProgrammingInputs
Sub-problems
Edge Cases
Further Readings
Valid Square
MathGeometryInputs
class Solution { public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) { }}Sub-problems
✅ Calculating distance between two points. ✅ Calculating slop from two points.
Properties of a Square
✅ All four sides should be of equal length. d=√((x_2-x_1)²+(y_2-y_1)²) ✅ Four 90-degree angles should be of equal length.
Edge Cases
✅ If any of the points are the same, or the distance between any two points is zero, return false.
Solution
public class Solution { public double dist(int[] p1, int[] p2) { // We are not using the square root as that is going to be same for all the points. return (p2[1] - p1[1]) * (p2[1] - p1[1]) + (p2[0] - p1[0]) * (p2[0] - p1[0]); } public boolean check(int[] p1, int[] p2, int[] p3, int[] p4) { return dist(p1,p2) > 0 && dist(p1, p2) == dist(p2, p3) && dist(p2, p3) == dist(p3, p4) && dist(p3, p4) == dist(p4, p1) && dist(p1, p3) == dist(p2, p4); } public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) { return check(p1, p2, p3, p4) || check(p1, p3, p2, p4) || check(p1, p2, p4, p3); }}// Time complexity : O(1). A fixed number of comparisons are done.// Space complexity : O(1). No extra space required.Checkpoints
✅ Check if any two points' distance is greater than 0. ✅ Check if any two points' distance is equal to the distance between the other two points. ✅ If any of the above scenerio fails to meet, return false.