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:
- 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.
- 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.
- 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.
- 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.
- maxSum = Math.max(maxSum, currentSum);: Update maxSum if the current subarray sum is larger.
- Why: Tracks the global maximum across all subarrays.
- 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:
- 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.
- ListNode current = head;: Start with the current node as the head of the input list.
- Why: We process each node sequentially.
- while (current != null): Loop until we reach the end of the list.
- Why: Ensures all nodes are reversed.
- ListNode next = current.next;: Store the next node before changing links.
- Why: Prevents losing the rest of the list.
- current.next = prev;: Reverse the link by pointing the current node’s next to the previous node.
- Why: Changes the direction of the list.
- prev = current;: Move prev to the current node.
- Why: Prepares prev for the next iteration.
- current = next;: Move current to the next node.
- Why: Advances to the next node to process.
- 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:
- if (root == null): Check if the current subtree is empty.
- Why: If empty, create a new node with the given value.
- return new TreeNode(val);: Return the new node as the root of the subtree.
- Why: Inserts the value at the correct position.
- if (val < root.val): Compare the value to insert with the current node’s value.
- Why: BST property: left subtree has smaller values.
- root.left = insertIntoBST(root.left, val);: Recursively insert into the left subtree.
- Why: Continues searching for the correct position.
- else: If val >= root.val, insert into the right subtree.
- Why: Right subtree has larger or equal values.
- root.right = insertIntoBST(root.right, val);: Recursively insert into the right subtree.
- Why: Maintains BST structure.
- 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:
- 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.
- for (int num : nums): Iterate through each element in the array.
- Why: Process all elements to find the k largest.
- minHeap.offer(num);: Add the current element to the heap.
- Why: Builds the heap incrementally.
- if (minHeap.size() > k): Check if the heap size exceeds k.
- Why: We only need the k largest elements.
- minHeap.poll();: Remove the smallest element if the heap is too large.
- Why: Ensures the heap contains the k largest elements.
- 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:
- List<List<Integer>> adjList = new ArrayList<>();: Create an adjacency list to represent the graph.
- Why: Efficiently stores neighbors for each node.
- for (int[] edge : graph): Convert edge list to adjacency list.
- Why: Edges are given as pairs [u, v].
- adjList.get(edge[0]).add(edge[1]);: Add edge from u to v and v to u (undirected).
- Why: Ensures bidirectional connectivity.
- Queue<Integer> queue = new LinkedList<>();: Initialize a queue for BFS.
- Why: BFS processes nodes level by level.
- queue.offer(start); visited[start] = true;: Start BFS from the start node, mark it visited.
- Why: Prevents revisiting nodes.
- while (!queue.isEmpty()): Process nodes until the queue is empty.
- Why: Explores all reachable nodes.
- if (node == end) return true;: Check if the current node is the target.
- Why: Path found if we reach the end node.
- for (int neighbor : adjList.get(node)): Explore all neighbors of the current node.
- Why: Continues BFS to unvisited neighbors.
- queue.offer(neighbor); visited[neighbor] = true;: Add unvisited neighbor to queue and mark visited.
- Why: Ensures each node is processed once.
- 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:
- HashMap<Character, Integer> charCount = new HashMap<>();: Create a hash map to store character frequencies.
- Why: Efficiently tracks how many times each character appears.
- for (char c : s.toCharArray()): Iterate through each character in the string.
- Why: Builds the frequency map.
- charCount.put(c, charCount.getOrDefault(c, 0) + 1);: Increment the count for the character.
- Why: getOrDefault handles first occurrences (returns 0 if absent).
- for (char c : s.toCharArray()): Iterate through the string again.
- Why: Finds the first character with a count of 1.
- if (charCount.get(c) == 1): Check if the character appears exactly once.
- Why: Identifies non-repeating characters.
- return c;: Return the first non-repeating character.
- Why: Meets the problem requirement.
- 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:
- if (low < high): Check if the subarray has more than one element.
- Why: Base case for recursion (single element is sorted).
- 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.
- quickSort(arr, low, pi - 1);: Recursively sort the left partition.
- Why: Elements left of pivot are smaller.
- quickSort(arr, pi + 1, high);: Recursively sort the right partition.
- Why: Elements right of pivot are larger.
- int pivot = arr[high];: Choose the last element as the pivot.
- Why: Simplifies partitioning (other pivot choices possible).
- for (int j = low; j < high; j++): Iterate through the subarray.
- Why: Places elements smaller than pivot to the left.
- if (arr[j] <= pivot): If current element is smaller or equal to pivot, swap it to the left side.
- Why: Builds the partition.
- int temp = arr[i + 1];: Swap the pivot to its final position.
- Why: Places pivot between smaller and larger elements.
- 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:
- int left = 0; int right = arr.length - 1;: Initialize pointers to the array’s start and end.
- Why: Defines the search range.
- while (left <= right): Continue searching while the range is valid.
- Why: Stops when the range collapses (left > right).
- int mid = left + (right - left) / 2;: Calculate the middle index.
- Why: Avoids integer overflow compared to (left + right) / 2.
- if (arr[mid] == target): Check if the middle element is the target.
- Why: If found, return its index.
- if (arr[mid] < target): If the middle element is too small, search the right half.
- Why: Target must be in the upper half.
- left = mid + 1;: Adjust the left pointer.
- Why: Excludes the middle element and lower half.
- else: If the middle element is too large, search the left half.
- Why: Target must be in the lower half.
- right = mid - 1;: Adjust the right pointer.
- Why: Excludes the middle element and upper half.
- 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:
- if (n < 0): Check for invalid input.
- Why: Factorial is undefined for negative numbers.
- throw new IllegalArgumentException(...);: Throw an exception for negative inputs.
- Why: Ensures robust error handling.
- if (n == 0 || n == 1): Base case: factorial of 0 or 1 is 1.
- Why: Stops recursion.
- return 1;: Return the base case result.
- Why: Defines the smallest problem solution.
- 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:
- if (n < 0): Check for invalid input.
- Why: Fibonacci is undefined for negative numbers.
- if (n <= 1): Base cases: F(0) = 0, F(1) = 1.
- Why: Defines the starting points.
- long[] dp = new long[n + 1];: Create an array to store Fibonacci numbers.
- Why: Stores intermediate results to avoid recalculation.
- dp[0] = 0; dp[1] = 1;: Initialize base cases.
- Why: Sets up the DP table.
- for (int i = 2; i <= n; i++): Iterate from 2 to n.
- Why: Computes each Fibonacci number.
- dp[i] = dp[i - 1] + dp[i - 2];: Compute F(i) = F(i-1) + F(i-2).
- Why: Fibonacci definition.
- 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