Leetcode problems - Java DS & Algos

java ds cheatsheet.md

Data Structures

Array

We can use 26 length array for storing frequency of elements for problems with only lowercase english alphabet input.

int[]freq = new int[26];

Stack

When recursion is banned you can use stack to simulate. DFS iterative

Stack<T> st = new Stack<>(); // T is ususally Character, Integer. We can create class and use it.
st.peek(); // What is the top element? without removing
st.pop(); // returns T typed element from the top
st.push(el); // add element
st.isEmpty();

Monotonic stack

• Elements in the stack are either increasing/decreasing from bottom to top.
• Sometimes we store the indexes so elements correspond to indexes are mono-sequence(increasing/decreasing).
• Before pushing we check the elements whether they are smaller(for decreasing stack) and if they are smaller we remove them and push.

for(int i=0;i<num.length;i++) {
  while(!st.isEmpty() && st.peek() > num[i]) { // increasing from bottom to top
    st.pop();
  }
  st.push(num[i]); // can be just 'i'
}

Note: when the result wants indexes we should st.push(i) and check becomes
while(!st.isEmpty() && nums[st.peek()] > nums[i])

Queue

Used for BFS.

Queue<T> q = new LinkedList<>();
q.offer(); // add to the last
q.poll(); // remove from front
q.isEmpty();