Data Structures

1. Arrays

int[] arr = new int[10];
arr[1] = 34;
arr[1] = 35;

int i = arr[1];
int size = arr.length;

// Fill array with a value
Arrays.fill(arr, -1);

// Sort
Arrays.sort(arr); // Ascending
Arrays.sort(arr, (a, b) -> b - a); // Descending

// Create array using a range. Useful for printing array index
int[] range = IntStream.range(0, 10).toArray();

2. Character

char c1 = 'a';
char[] arr = "test".toCharArray();
char c2 = str.charAt(2);

// Character
Character.toLowerCase(c)
Character.isLowerCase(c);

Character.toUpperCase(c)
Character.isUpperCase(c);

Character.isLetter(c)
Character.isDigit(c)
Character.isAlphabetic(c);
Character.isLetterOrDigit(c)

3. String & StringBuilder

// String
String str = new String();
str = "abc";
int size = str.length();
char[] arr = str.toCharArray();
String sub = str.substring(1, 3); //[a, b)
str.toLowerCase();
str.toUpperCase();
str.replaceAll("a", "z");

// String Builder
StringBuilder sb = new StringBuilder();
sb.append("hellohowareyou?"); // Returns StringBuilder
sb.insert(2, "z");            // Returns StringBuilder
sb.delete(1, 3)               // [from, to) | Returns StringBuilder
sb.deleteCharAt(0);           // Returns StringBuilder
sb.reverse();                 // Returns StringBuilder

sb.substring(1);              // Returns String
sb.substring(3, 5);           // [from, to) | Returns String

4. List & ArrayList

List<Integer> list = new ArrayList<>();
list.add(5);
list.addAll(List.of(6, 7, 8, 9, 10));

// Index based
list.remove(3);
list.set(0, 9);
list.get(0);

int size = list.size();
list.clear();
list.isEmpty();

// Inefficient - O(n)
list.contains(77);
list.indexOf(10);

Integer[] arr = list.toArray(new Integer[0]);
int[] arrPrimitive = list.stream().mapToInt(Integer::intValue).toArray();

// Sort O(nlog(n))
Collections.sort(list);
Collections.sort(list, (a, b) -> b - a);
Collections.sort(personList, (p1, p2) -> p2.age - p1.age);

5. Stack

Stack<Integer> st = new Stack<>();
st.push(1);
st.pop();

st.peek();

6. Queue & Deque

// -----------------Queue-----------------
Queue<Integer> q = new LinkedList<>();
q.add(1);
q.remove();
q.peek();


// Without exception
q.offer(2);
q.poll()

// -----------------Deque-----------------

Deque<Integer> dq = new LinkedList<>();
dq.addFirst(1);
dq.addLast(2);

int f1 = dq.getFirst();
int l1 = dq.getLast();

int f2 = dq.removeFirst();
int l2 = dq.removeLast();

7. PriorityQueue

// Basics
PriorityQueue<Integer> pq = new PriorityQueue<>();
PriorityQueue<Integer> maxPQ = new PriorityQueue<>(Comparator.reverseOrder());

// Add/Offer
pq.add(5);

// Remove/Poll
Integer item = pq.remove();

// Return without removing
Integer item = pq.peek();

// -----------------Inefficient-----------------
// Contains
boolean exists = pq.contains(5);

// Remove specific object
pq.remove(5);

//--------------Custom comparators--------------------

// Max heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

// Based on string length
PriorityQueue<String> strPQByLength = new PriorityQueue<>((s1, s2) -> s2.length() - s1.length());

// Lexicographical Order
PriorityQueue<String> strPQLexi = new PriorityQueue<>();

// Reverse Lexicographical Order
PriorityQueue<String> strPQLexiDesc = new PriorityQueue<>(Comparator.reverseOrder());

// ----------------Custom Objects------------------

class Person {
    String name;
    int age;
    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
}

// Based on age in descending order
PriorityQueue<Person> personPQ = new PriorityQueue<>((p1, p2) -> p2.age - p1.age);

Formulas

Arrays

1d to 2d and 2d to 1d array

// Convert 1d array arr to 2d array of size mxn
int[][] matrix = new int[m][n];
for(int i=0; i<arr.length; i++) {
    int row = i/n;
    int col = i%n;
    matrix[row][col] = arr[i];
}

int[][] matrix = new int[m][n];
int idx = r*cols + cols;l.07

Concepts

Subarray, substring, subsequence and subsets