Click here go to DSA 📚 Books 📚
In-order, Pre-order, and Post-order traversals are Depth-First traversals. For a Graph, the complexity of a Depth First Traversal is O(n + m), where n is the number of nodes, and m is the number of edges. Since a Binary Tree is also a Graph, the same applies here. The complexity of each of these Depth-first traversals is O(n+m). Since the number of edges that can originate from a node is limited to 2 in the case of a Binary Tree, the maximum number of total edges in a Binary Tree is n-1, where n is the total number of nodes. The complexity then becomes O(n + n-1), which is O(n).
For anyone who is getting confused with Top-down and bottom-up, Recursion memoization is always TOP-DOWN(and not bottom-up), as we take a bigger problem and recursively solve for the smaller subproblems. Whereas in tabular DP where we start filling the table from top left to bottom right is actually BOTTOM-UP because we compute dp values of smaller subproblems first and then using these values compute dp values of bigger problems.
Recursion + memoization is called Top-Down DP and Tabulation method is called Bottom-Up DP.
PS: Top-down and Bottom up is decided by the essence of methodology and not by whether we are filling table from top to bottom or vice versa!
for (int[] row : matrix)
System.out.println(Arrays.toString(row));
StringBuilder reverseStr = new StringBuilder();
reverseStr.append(str).reverse();
int[][] matrix = new int[len][len];
for (int[] row : matrix)
Arrays.fill(row, -1);
char[] ch = str.toCharArray();
If you are working with the Character class and want to compare two char values, then use equals() method
with primitive char values, you can simply use the == equal operator
If given key is exist in the map then it will return corresponding value otherwise it return the default given value by us here it's 500
//(key, defaultValue)
map.getOrDefault(200, 500) + 1
map.put(str.charAt(j), map.getOrDefault(str.charAt(j), 1) + 1)
In many permutations/subset generation problems question demand for unique and sorted elements in it, so for that we can use TreeSet which follow both of these properties. On the other hand, Hashset only handle unique but can't handle ordering whereas TreeSet can handle ordering of elements.
TreeSet<String> set = new TreeSet<String>();
new ArrayList<String>(set)
sb.setLength(sb.length() - 1);
List<Integer> subList = Arrays.stream(edges[i]).boxed().collect(Collectors.toList());
int[][] sorted = intervals.clone();
Arrays.sort(sorted, (a,b) -> Integer.compare(a[0], b[0]));
int[][] arr = new int[list.size()][];
return list.toArray(arr);
In Java || is a short-circuit operator, the right hand side will not be evaluated if the left hand side is true
map.entrySet().forEach(entry -> {
System.out.println(entry.getKey() + " " + entry.getValue());
});
ArrayList<Integer>[] adj = new ArrayList[numCourses];