DSA Notes - Data Structures & Algorithms

Arrays

An array is a collection of elements stored at contiguous memory locations. It's the most fundamental data structure in programming.

What is an Array?

Arrays store multiple values of the same type in a single variable. Each element can be accessed using an index (starting from 0).

Java

// Declaration and Initialization
int[] arr = new int[5];           // Creates array of size 5
int[] arr2 = {1, 2, 3, 4, 5};     // Direct initialization

// Accessing elements
int first = arr2[0];              // Gets first element (1)
arr2[2] = 10;                     // Sets third element to 10

// Array length
int size = arr2.length;           // Returns 5

Time Complexity

Operation	Time Complexity	Notes
Access by index	`O(1)`	Direct memory access
Search (unsorted)	`O(n)`	Linear search
Search (sorted)	`O(log n)`	Binary search
Insert at end	`O(1)`	If space available
Insert at beginning	`O(n)`	Shift all elements
Delete	`O(n)`	Shift elements

Common Array Operations

1. Finding Maximum/Minimum

Java

public static int findMax(int[] arr) {
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}

// Time: O(n), Space: O(1)

2. Reversing an Array

Java

public static void reverse(int[] arr) {
    int left = 0, right = arr.length - 1;
    while (left < right) {
        // Swap elements
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
        left++;
        right--;
    }
}

// Time: O(n), Space: O(1)

3. Two Pointer Technique

Java

// Find pair with given sum in sorted array
public static int[] twoSum(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    
    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == target) {
            return new int[]{left, right};
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return new int[]{-1, -1}; // Not found
}

// Time: O(n), Space: O(1)

Pro Tip: The two-pointer technique is extremely useful for sorted arrays. It can solve many problems in O(n) time that would otherwise require O(n²).

Interview Problems

Kadane's Algorithm - Find maximum subarray sum
Dutch National Flag - Sort array of 0s, 1s, 2s
Sliding Window Maximum - Max in each window of size k
Merge Intervals - Merge overlapping intervals
Rotate Array - Rotate array by k positions

Strings

A string is a sequence of characters. In Java, strings are immutable objects.

String Basics

Java

// String creation
String s1 = "Hello";                    // String literal
String s2 = new String("Hello");        // Using constructor

// Common operations
int len = s1.length();                  // Length: 5
char c = s1.charAt(0);                  // First char: 'H'
String sub = s1.substring(1, 3);        // Substring: "el"
String lower = s1.toLowerCase();        // "hello"
String upper = s1.toUpperCase();        // "HELLO"

// String comparison
boolean equals = s1.equals(s2);         // true (content)
int compare = s1.compareTo(s2);         // 0 (lexicographic)

// StringBuilder for mutable strings
StringBuilder sb = new StringBuilder();
sb.append("Hello");
sb.append(" World");
String result = sb.toString();          // "Hello World"

Important: Never use == to compare strings in Java. Always use .equals() method. The == operator compares references, not content.

Common String Algorithms

1. Check Palindrome

Java

public static 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;
}

// Time: O(n), Space: O(1)

2. Check Anagram

Java

public static boolean isAnagram(String s1, String s2) {
    if (s1.length() != s2.length()) return false;
    
    int[] count = new int[26];
    
    for (int i = 0; i < s1.length(); i++) {
        count[s1.charAt(i) - 'a']++;
        count[s2.charAt(i) - 'a']--;
    }
    
    for (int c : count) {
        if (c != 0) return false;
    }
    return true;
}

// Time: O(n), Space: O(1) - fixed 26 chars

Interview Problems

Longest Palindromic Substring - Find longest palindrome
String Compression - Compress repeated characters
Valid Parentheses - Check balanced brackets
Longest Common Prefix - Find common prefix
KMP Pattern Matching - Efficient substring search

Linked Lists

A linked list is a linear data structure where elements are stored in nodes, and each node points to the next node.

Types of Linked Lists

Singly Linked List - Each node points to next node
Doubly Linked List - Each node points to next and previous
Circular Linked List - Last node points to first

Node Structure

Java

// Singly Linked List Node
class ListNode {
    int val;
    ListNode next;
    
    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

// Doubly Linked List Node
class DoublyNode {
    int val;
    DoublyNode prev;
    DoublyNode next;
    
    DoublyNode(int val) {
        this.val = val;
        this.prev = null;
        this.next = null;
    }
}

Common Operations

1. Reverse Linked List

Java

public ListNode reverse(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    
    while (curr != null) {
        ListNode next = curr.next;  // Save next
        curr.next = prev;           // Reverse link
        prev = curr;                // Move prev
        curr = next;                // Move curr
    }
    
    return prev;  // New head
}

// Time: O(n), Space: O(1)

2. Detect Cycle (Floyd's Algorithm)

Java

public boolean hasCycle(ListNode head) {
    if (head == null) return false;
    
    ListNode slow = head;
    ListNode fast = head;
    
    while (fast != null && fast.next != null) {
        slow = slow.next;         // Move 1 step
        fast = fast.next.next;    // Move 2 steps
        
        if (slow == fast) {
            return true;  // Cycle detected
        }
    }
    
    return false;
}

// Time: O(n), Space: O(1)

Pro Tip: Floyd's Tortoise and Hare algorithm is essential for linked list problems. The slow and fast pointer technique can also find the middle element, cycle start point, and more.

Time Complexity

Operation	Time Complexity
Access by index	`O(n)`
Insert at beginning	`O(1)`
Insert at end	`O(n)` or `O(1)` with tail pointer
Delete	`O(1)` if node given, else `O(n)`
Search	`O(n)`

Stacks & Queues

Stack (LIFO - Last In First Out)

A stack is a linear data structure that follows the LIFO principle. Think of a stack of plates.

Java

// Using Java Stack class
Stack<Integer> stack = new Stack<>();

stack.push(1);          // Add to top
stack.push(2);
stack.push(3);

int top = stack.peek(); // See top: 3
int pop = stack.pop();  // Remove top: 3

boolean empty = stack.isEmpty();  // false
int size = stack.size();          // 2

// Common use: Valid Parentheses
public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '{' || c == '[') {
            stack.push(c);
        } else {
            if (stack.isEmpty()) return false;
            char top = stack.pop();
            if ((c == ')' && top != '(') ||
                (c == '}' && top != '{') ||
                (c == ']' && top != '[')) {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

Queue (FIFO - First In First Out)

A queue is a linear data structure that follows the FIFO principle. Think of a line at a ticket counter.

Java

// Using LinkedList as Queue
Queue<Integer> queue = new LinkedList<>();

queue.offer(1);         // Add to back
queue.offer(2);
queue.offer(3);

int front = queue.peek();   // See front: 1
int poll = queue.poll();    // Remove front: 1

// Priority Queue (Min Heap)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(3);
minHeap.offer(1);
minHeap.offer(2);
int min = minHeap.poll();   // Returns 1 (smallest)

// Max Heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
maxHeap.offer(3);
maxHeap.offer(1);
maxHeap.offer(2);
int max = maxHeap.poll();   // Returns 3 (largest)

Interview Problems

Next Greater Element - Find next larger element for each
Min Stack - Stack with O(1) getMin()
Implement Queue using Stacks
Sliding Window Maximum - Using deque
LRU Cache - Using HashMap + Doubly Linked List

Trees

A tree is a hierarchical data structure consisting of nodes connected by edges. Each tree has a root node and child nodes.

Binary Tree Structure

Java

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

Tree Traversals

Java

// Inorder: Left -> Root -> Right (gives sorted order in BST)
public void inorder(TreeNode root) {
    if (root == null) return;
    inorder(root.left);
    System.out.print(root.val + " ");
    inorder(root.right);
}

// Preorder: Root -> Left -> Right
public void preorder(TreeNode root) {
    if (root == null) return;
    System.out.print(root.val + " ");
    preorder(root.left);
    preorder(root.right);
}

// Postorder: Left -> Right -> Root
public void postorder(TreeNode root) {
    if (root == null) return;
    postorder(root.left);
    postorder(root.right);
    System.out.print(root.val + " ");
}

// Level Order (BFS)
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> level = new ArrayList<>();
        
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        result.add(level);
    }
    return result;
}

Binary Search Tree (BST)

A BST is a binary tree where left child < parent < right child for all nodes.

Java

// Search in BST - O(log n) average, O(n) worst
public TreeNode search(TreeNode root, int target) {
    if (root == null || root.val == target) {
        return root;
    }
    if (target < root.val) {
        return search(root.left, target);
    }
    return search(root.right, target);
}

// Insert in BST
public TreeNode insert(TreeNode root, int val) {
    if (root == null) {
        return new TreeNode(val);
    }
    if (val < root.val) {
        root.left = insert(root.left, val);
    } else {
        root.right = insert(root.right, val);
    }
    return root;
}

Interview Problems

Maximum Depth of Binary Tree
Validate Binary Search Tree
Lowest Common Ancestor
Serialize and Deserialize Binary Tree
Binary Tree Maximum Path Sum

Graphs

A graph is a non-linear data structure consisting of vertices (nodes) and edges connecting them.

Graph Representation

Java

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

// Add edge (undirected)
public void addEdge(int u, int v) {
    graph.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
    graph.computeIfAbsent(v, k -> new ArrayList<>()).add(u);
}

// Adjacency Matrix
int[][] matrix = new int[n][n];
matrix[u][v] = 1;  // Edge from u to v
matrix[v][u] = 1;  // For undirected graph

BFS (Breadth-First Search)

Java

public void bfs(int start) {
    Set<Integer> visited = new HashSet<>();
    Queue<Integer> queue = new LinkedList<>();
    
    visited.add(start);
    queue.offer(start);
    
    while (!queue.isEmpty()) {
        int node = queue.poll();
        System.out.print(node + " ");
        
        for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                queue.offer(neighbor);
            }
        }
    }
}
// Time: O(V + E), Space: O(V)

DFS (Depth-First Search)

Java

Set<Integer> visited = new HashSet<>();

public void dfs(int node) {
    visited.add(node);
    System.out.print(node + " ");
    
    for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
        if (!visited.contains(neighbor)) {
            dfs(neighbor);
        }
    }
}
// Time: O(V + E), Space: O(V)

When to use BFS vs DFS:
• BFS: Shortest path in unweighted graph, level-order traversal
• DFS: Detect cycles, topological sort, find connected components

Interview Problems

Number of Islands
Clone Graph
Course Schedule (Topological Sort)
Word Ladder
Dijkstra's Shortest Path

Sorting Algorithms

Comparison of Sorting Algorithms

Algorithm	Best	Average	Worst	Space	Stable
Bubble Sort	`O(n)`	`O(n²)`	`O(n²)`	`O(1)`	Yes
Selection Sort	`O(n²)`	`O(n²)`	`O(n²)`	`O(1)`	No
Insertion Sort	`O(n)`	`O(n²)`	`O(n²)`	`O(1)`	Yes
Merge Sort	`O(n log n)`	`O(n log n)`	`O(n log n)`	`O(n)`	Yes
Quick Sort	`O(n log n)`	`O(n log n)`	`O(n²)`	`O(log n)`	No
Heap Sort	`O(n log n)`	`O(n log n)`	`O(n log n)`	`O(1)`	No

Quick Sort Implementation

Java

public 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);
    }
}

private 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, j);
        }
    }
    swap(arr, i + 1, high);
    return i + 1;
}

private void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

Merge Sort Implementation

Java

public 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);
    }
}

private void merge(int[] arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    
    int[] L = new int[n1];
    int[] R = new int[n2];
    
    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];
    
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
        }
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

Searching Algorithms

Binary Search

Binary search works on sorted arrays and has O(log n) time complexity.

Java

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

// Find first occurrence
public int findFirst(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    int result = -1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            result = mid;
            right = mid - 1;  // Continue searching left
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

// Find last occurrence
public int findLast(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    int result = -1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            result = mid;
            left = mid + 1;  // Continue searching right
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

Common Binary Search Mistakes:
1. Using (left + right) / 2 - can cause integer overflow
2. Using left < right instead of left <= right
3. Forgetting to move boundaries correctly

Recursion & Backtracking

Recursion is when a function calls itself to solve smaller subproblems.

Recursion Template

Java

public returnType recursiveFunction(parameters) {
    // 1. Base case - when to stop
    if (baseCondition) {
        return baseValue;
    }
    
    // 2. Recursive case - break problem into smaller subproblems
    // 3. Call function with smaller input
    return recursiveFunction(smallerInput);
}

// Example: Factorial
public int factorial(int n) {
    if (n <= 1) return 1;           // Base case
    return n * factorial(n - 1);     // Recursive case
}

// Example: Fibonacci
public int fibonacci(int n) {
    if (n <= 1) return n;            // Base case
    return fibonacci(n-1) + fibonacci(n-2);  // Recursive case
}

Backtracking

Backtracking is recursion with the ability to undo choices.

Java

// Generate all subsets
public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(nums, 0, new ArrayList<>(), result);
    return result;
}

private void backtrack(int[] nums, int start, 
                       List<Integer> current, 
                       List<List<Integer>> result) {
    result.add(new ArrayList<>(current));  // Add current subset
    
    for (int i = start; i < nums.length; i++) {
        current.add(nums[i]);               // Make choice
        backtrack(nums, i + 1, current, result);  // Explore
        current.remove(current.size() - 1); // Undo choice (backtrack)
    }
}

Dynamic Programming

Dynamic Programming (DP) is an optimization technique that solves complex problems by breaking them into overlapping subproblems.

When to Use DP?

Problem has optimal substructure - optimal solution uses optimal solutions to subproblems
Problem has overlapping subproblems - same subproblems are solved multiple times

DP Approaches

Top-Down (Memoization) - Start from main problem, solve subproblems recursively, cache results
Bottom-Up (Tabulation) - Start from base cases, build up to main problem

Classic DP Problems

1. Fibonacci with Memoization

Java

// Top-Down with Memoization
int[] memo = new int[n + 1];
Arrays.fill(memo, -1);

public int fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];  // Return cached result
    memo[n] = fib(n-1) + fib(n-2);      // Cache result
    return memo[n];
}

// Bottom-Up with Tabulation
public int fibBottomUp(int n) {
    if (n <= 1) return 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];
}

// Space Optimized O(1)
public int fibOptimized(int n) {
    if (n <= 1) return n;
    int prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

2. Longest Common Subsequence

Java

public int lcs(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    int[][] dp = new int[m + 1][n + 1];
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1.charAt(i-1) == s2.charAt(j-1)) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    return dp[m][n];
}
// Time: O(m*n), Space: O(m*n)

3. 0/1 Knapsack Problem

Java

public int knapsack(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    int[][] dp = new int[n + 1][capacity + 1];
    
    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= capacity; w++) {
            // Don't take item i
            dp[i][w] = dp[i-1][w];
            
            // Take item i (if it fits)
            if (weights[i-1] <= w) {
                dp[i][w] = Math.max(dp[i][w], 
                    values[i-1] + dp[i-1][w - weights[i-1]]);
            }
        }
    }
    return dp[n][capacity];
}

Interview Problems

Climbing Stairs - Ways to climb n stairs
Coin Change - Min coins to make amount
Longest Increasing Subsequence
Edit Distance - Min operations to convert string
House Robber - Max money without adjacent houses

Greedy Algorithms

Greedy algorithms make the locally optimal choice at each step, hoping to find the global optimum.

Greedy vs DP: Greedy makes one choice and moves on. DP considers all choices and picks the best. Greedy is faster but doesn't always work.

Classic Greedy Problems

1. Activity Selection

Java

public int maxActivities(int[] start, int[] end) {
    int n = start.length;
    // Assume sorted by end time
    
    int count = 1;
    int lastEnd = end[0];
    
    for (int i = 1; i < n; i++) {
        if (start[i] >= lastEnd) {
            count++;
            lastEnd = end[i];
        }
    }
    return count;
}

2. Fractional Knapsack

Java

public double fractionalKnapsack(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    double[][] items = new double[n][2];  // [value/weight ratio, weight]
    
    for (int i = 0; i < n; i++) {
        items[i][0] = (double) values[i] / weights[i];
        items[i][1] = weights[i];
    }
    
    // Sort by value/weight ratio (descending)
    Arrays.sort(items, (a, b) -> Double.compare(b[0], a[0]));
    
    double totalValue = 0;
    int remaining = capacity;
    
    for (double[] item : items) {
        if (remaining >= item[1]) {
            totalValue += item[0] * item[1];
            remaining -= item[1];
        } else {
            totalValue += item[0] * remaining;  // Take fraction
            break;
        }
    }
    return totalValue;
}

Interview Problems

Jump Game - Can reach the end?
Gas Station - Find starting point for circular trip
Meeting Rooms II - Min conference rooms needed
Task Scheduler - Min time to complete tasks
Partition Labels - Partition string into max parts