Saturday, May 3, 2025

DATA STRUCTURES AND ALGORITHMS

 1. Arrays

Question: Write a function to find the maximum sum of a contiguous subarray in an array of integers (Kadane’s Algorithm).

Answer:

public class MaxSubArraySum {
    public static int maxSubArray(int[] nums) {
        // Step 1: Initialize variables
        int maxSum = nums[0]; // Tracks maximum sum found
        int currentSum = nums[0]; // Tracks current subarray sum

        // Step 2: Iterate through array starting from second element
        for (int i = 1; i < nums.length; i++) {
            // Step 3: Decide to start new subarray or extend current
            currentSum = Math.max(nums[i], currentSum + nums[i]);
            // Step 4: Update maximum sum if current sum is larger
            maxSum = Math.max(maxSum, currentSum);
        }

        // Step 5: Return result
        return maxSum;
    }

    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println("Maximum Subarray Sum: " + maxSubArray(nums)); // Output: 6
    }
}
Step-by-Step Line Interpretation:
  1. int maxSum = nums[0];: Initialize maxSum to the first element, as it’s the minimum possible sum for an empty or single-element array.
    • Why: Ensures we have a valid starting point, even if all numbers are negative.
  2. int currentSum = nums[0];: Initialize currentSum to track the sum of the current subarray ending at the current index.
    • Why: Kadane’s algorithm builds subarrays incrementally.
  3. for (int i = 1; i < nums.length; i++): Loop from the second element (index 1) to the end of the array.
    • Why: We’ve initialized with the first element, so we process the rest.
  4. currentSum = Math.max(nums[i], currentSum + nums[i]);: At each index, decide whether to start a new subarray (take nums[i]) or extend the existing subarray (add nums[i] to currentSum).
    • Why: If adding the current element makes the sum smaller than the element itself, it’s better to start fresh.
  5. maxSum = Math.max(maxSum, currentSum);: Update maxSum if the current subarray sum is larger.
    • Why: Tracks the global maximum across all subarrays.
  6. return maxSum;: Return the maximum subarray sum found.
    • Why: Provides the final result.
Explanation:
  • Problem: Find the contiguous subarray with the largest sum (e.g., for [-2, 1, -3, 4, -1, 2, 1, -5, 4], the subarray [4, -1, 2, 1] gives sum 6).
  • Algorithm: Kadane’s Algorithm iterates through the array, maintaining a running sum (currentSum) and updating the global maximum (maxSum).
  • Complexity Analysis:
    • Time Complexity: O(n), where n is the array length (single pass through the array).
    • Space Complexity: O(1), as we only use two variables (maxSum, currentSum).
  • Practical Use: Common in financial data analysis (e.g., maximum profit from stock prices) and coding interviews (LeetCode #53).

2. Linked Lists
Question: Write a function to reverse a singly linked list.

Answer:

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class ReverseLinkedList {
    public static ListNode reverseList(ListNode head) {
        // Step 1: Initialize pointers
        ListNode prev = null;
        ListNode current = head;

        // Step 2: Iterate until end of list
        while (current != null) {
            // Step 3: Store next node
            ListNode next = current.next;
            // Step 4: Reverse link
            current.next = prev;
            // Step 5: Move pointers
            prev = current;
            current = next;
        }

        // Step 6: Return new head
        return prev;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        ListNode reversed = reverseList(head);
        while (reversed != null) {
            System.out.print(reversed.val + " "); // Output: 3 2 1
            reversed = reversed.next;
        }
    }
}
Step-by-Step Line Interpretation:

  1. ListNode prev = null;: Initialize prev to null, as the new tail’s next will be null.
    • Why: Tracks the previous node in the reversed list.
  2. ListNode current = head;: Start with the current node as the head of the input list.
    • Why: We process each node sequentially.
  3. while (current != null): Loop until we reach the end of the list.
    • Why: Ensures all nodes are reversed.
  4. ListNode next = current.next;: Store the next node before changing links.
    • Why: Prevents losing the rest of the list.
  5. current.next = prev;: Reverse the link by pointing the current node’s next to the previous node.
    • Why: Changes the direction of the list.
  6. prev = current;: Move prev to the current node.
    • Why: Prepares prev for the next iteration.
  7. current = next;: Move current to the next node.
    • Why: Advances to the next node to process.
  8. return prev;: Return prev, which is the new head of the reversed list.
    • Why: The last node processed becomes the head.
Explanation:
  • Problem: Reverse a linked list (e.g., 1->2->3 becomes 3->2->1).
  • Algorithm: Iteratively reverse pointers by adjusting next references, using three pointers (prev, current, next).
  • Complexity Analysis:
    • Time Complexity: O(n), where n is the number of nodes (single pass).
    • Space Complexity: O(1), as we only use three pointers.
  • Practical Use: Used in list manipulation problems (LeetCode #206) and applications like undo operations.

3. Trees (Binary Search Tree)
Question: Write a function to insert a value into a Binary Search Tree (BST) and return the updated root.
Answer:
java
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class BSTInsert {
    public static TreeNode insertIntoBST(TreeNode root, int val) {
        // Step 1: Base case - empty tree
        if (root == null) {
            return new TreeNode(val);
        }

        // Step 2: Recursive insertion
        if (val < root.val) {
            // Insert into left subtree
            root.left = insertIntoBST(root.left, val);
        } else {
            // Insert into right subtree
            root.right = insertIntoBST(root.right, val);
        }

        // Step 3: Return unchanged root
        return root;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(7);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        root = insertIntoBST(root, 5);
        // Inorder traversal to verify: 1, 2, 3, 4, 5, 7
        printInorder(root);
    }

    public static void printInorder(TreeNode root) {
        if (root != null) {
            printInorder(root.left);
            System.out.print(root.val + " ");
            printInorder(root.right);
        }
    }
}
Step-by-Step Line Interpretation:
  1. if (root == null): Check if the current subtree is empty.
    • Why: If empty, create a new node with the given value.
  2. return new TreeNode(val);: Return the new node as the root of the subtree.
    • Why: Inserts the value at the correct position.
  3. if (val < root.val): Compare the value to insert with the current node’s value.
    • Why: BST property: left subtree has smaller values.
  4. root.left = insertIntoBST(root.left, val);: Recursively insert into the left subtree.
    • Why: Continues searching for the correct position.
  5. else: If val >= root.val, insert into the right subtree.
    • Why: Right subtree has larger or equal values.
  6. root.right = insertIntoBST(root.right, val);: Recursively insert into the right subtree.
    • Why: Maintains BST structure.
  7. return root;: Return the current root, unchanged except for updated subtrees.
    • Why: Preserves the tree structure.
Explanation:
  • Problem: Insert a value into a BST while maintaining its properties (left < root <= right).
  • Algorithm: Recursively traverse the tree, inserting the new node at the appropriate leaf position.
  • Complexity Analysis:
    • Time Complexity: O(h), where h is the tree height (O(log n) for balanced BST, O(n) for skewed).
    • Space Complexity: O(h) due to recursive call stack.
  • Practical Use: Used in database indexing and search-efficient data structures (LeetCode #701).

4. Heaps
Question: Write a function to find the kth largest element in an array using a min-heap.
Answer:
java
import java.util.PriorityQueue;

public class KthLargestElement {
    public static int findKthLargest(int[] nums, int k) {
        // Step 1: Initialize min-heap
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        // Step 2: Process each element
        for (int num : nums) {
            // Step 3: Add element to heap
            minHeap.offer(num);
            // Step 4: Maintain heap size at k
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }

        // Step 5: Return kth largest
        return minHeap.peek();
    }

    public static void main(String[] args) {
        int[] nums = {3, 2, 1, 5, 6, 4};
        int k = 2;
        System.out.println("Kth Largest: " + findKthLargest(nums, k)); // Output: 5
    }
}
Step-by-Step Line Interpretation:
  1. PriorityQueue<Integer> minHeap = new PriorityQueue<>();: Create a min-heap to store the k largest elements.
    • Why: Min-heap keeps the smallest element at the root, easy to remove.
  2. for (int num : nums): Iterate through each element in the array.
    • Why: Process all elements to find the k largest.
  3. minHeap.offer(num);: Add the current element to the heap.
    • Why: Builds the heap incrementally.
  4. if (minHeap.size() > k): Check if the heap size exceeds k.
    • Why: We only need the k largest elements.
  5. minHeap.poll();: Remove the smallest element if the heap is too large.
    • Why: Ensures the heap contains the k largest elements.
  6. return minHeap.peek();: Return the root of the heap, which is the kth largest element.
    • Why: After processing, the smallest of the k largest elements is at the root.
Explanation:
  • Problem: Find the kth largest element in an array (e.g., for [3, 2, 1, 5, 6, 4], k=2, return 5).
  • Algorithm: Use a min-heap to maintain the k largest elements, removing the smallest when the heap size exceeds k.
  • Complexity Analysis:
    • Time Complexity: O(n log k), where n is array length (each insertion/removal is O(log k)).
    • Space Complexity: O(k) for the heap.
  • Practical Use: Common in streaming data or ranking problems (LeetCode #215).

5. Graphs
Question: Write a function to perform Breadth-First Search (BFS) on a graph to find if a path exists between two nodes.
Answer:
java
import java.util.*;

public class GraphBFS {
    public static boolean hasPath(int[][] graph, int start, int end) {
        // Step 1: Initialize adjacency list
        List<List<Integer>> adjList = new ArrayList<>();
        for (int i = 0; i < graph.length; i++) adjList.add(new ArrayList<>());
        for (int[] edge : graph) {
            adjList.get(edge[0]).add(edge[1]);
            adjList.get(edge[1]).add(edge[0]); // Undirected graph
        }

        // Step 2: Initialize BFS
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[graph.length];
        queue.offer(start);
        visited[start] = true;

        // Step 3: BFS traversal
        while (!queue.isEmpty()) {
            int node = queue.poll();
            if (node == end) return true; // Path found
            for (int neighbor : adjList.get(node)) {
                if (!visited[neighbor]) {
                    queue.offer(neighbor);
                    visited[neighbor] = true;
                }
            }
        }

        // Step 4: No path found
        return false;
    }

    public static void main(String[] args) {
        int[][] edges = {{0, 1}, {1, 2}, {2, 3}, {3, 4}};
        System.out.println("Has Path: " + hasPath(edges, 0, 4)); // Output: true
    }
}
Step-by-Step Line Interpretation:
  1. List<List<Integer>> adjList = new ArrayList<>();: Create an adjacency list to represent the graph.
    • Why: Efficiently stores neighbors for each node.
  2. for (int[] edge : graph): Convert edge list to adjacency list.
    • Why: Edges are given as pairs [u, v].
  3. adjList.get(edge[0]).add(edge[1]);: Add edge from u to v and v to u (undirected).
    • Why: Ensures bidirectional connectivity.
  4. Queue<Integer> queue = new LinkedList<>();: Initialize a queue for BFS.
    • Why: BFS processes nodes level by level.
  5. queue.offer(start); visited[start] = true;: Start BFS from the start node, mark it visited.
    • Why: Prevents revisiting nodes.
  6. while (!queue.isEmpty()): Process nodes until the queue is empty.
    • Why: Explores all reachable nodes.
  7. if (node == end) return true;: Check if the current node is the target.
    • Why: Path found if we reach the end node.
  8. for (int neighbor : adjList.get(node)): Explore all neighbors of the current node.
    • Why: Continues BFS to unvisited neighbors.
  9. queue.offer(neighbor); visited[neighbor] = true;: Add unvisited neighbor to queue and mark visited.
    • Why: Ensures each node is processed once.
  10. return false;: Return false if no path is found.
    • Why: Exhausted all nodes without reaching the end.
Explanation:
  • Problem: Determine if a path exists between two nodes in an undirected graph.
  • Algorithm: BFS explores nodes level by level, using a queue and visited array to track progress.
  • Complexity Analysis:
    • Time Complexity: O(V + E), where V is vertices and E is edges (processes each node and edge once).
    • Space Complexity: O(V) for queue and visited array.
  • Practical Use: Used in network routing, social network analysis (LeetCode #1971).

6. Hash Tables
Question: Write a function to find the first non-repeating character in a string.
Answer:
java
import java.util.HashMap;

public class FirstNonRepeatingChar {
    public static char firstNonRepeatingChar(String s) {
        // Step 1: Initialize hash map
        HashMap<Character, Integer> charCount = new HashMap<>();

        // Step 2: Count character frequencies
        for (char c : s.toCharArray()) {
            charCount.put(c, charCount.getOrDefault(c, 0) + 1);
        }

        // Step 3: Find first character with count 1
        for (char c : s.toCharArray()) {
            if (charCount.get(c) == 1) {
                return c;
            }
        }

        // Step 4: No non-repeating character
        return '_';
    }

    public static void main(String[] args) {
        String s = "leetcode";
        System.out.println("First Non-Repeating Char: " + firstNonRepeatingChar(s)); // Output: l
    }
}
Step-by-Step Line Interpretation:
  1. HashMap<Character, Integer> charCount = new HashMap<>();: Create a hash map to store character frequencies.
    • Why: Efficiently tracks how many times each character appears.
  2. for (char c : s.toCharArray()): Iterate through each character in the string.
    • Why: Builds the frequency map.
  3. charCount.put(c, charCount.getOrDefault(c, 0) + 1);: Increment the count for the character.
    • Why: getOrDefault handles first occurrences (returns 0 if absent).
  4. for (char c : s.toCharArray()): Iterate through the string again.
    • Why: Finds the first character with a count of 1.
  5. if (charCount.get(c) == 1): Check if the character appears exactly once.
    • Why: Identifies non-repeating characters.
  6. return c;: Return the first non-repeating character.
    • Why: Meets the problem requirement.
  7. return '_';: Return a placeholder if no non-repeating character exists.
    • Why: Handles edge cases (e.g., all characters repeat).
Explanation:
  • Problem: Find the first character in a string that appears only once (e.g., "leetcode" → 'l').
  • Algorithm: Use a hash map to count character frequencies, then scan the string for the first character with count 1.
  • Complexity Analysis:
    • Time Complexity: O(n), where n is string length (two passes over the string).
    • Space Complexity: O(k), where k is the number of unique characters (≤26 for lowercase letters).
  • Practical Use: Used in text processing and pattern matching (LeetCode #387).

7. Sorting (Quick Sort)
Question: Implement Quick Sort to sort an array of integers.
Answer:
java
public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        // Step 1: Base case
        if (low < high) {
            // Step 2: Partition and get pivot index
            int pi = partition(arr, low, high);
            // Step 3: Recursively sort left and right partitions
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    public static int partition(int[] arr, int low, int high) {
        // Step 4: Choose pivot (last element)
        int pivot = arr[high];
        int i = low - 1; // Index of smaller element

        // Step 5: Partition array
        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                // Swap elements
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // Step 6: Place pivot in correct position
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        // Step 7: Return pivot index
        return i + 1;
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        quickSort(arr, 0, arr.length - 1);
        System.out.print("Sorted Array: ");
        for (int num : arr) {
            System.out.print(num + " "); // Output: 11 12 22 25 34 64 90
        }
    }
}
Step-by-Step Line Interpretation:
  1. if (low < high): Check if the subarray has more than one element.
    • Why: Base case for recursion (single element is sorted).
  2. int pi = partition(arr, low, high);: Partition the array and get the pivot’s final index.
    • Why: Divides the array into two parts around the pivot.
  3. quickSort(arr, low, pi - 1);: Recursively sort the left partition.
    • Why: Elements left of pivot are smaller.
  4. quickSort(arr, pi + 1, high);: Recursively sort the right partition.
    • Why: Elements right of pivot are larger.
  5. int pivot = arr[high];: Choose the last element as the pivot.
    • Why: Simplifies partitioning (other pivot choices possible).
  6. for (int j = low; j < high; j++): Iterate through the subarray.
    • Why: Places elements smaller than pivot to the left.
  7. if (arr[j] <= pivot): If current element is smaller or equal to pivot, swap it to the left side.
    • Why: Builds the partition.
  8. int temp = arr[i + 1];: Swap the pivot to its final position.
    • Why: Places pivot between smaller and larger elements.
  9. return i + 1;: Return the pivot’s index.
    • Why: Informs recursive calls of the partition point.
Explanation:
  • Problem: Sort an array using Quick Sort (e.g., [64, 34, 25, 12, 22, 11, 90][11, 12, 22, 25, 34, 64, 90]).
  • Algorithm: Quick Sort selects a pivot, partitions the array, and recursively sorts subarrays.
  • Complexity Analysis:
    • Time Complexity: O(n log n) average, O(n²) worst case (rare with good pivot).
    • Space Complexity: O(log n) for recursive call stack.
  • Practical Use: Widely used in general-purpose sorting (LeetCode #912).

8. Searching (Binary Search)
Question: Write a function to perform Binary Search on a sorted array to find a target value.
Answer:
java
public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        // Step 1: Initialize pointers
        int left = 0;
        int right = arr.length - 1;

        // Step 2: Search loop
        while (left <= right) {
            // Step 3: Calculate mid
            int mid = left + (right - left) / 2;
            // Step 4: Check target
            if (arr[mid] == target) {
                return mid;
            }
            // Step 5: Adjust search range
            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        // Step 6: Target not found
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 4, 10, 40};
        int target = 10;
        int result = binarySearch(arr, target);
        System.out.println("Target Index: " + result); // Output: 3
    }
}
Step-by-Step Line Interpretation:
  1. int left = 0; int right = arr.length - 1;: Initialize pointers to the array’s start and end.
    • Why: Defines the search range.
  2. while (left <= right): Continue searching while the range is valid.
    • Why: Stops when the range collapses (left > right).
  3. int mid = left + (right - left) / 2;: Calculate the middle index.
    • Why: Avoids integer overflow compared to (left + right) / 2.
  4. if (arr[mid] == target): Check if the middle element is the target.
    • Why: If found, return its index.
  5. if (arr[mid] < target): If the middle element is too small, search the right half.
    • Why: Target must be in the upper half.
  6. left = mid + 1;: Adjust the left pointer.
    • Why: Excludes the middle element and lower half.
  7. else: If the middle element is too large, search the left half.
    • Why: Target must be in the lower half.
  8. right = mid - 1;: Adjust the right pointer.
    • Why: Excludes the middle element and upper half.
  9. return -1;: Return -1 if the target is not found.
    • Why: Indicates the target doesn’t exist in the array.
Explanation:
  • Problem: Find the index of a target value in a sorted array (e.g., [2, 3, 4, 10, 40], target=10 → index 3).
  • Algorithm: Binary Search divides the search range in half repeatedly, leveraging the sorted property.
  • Complexity Analysis:
    • Time Complexity: O(log n), where n is array length (halves the search space each step).
    • Space Complexity: O(1) for iterative version.
  • Practical Use: Used in search engines and sorted data lookups (LeetCode #704).

9. Recursion
Question: Write a recursive function to calculate the factorial of a number.
Answer:
java
public class Factorial {
    public static long factorial(int n) {
        // Step 1: Base cases
        if (n < 0) {
            throw new IllegalArgumentException("Negative numbers not allowed");
        }
        if (n == 0 || n == 1) {
            return 1;
        }

        // Step 2: Recursive case
        return n * factorial(n - 1);
    }

    public static void main(String[] args) {
        int n = 5;
        System.out.println("Factorial of " + n + ": " + factorial(n)); // Output: 120
    }
}
Step-by-Step Line Interpretation:
  1. if (n < 0): Check for invalid input.
    • Why: Factorial is undefined for negative numbers.
  2. throw new IllegalArgumentException(...);: Throw an exception for negative inputs.
    • Why: Ensures robust error handling.
  3. if (n == 0 || n == 1): Base case: factorial of 0 or 1 is 1.
    • Why: Stops recursion.
  4. return 1;: Return the base case result.
    • Why: Defines the smallest problem solution.
  5. return n * factorial(n - 1);: Recursive case: n! = n × (n-1)!.
    • Why: Breaks the problem into a smaller subproblem.
Explanation:
  • Problem: Compute n! (e.g., 5! = 5 × 4 × 3 × 2 × 1 = 120).
  • Algorithm: Recursively multiply n by the factorial of n-1, with base cases for 0 and 1.
  • Complexity Analysis:
    • Time Complexity: O(n), due to n recursive calls.
    • Space Complexity: O(n), for the recursive call stack.
  • Practical Use: Basis for recursive algorithms in combinatorics and tree traversals.

10. Dynamic Programming
Question: Write a function to find the nth Fibonacci number using dynamic programming (bottom-up approach).

Answer:
java
public class Fibonacci {
    public static long fibonacci(int n) {
        // Step 1: Handle edge cases
        if (n < 0) {
            throw new IllegalArgumentException("Negative numbers not allowed");
        }
        if (n <= 1) {
            return n;
        }

        // Step 2: Initialize DP array
        long[] dp = new long[n + 1];
        dp[0] = 0;
        dp[1] = 1;

        // Step 3: Fill DP array
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        // Step 4: Return result
        return dp[n];
    }

    public static void main(String[] args) {
        int n = 10;
        System.out.println("Fibonacci " + n + ": " + fibonacci(n)); // Output: 55
    }
}
Step-by-Step Line Interpretation:
  1. if (n < 0): Check for invalid input.
    • Why: Fibonacci is undefined for negative numbers.
  2. if (n <= 1): Base cases: F(0) = 0, F(1) = 1.
    • Why: Defines the starting points.
  3. long[] dp = new long[n + 1];: Create an array to store Fibonacci numbers.
    • Why: Stores intermediate results to avoid recalculation.
  4. dp[0] = 0; dp[1] = 1;: Initialize base cases.
    • Why: Sets up the DP table.
  5. for (int i = 2; i <= n; i++): Iterate from 2 to n.
    • Why: Computes each Fibonacci number.
  6. dp[i] = dp[i - 1] + dp[i - 2];: Compute F(i) = F(i-1) + F(i-2).
    • Why: Fibonacci definition.
  7. return dp[n];: Return the nth Fibonacci number.
    • Why: Provides the final result.
Explanation:
  • Problem: Compute the nth Fibonacci number (e.g., F(10) = 55).
  • Algorithm: Use bottom-up DP to build Fibonacci numbers iteratively, storing results in an array.
  • Complexity Analysis:
    • Time Complexity: O(n), single loop from 2 to n.
    • Space Complexity: O(n) for the DP array (can be optimized to O(1) using two variables).
  • Practical Use: Used in optimization problems and recursive sequence calculations (LeetCode #509).

Summary of Topics Covered
  • Arrays: Kadane’s Algorithm for maximum subarray sum (O(n) time, O(1) space).
  • Linked Lists: Reverse a linked list (O(n) time, O(1) space).
  • Trees (BST): Insert into a BST (O(h) time, O(h) space).
  • Heaps: Kth largest element using min-heap (O(n log k) time, O(k) space).
  • Graphs: BFS for path existence (O(V + E) time, O(V) space).
  • Hash Tables: First non-repeating character (O(n) time, O(k) space).
  • Sorting (Quick Sort): Sort an array (O(n log n) average time, O(log n) space).
  • Searching (Binary Search): Find target in sorted array (O(log n) time, O(1) space).
  • Recursion: Factorial calculation (O(n) time, O(n) space).
  • Dynamic Programming: Fibonacci number (O(n) time, O(n) space).
  • Complexity Analysis: Each solution includes Big O notation for time and space, reinforcing analysis skills.
Practical Learning Path (20 Hours)
  • Hours Allocation:
    • Arrays: 2 hours (Kadane’s, two-pointer problems).
    • Linked Lists: 2 hours (reverse, cycle detection).
    • Trees (BST, Heaps): 3 hours (insert, traversal, heap operations).
    • Graphs: 3 hours (BFS, DFS).
    • Hash Tables: 2 hours (frequency counting, mapping).
    • Sorting & Searching: 3 hours (Quick Sort, Binary Search).
    • Recursion & DP: 3 hours (factorial, Fibonacci, knapsack).
    • Complexity Analysis: 2 hours (integrated with each topic).
  • Practice: Solve similar problems on LeetCode (e.g., #53, #206, #701, #215, #387, #912, #704, #509).

No comments:

Post a Comment