Data Structures &
Algorithms Complete Notes

// Example 1: O(1) - Constant
int getFirst(int[] arr) {
    return arr[0];  // Always 1 operation, regardless of array size
}

// Example 2: O(n) - Linear
void printAll(int[] arr) {
    for(int i = 0; i < arr.length; i++) {  // Loop runs n times
        System.out.println(arr[i]);
    }
}

// Example 3: O(n²) - Quadratic
void bubbleSort(int[] arr) {
    for(int i = 0; i < arr.length; i++) {          // Outer loop: n times
        for(int j = 0; j < arr.length-1; j++) { // Inner loop: n times
            // n × n = O(n²)
        }
    }
}

// O(1) space - only uses fixed variables
int sum(int[] arr) {
    int total = 0;  // Just 1 variable
    for(int x : arr) total += x;
    return total;
}

// O(n) space - creates new array
int[] duplicate(int[] arr) {
    int[] copy = new int[arr.length];  // New array of size n
    System.arraycopy(arr, 0, copy, 0, arr.length);
    return copy;
}

// 2D array declaration and access
int[][] matrix = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};

// Access element at row 1, column 2
int value = matrix[1][2];  // Returns 6

// Traverse 2D array
for(int i = 0; i < matrix.length; i++) {
    for(int j = 0; j < matrix[i].length; j++) {
        System.out.print(matrix[i][j] + " ");
    }
    System.out.println();
}

// Find if array is sorted
boolean isSorted(int[] arr) {
    for(int i = 0; i < arr.length - 1; i++) {
        if(arr[i] > arr[i+1]) return false;
    }
    return true;
}

// Reverse array using two pointers
void reverse(int[] arr) {
    int left = 0, right = arr.length - 1;
    while(left < right) {
        // Swap
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
        left++;
        right--;
    }
}

// Check if palindrome
boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;
    while(left < right) {
        if(s.charAt(left) != s.charAt(right)) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

// Reverse string
String reverse(String s) {
    char[] chars = s.toCharArray();
    int left = 0, right = chars.length - 1;
    while(left < right) {
        char temp = chars[left];
        chars[left] = chars[right];
        chars[right] = temp;
        left++;
        right--;
    }
    return new String(chars);
}

// Node structure
class Node {
    int data;
    Node next;
    
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

// Simple linked list
class LinkedList {
    Node head;
    
    // Insert at beginning - O(1)
    void insertFirst(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }
}

// Display all elements
void display() {
    Node current = head;
    while(current != null) {
        System.out.print(current.data + " → ");
        current = current.next;
    }
    System.out.println("null");
}

// Doubly linked list node
class DNode {
    int data;
    DNode next, prev;
    
    DNode(int data) {
        this.data = data;
        this.next = this.prev = null;
    }
}

// Stack implementation
class Stack {
    private int[] items;
    private int top = -1;
    
    Stack(int capacity) {
        items = new int[capacity];
    }
    
    void push(int value) {
        items[++top] = value;
    }
    
    int pop() {
        return items[top--];
    }
    
    int peek() {
        return items[top];
    }
    
    boolean isEmpty() {
        return top == -1;
    }
}

// Check balanced parentheses using stack
boolean isBalanced(String s) {
    Stack<Character> st = new Stack<>();
    
    for(char c : s.toCharArray()) {
        if(c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else if(c == ')' || c == ']' || c == '}') {
            if(st.isEmpty()) return false;
            st.pop();
        }
    }
    
    return st.isEmpty();
}

       A (root)
      /|\
     B C D
    /|   |
   E F   G

Terminology:
- Root: Top node (A)
- Parent: Node with children (A is parent of B, C, D)
- Children: Nodes under a parent (B, C are children of A)
- Leaf: Node with no children (E, F, G)
- Subtree: Tree below any node
- Height: Distance from node to deepest leaf
- Depth: Distance from root to node

// Binary tree node
class TreeNode {
    int data;
    TreeNode left, right;
    
    TreeNode(int data) {
        this.data = data;
    }
}

// Inorder traversal (recursive)
void inorder(TreeNode root) {
    if(root == null) return;
    inorder(root.left);
    System.out.print(root.data + " ");
    inorder(root.right);
}

// Level order traversal (using queue for BFS)
void levelOrder(TreeNode root) {
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);
    
    while(!q.isEmpty()) {
        TreeNode node = q.poll();
        System.out.print(node.data + " ");
        
        if(node.left != null) q.add(node.left);
        if(node.right != null) q.add(node.right);
    }
}

// BST Search
TreeNode search(TreeNode root, int key) {
    if(root == null) return null;
    
    if(key == root.data) return root;
    else if(key < root.data) return search(root.left, key);
    else return search(root.right, key);
}

// BST Insert
TreeNode insert(TreeNode root, int value) {
    if(root == null) return new TreeNode(value);
    
    if(value < root.data) {
        root.left = insert(root.left, value);
    } else if(value > root.data) {
        root.right = insert(root.right, value);
    }
    
    return root;
}

// Min Heap using array
class MinHeap {
    private int[] heap;
    private int size = 0;
    
    // Parent: (i-1)/2, Left: 2i+1, Right: 2i+2
    
    void insert(int value) {
        heap[size] = value;
        bubbleUp(size);
        size++;
    }
    
    void bubbleUp(int index) {
        while(index > 0) {
            int parent = (index - 1) / 2;
            if(heap[index] < heap[parent]) {
                // Swap
                int temp = heap[index];
                heap[index] = heap[parent];
                heap[parent] = temp;
                index = parent;
            } else break;
        }
    }
}

// Types of Graphs:
1. Directed (Digraph): A→B (one direction)
2. Undirected: A—B (both directions)
3. Weighted: Edge has a value/cost
4. Unweighted: All edges equal

// Density:
- Sparse: Few edges (n ~ m, where m is edges)
- Dense: Many edges (m ~ n²)

// Adjacency List representation
Map<Integer, List<Integer>> graph = new HashMap<>();

// Add edge from u to v
void addEdge(int u, int v) {
    graph.putIfAbsent(u, new ArrayList<>());
    graph.get(u).add(v);
}

// BFS Traversal
void bfs(int start) {
    Queue<Integer> q = new LinkedList<>();
    Set<Integer> visited = new HashSet<>();
    
    q.add(start);
    visited.add(start);
    
    while(!q.isEmpty()) {
        int node = q.poll();
        System.out.print(node + " ");
        
        for(int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
            if(!visited.contains(neighbor)) {
                visited.add(neighbor);
                q.add(neighbor);
            }
        }
    }
}

// DFS Traversal (Recursive)
void dfs(int node, Set<Integer> visited) {
    visited.add(node);
    System.out.print(node + " ");
    
    for(int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
        if(!visited.contains(neighbor)) {
            dfs(neighbor, visited);
        }
    }
}

// Bubble Sort
void bubbleSort(int[] arr) {
    int n = arr.length;
    
    for(int i = 0; i < n - 1; i++) {
        // Last i elements are already sorted
        for(int j = 0; j < n - i - 1; j++) {
            if(arr[j] > arr[j + 1]) {
                // Swap
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

// Quick Sort
void quickSort(int[] arr, int low, int high) {
    if(low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int partition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    
    for(int j = low; j < high; j++) {
        if(arr[j] < pivot) {
            i++;
            // Swap arr[i] and arr[j]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    
    // Swap arr[i+1] and arr[high]
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    
    return i + 1;
}

// Merge Sort
void mergeSort(int[] arr, int left, int right) {
    if(left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

// Linear Search
int linearSearch(int[] arr, int target) {
    for(int i = 0; i < arr.length; i++) {
        if(arr[i] == target) {
            return i;
        }
    }
    return -1;  // Not found
}

// Binary Search (Iterative)
int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    
    while(left <= right) {
        int mid = left + (right - left) / 2;
        
        if(arr[mid] == target) {
            return mid;
        } else if(arr[mid] < target) {
            left = mid + 1;  // Search right half
        } else {
            right = mid - 1;  // Search left half
        }
    }
    
    return -1;  // Not found
}

// Binary Search (Recursive)
int binarySearchRec(int[] arr, int target, int left, int right) {
    if(left > right) return -1;
    
    int mid = left + (right - left) / 2;
    
    if(arr[mid] == target) return mid;
    else if(arr[mid] < target) return binarySearchRec(arr, target, mid + 1, right);
    else return binarySearchRec(arr, target, left, mid - 1);
}

// Naive Recursion – EXPONENTIAL O(2ⁿ) – VERY SLOW
int fib(int n) {
    if(n <= 1) return n;
    return fib(n-1) + fib(n-2);  // Recomputes same values!
}

// DP with Memoization – O(n) – MUCH FASTER
int fib(int n, int[] memo) {
    if(n <= 1) return n;
    if(memo[n] != 0) return memo[n];  // Return cached result
    
    memo[n] = fib(n-1, memo) + fib(n-2, memo);
    return memo[n];
}

// DP with Tabulation (bottom-up) – O(n) – BEST
int fib(int n) {
    int[] dp = new int[n+1];
    dp[0] = 0; dp[1] = 1;
    
    for(int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    
    return dp[n];
}

// 0/1 Knapsack using DP
int knapsack(int[] weights, int[] values, int W) {
    int n = weights.length;
    int[][] dp = new int[n+1][W+1];
    
    // dp[i][w] = max value with first i items and capacity w
    
    for(int i = 1; i <= n; i++) {
        for(int w = 1; w <= W; w++) {
            if(weights[i-1] <= w) {
                // Include or exclude item
                dp[i][w] = Math.max(
                    values[i-1] + dp[i-1][w-weights[i-1]],  // Include
                    dp[i-1][w]                               // Exclude
                );
            } else {
                dp[i][w] = dp[i-1][w];  // Can't include
            }
        }
    }
    
    return dp[n][W];
}

// Activity Selection – Greedy approach
void activitySelection(List<Activity> activities) {
    // Sort by finish time
    activities.sort((a, b) -> a.finish - b.finish);
    
    List<Activity> selected = new ArrayList<>();
    selected.add(activities.get(0));
    int lastFinish = activities.get(0).finish;
    
    for(int i = 1; i < activities.size(); i++) {
        if(activities.get(i).start >= lastFinish) {
            selected.add(activities.get(i));
            lastFinish = activities.get(i).finish;
        }
    }
    
    System.out.println("Selected " + selected.size() + " activities");
}

// Greedy approach: Take items by value/weight ratio
double knapsack(int[] values, int[] weights, int W) {
    // Sort by value/weight ratio in descending order
    // Take items greedily until capacity full
}
Time Complexity: O(n log n) due to sorting