/dsa-patterns

DSA Study Plan

Week 1-2: Sliding Window

Theory

The sliding window technique is used to solve problems that involve subarrays or substrings. It involves moving a window of a fixed size or a dynamically sized window across the array or string to find a solution.

Problems

  1. Maximum Sum Subarray of Size K (Easy)
  2. Longest Substring Without Repeating Characters (Medium)
  3. Permutation in String (Medium)
  4. Longest Substring with At Most K Distinct Characters (Hard)
  5. Minimum Window Substring (Hard)
  6. Smallest Subarray with a Given Sum (Easy)
  7. Fruit Into Baskets (Medium)
  8. Sliding Window Maximum (Hard)
  9. Subarrays with K Different Integers (Hard)
  10. Replace the Substring for Balanced String (Medium)

Week 3-4: Two Pointers

Theory

The two-pointer technique involves using two pointers to traverse the array or list. It's particularly useful for problems that involve pairs or require searching for two elements in a sorted array.

Problems

  1. Two Sum II - Input Array is Sorted (Easy)
  2. Remove Duplicates from Sorted Array (Easy)
  3. Container With Most Water (Medium)
  4. 3Sum (Medium)
  5. Four Sum (Medium)
  6. Move Zeroes (Easy)
  7. Linked List Cycle II (Medium)
  8. Palindrome Linked List (Easy)
  9. Remove Nth Node From End of List (Medium)
  10. Trapping Rain Water (Hard)

Week 5: Fast and Slow Pointers

Theory

Fast and slow pointers (also known as the tortoise and hare algorithm) are used to detect cycles in data structures like linked lists or to find the middle element.

Problems

  1. Linked List Cycle (Easy)
  2. Middle of the Linked List (Easy)
  3. Find the Duplicate Number (Medium)
  4. Happy Number (Easy)
  5. Palindrome Linked List (Easy)
  6. Reorder List (Medium)
  7. Intersection of Two Linked Lists (Easy)
  8. Cycle Detection in Directed Graph (Hard)
  9. Cycle Detection in Undirected Graph (Medium)
  10. Split Linked List in Parts (Medium)

Week 6: Merge Intervals

Theory

Merge intervals technique is used to solve problems that involve overlapping intervals. The main idea is to sort the intervals and then merge overlapping intervals.

Problems

  1. Merge Intervals (Medium)
  2. Insert Interval (Medium)
  3. Interval List Intersections (Medium)
  4. Meeting Rooms (Easy)
  5. Meeting Rooms II (Medium)
  6. Minimum Interval to Include Each Query (Hard)
  7. Employee Free Time (Hard)
  8. Non-overlapping Intervals (Medium)
  9. Partition Labels (Medium)
  10. Car Pooling (Medium)

Week 7: Cyclic Sort

Theory

Cyclic sort is useful for problems where numbers are within a specific range and you need to sort them with minimal space and time complexity.

Problems

  1. Missing Number (Easy)
  2. Find All Numbers Disappeared in an Array (Easy)
  3. Find the Duplicate Number (Medium)
  4. Find All Duplicates in an Array (Medium)
  5. Set Mismatch (Easy)
  6. First Missing Positive (Hard)
  7. Kth Missing Positive Number (Easy)
  8. Find the Missing Number in a Sorted Array (Easy)
  9. Find the Error Number (Easy)
  10. Check Array Formation Through Concatenation (Easy)

Week 8: In-place Reversal of a Linked List

Theory

In-place reversal involves reversing portions of a linked list without using extra space.

Problems

  1. Reverse Linked List (Easy)
  2. Reverse Linked List II (Medium)
  3. Reverse Nodes in k-Group (Hard)
  4. Swap Nodes in Pairs (Medium)
  5. Rotate List (Medium)
  6. Reverse Substrings Between Each Pair of Parentheses (Medium)
  7. Reverse Even Length Groups (Medium)
  8. Palindrome Linked List (Easy)
  9. Split Linked List in Parts (Medium)
  10. Flatten a Multilevel Doubly Linked List (Medium)

Week 9: Tree Traversal

Theory

Tree traversal techniques include inorder, preorder, and postorder traversals, which are used to visit all nodes in a tree in a specific order.

Problems

  1. Binary Tree Inorder Traversal (Easy)
  2. Binary Tree Preorder Traversal (Easy)
  3. Binary Tree Postorder Traversal (Easy)
  4. Binary Tree Level Order Traversal (Medium)
  5. Binary Tree Zigzag Level Order Traversal (Medium)
  6. Vertical Order Traversal of a Binary Tree (Hard)
  7. Serialize and Deserialize Binary Tree (Hard)
  8. Construct Binary Tree from Preorder and Inorder Traversal (Medium)
  9. Binary Tree Maximum Path Sum (Hard)
  10. Lowest Common Ancestor of a Binary Tree (Medium)

Week 10: Graph Traversal

Theory

Graph traversal techniques such as Breadth-First Search (BFS) and Depth-First Search (DFS) are used to explore nodes and edges in a graph.

Problems

  1. Number of Islands (Medium)
  2. Clone Graph (Medium)
  3. Graph Valid Tree (Medium)
  4. Word Ladder (Hard)
  5. Course Schedule (Medium)
  6. Course Schedule II (Medium)
  7. Pacific Atlantic Water Flow (Medium)
  8. All Paths From Source to Target (Medium)
  9. Critical Connections in a Network (Hard)
  10. Find Eventual Safe States (Medium)

Week 11: Binary Search

Theory

Binary search is a divide-and-conquer algorithm used to find elements in a sorted array or to determine the position of an element.

Problems

  1. Binary Search (Easy)
  2. Search Insert Position (Easy)
  3. Find Minimum in Rotated Sorted Array (Medium)
  4. Find Peak Element (Medium)
  5. Search in Rotated Sorted Array (Medium)
  6. Time Based Key-Value Store (Medium)
  7. Median of Two Sorted Arrays (Hard)
  8. Koko Eating Bananas (Medium)
  9. Capacity To Ship Packages Within D Days (Medium)
  10. Find K Closest Elements (Medium)

Week 12: Greedy Algorithms

Theory

Greedy algorithms make locally optimal choices at each step with the hope of finding a global optimum.

Problems

  1. Activity Selection (N/A)
  2. Fractional Knapsack (N/A)
  3. Job Sequencing Problem (N/A)
  4. Candy (Hard)
  5. Jump Game II (Medium)
  6. Assign Cookies (Easy)
  7. Gas Station (Medium)
  8. Minimum Number of Arrows to Burst Balloons (Medium)
  9. Queue Reconstruction by Height (Medium)
  10. Reorganize String (Medium)

Week 13-14: Dynamic Programming (DP)

Theory

Dynamic Programming involves breaking down problems into overlapping subproblems and solving each subproblem only once.

Problems

  1. Fibonacci Number (Easy)
  2. Climbing Stairs (Easy)
  3. House Robber (Medium)
  4. House Robber II (Medium)
  5. Longest Increasing Subsequence (Medium)
  6. Coin Change (Medium)
  7. Partition Equal Subset Sum (Medium)
  8. Unique Paths (Medium)
  9. Longest Common Subsequence (Medium)
  10. Edit Distance (Hard)

Week 15: Backtracking

Theory

Backtracking involves exploring all potential solutions and backtracking once an invalid solution is found to try another path.

Problems

  1. N-Queens (Hard)
  2. Subsets (Medium)
  3. Permutations (Medium)
  4. Combination Sum (Medium)
  5. Word Search (Medium)
  6. Palindrome Partitioning (Medium)
  7. Letter Combinations of a Phone Number (Medium)
  8. Sudoku Solver (Hard)
  9. Generate Parentheses (Medium)
  10. Combination Sum II (Medium)

Week 16: Bit Manipulation

Theory

Bit manipulation involves using bitwise operations to solve problems efficiently by manipulating individual bits of numbers.

Problems

  1. Single Number (Easy)
  2. Number of 1 Bits (Easy)
  3. Counting Bits (Easy)
  4. Missing Number (Easy)
  5. Power of Two (Easy)
  6. Bitwise AND of Numbers Range (Medium)
  7. Binary Watch (Easy)
  8. Reverse Bits (Easy)
  9. Maximum XOR of Two Numbers in an Array (Medium)
  10. Sum of Two Integers (Medium)

Week 17: Mathematical Patterns

Theory

These problems leverage mathematical properties, formulas, and techniques to find solutions efficiently.

Problems

  1. Count Primes (Easy)
  2. Valid Perfect Square (Easy)
  3. Roman to Integer (Easy)
  4. Integer to Roman (Medium)
  5. Pascal's Triangle (Easy)
  6. Excel Sheet Column Number (Easy)
  7. Power of Three (Easy)
  8. Super Pow (Medium)
  9. Pow(x, n) (Medium)
  10. Kth Largest Element in an Array (Medium)

Week 18: Topological Sort

Theory

Topological sort is used to order vertices in a Directed Acyclic Graph (DAG).

Problems

  1. Course Schedule (Medium)
  2. Course Schedule II (Medium)
  3. Alien Dictionary (Hard)
  4. Minimum Height Trees (Medium)
  5. Longest Increasing Path in a Matrix (Hard)
  6. Sequence Reconstruction (Medium)
  7. Parallel Courses (Medium)
  8. Reconstruct Original Digits from English (Medium)
  9. Longest Consecutive Sequence (Medium)
  10. Checking Existence of Edge Length Limited Paths (Hard)

Week 19: Union-Find

Theory

Union-Find is a data structure that keeps track of a set of elements partitioned into disjoint (non-overlapping) subsets. It supports union and find operations.

Problems

  1. Number of Connected Components in an Undirected Graph (Medium)
  2. Redundant Connection (Medium)
  3. Graph Valid Tree (Medium)
  4. Accounts Merge (Medium)
  5. Most Stones Removed with Same Row or Column (Medium)
  6. Smallest String With Swaps (Medium)
  7. Find Redundant Connection II (Hard)
  8. Swim in Rising Water (Hard)
  9. Largest Component Size by Common Factor (Hard)
  10. Earliest Moment When Everyone Become Friends (Medium)

Week 20: Heap/Priority Queue

Theory

Heaps are a specialized tree-based data structure that satisfy the heap property. They are useful for problems that require frequent access to the smallest or largest elements.

Problems

  1. Kth Largest Element in a Stream (Easy)
  2. Top K Frequent Elements (Medium)
  3. Find Median from Data Stream (Hard)
  4. Merge k Sorted Lists (Hard)
  5. Task Scheduler (Medium)
  6. Sort Characters By Frequency (Medium)
  7. Reorganize String (Medium)
  8. Minimum Cost to Connect Sticks (Medium)
  9. Meeting Rooms II (Medium)
  10. Kth Smallest Element in a Sorted Matrix (Medium)