DSA Coding Cheatsheet for Java
You can keep it handy while solving problems. It will save you time from looking into syntax and help you to focus more on the aspect of problem-solving and algorithms.
Array
// Create an array of size n
int[] numbers = new int[n];
// Iterating using value
for (int num : numbers)
{
}
// Iterating using index
for (int i = 0; i < s.length(); i++){
char c = s.charAt(i);
}
// Get length of an array
int length = numbers.length
Arrays.sort(numbers) // Sort the array
Arrays.sort(nums, Collections.reverseOrder()) // For descending sort
Arrays.fill(arr, val) // Populate the array with given value
int min = Arrays.stream(nums).min().getAsInt(); // Find minimum
int[][] 2d_array = { // Declaring and initializing an 2-D array
{1, 3},
{2, 3},
};
// Sort the array by the first column
Arrays.sort(arr, (a, b) -> Integer.compare(a[0], b[0]));
Matrix
// To check whether indexes are within boundary or not
private boolean isSafe(int[][] grid, int r, int c)
{
return r >= 0 && r < grid.length && c >= 0 && c < grid[0].length;
}
private void DFS(int[][] grid, boolean[][] visited, int r, int c) {
int[] rowIdx = { -1,0,1,0};
int[] colIdx = { 0,-1,0,1};
visited[r][c] = true;
for(int i = 0; i < 4 ; ++i) {
int rN = r + rowIdx[i];
int cN = c + colIdx[i];
if(isSafe(grid, visited, rN, cN)) {
DFS(grid, visited, rN, cN);
}
}
}
ArrayList
ArrayList<Integer> numbers = new ArrayList<>();
numbers.add(10);
numbers.add(20);
for (Integer number : numbers) { // Using for-each loop
System.out.println(number);
}
for (int i = 0; i < numbers.size(); i++) { // Using regular for loop
System.out.println(numbers.get(i));
}
Character
char c = '7';
int value = Character.getNumericValue(c) // 7
// To convert int to char e.g. 7 -> '7'
(char)(7 + '0')
// Convert char to String e.g. '7' to "7"
Character.toString(c);
String
String
// Iterate over a string
String str = "Hello";
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
System.out.println(c);
}
String str = "Hello";
for (char c : str.toCharArray()) {
System.out.println(c);
}
str.charAt(i) // Get the character at index i
str.indexOf(char or String) // Get the index of given character or string
str.lastIndexOf(char or String) // Get the last index of given charater or string
str.length() // Length of the string
str.isEmpty() // Check if string is empty
str.trim() // Remove the leading and trailing whitespaces
str.toLowerCase() // Convert string to lower case
str.replaceAll()
// Get the substring from start index till end of string
str.substring(starting_index)
str.substring(1) // Output: "ello"
s.equals(String) // Compare content of two strings, return true if they are same, otherwise false
StringBuilder
StringBuilder s = new StringBuilder()
s.append() // Append the string
s.insert(0, "text") //Prepend
s.toString() // Convert to String object
s.reverse() // Reverse the content
s.equals(t) // Checking equality
Sorting
public class Interval {
int start, end;
Interval(int start, int end) {
this.start = start;
this.end = end;
}
}
// Sort list by start
intervals : List<Interval>
Collections.sort(intervals, Comparator.comparingInt(i -> i.start));
// Sort array by 0th element for each row
int[][] intervals = {
{3, 4},
{1, 2},
{5, 6},
};
Arrays.sort(intervals , Comparator.comparingInt(a -> a[0]));
List
List<T> list= new ArrayList<T>(); // Dynamic Array
List<T> list= new ArrayList(c); //Initialize with elements from collection c
List<T> list = Arrays.asList(arr);
List<List<Integer> output = new ArrayList();
output.add(new ArrayList<Integer>());
// Getting element from list using index
list.get(index);
// Removing an integer value from an ArrayList<Integer>
int i = 10;
list.remove(Integer.valueOf(i));
Stack
Stack<Integer> stack = new Stack<Integer>()
stack.push(15)
stack.pop()
stack.peek()
stack.isEmpty()
st.size()
// Iteration can be done in two ways
// 1. Pop elements until stack is empty
while(!stack.isEmpty())
{
int element = stack.pop();
}
// 2. Using iterator because Stack implements Collection interface
for(int num : stack)
{
}
Queue
LinkedList<T> q = new LinkedList<>();
q.add()
q.size()
q.isEmpty()
q.remove() - thrown exception when queue is empty.
q.peek()
q.poll() - returns null when queue is empty.
HashMap
HashMap<String, Integer> map = new HashMap<>()
// Add elements
map.put("Apple", 100);
map.put("Orange", 70);
map.put("Banana", 50);
// Getting the value
map.get("Apple");
// Check if key is present
map.containsKey("Apple");
// Update value for a key
map.replace("Apple", 101);
// Iterating the map using for-each loop
for (String key : hashMap.keySet()) {// Method 1
Integer value = hashMap.get(key);
}
for (HashMap.Entry<String, Integer> m : map.entrySet()) // Method 2
System.out.println("Key: " + m.getKey()
+ " Value: " + m.getValue());
Collection<Integer> prices = map.values(); // Iterating over values
for (String price : prices) {}
// Pre-initialized map
HashMap<Character, String> digitToLetterMap = new HashMap<>() {{
put('2', "abc");
put('3', "def");
put('4', "ghi");
put('5', "jkl");
put('6', "mno");
put('7', "pqrs");
put('8', "tuv");
put('9', "wxyz");
}};
TreeMap for sorted map.
floorKey() method in the TreeMap class is used to return the greatest key in the TreeMap that is less than or equal to the given key, or null if there is no such key.
Priority Queue
Queue<T> minHeap = new PriorityQueue<>();
Queue<T> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
add() // Add element to help
poll() // Remove the top element from heap
peek() // Just look the top element
Task: Maintain ordering of students by rank in ascending order and get the topper name
public class Student {
private String name;
private int rank;
public Student(String name, int rank)
{
this.name = name;
this.rank = rank;
}
public String getName()
{
return name;
}
public int getRank()
{
return rank;
}
}
var students = DataStore.getStudents();
var studentQueue = new PriorityQueue<Student>(Comparator.comparingInt(Student::getRank));
for(Student student : students)
{
studentQueue.add(student);
}
System.out.println("Topper name: " + studentQueue.peek().getName());
Task: If you want to maintain the ranks in reverse order
var studentQueue = new PriorityQueue<Student>(Comparator.comparingInt(Student::getRank).reversed());
Math
Math.min()
Math.sqrt() // Compute square root of a number
Integer.parseInt(String)
Integer.toString(Integer) // Convert an integer to string
Integer.MIN_VALUE
Integer.MAX_VALUE
// Largest power of 2 less than or equal to number
int res = (int) (Math.log(number) / Math.log(2)) // number: 42, res = 5
Graph
// Create a graph with n nodes => (0, 1, 2, ... n -1)
List<List> adj = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
adj.add(new ArrayList<>());
}
// Iterate over neighbors of a node i
for(int neighbor : adj.get(i)) {
}
// Store graph for testing
List<List<Integer>> adj = new ArrayList<>();
adj.add(Arrays.asList(1, 2, 3)); // Edges from node 0
adj.add(Arrays.asList(4, 5, 6)); // Edges from node 1
adj.add(Arrays.asList(1, 3)); // Edges from node 2
// Store graph traversal
ArrayList<Integer> res = new ArrayList<>();
// Track visited nodes
boolean visited[] = new boolean[V]
Streams
String[] arr = {"Apple", "Banana", "Kanana", "Cherry"};
String substring = "nana";
// Find last index of a string containing a substring
int lastIndex = IntStream.range(0, arr.length) // Create a int stream
.filter(i -> arr[i].contains(substring)) // Filter elements of stream
.reduce((f, s) -> s) // Reduce stream to a single element
.orElse(-1);
public static long countOccurrences(String str, char letter) {
return str.chars() // Convert the string to an IntStream of character codes
.filter(c -> c == letter) // Keep only characters equal to the specified letter
.count(); // Count the occurrences
}