Leetcode problems - Java DS & Algos

gistfile1.md

Data Structures

Array

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'
}

Queue

Used for BFS.

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