dsa topics | My Portfolio

This is a comprehensive, topic-by-topic breakdown of the Data Structures and Algorithms (DSA) concepts required for SDE interviews (from startups to FAANG).

The list is organized by Data Structure, followed by the specific Algorithmic Patterns you need to master for that structure.

1. Arrays & Strings

Most interview questions (approx. 40%) start here. Mastery of indices and pointers is key.

Pattern / Technique	Description	Common Problems
Two Pointers	Using two pointers (start/end or same direction) to compare values.	Pair with Target Sum, Move Zeroes, Container With Most Water, Trapping Rain Water.
Sliding Window	Expanding/shrinking a window to satisfy a condition (usually for subarrays/substrings).	Longest Substring Without Repeating Characters, Minimum Window Substring, Max Sum Subarray of Size K.
Prefix Sum	Pre-calculating sums to answer range queries in $O(1)$.	Range Sum Query, Subarray Sum Equals K, Product of Array Except Self.
Cyclic Sort	Used when input array contains numbers in range `1 to N`.	Find Missing Number, Find All Duplicates in an Array.
Kadane’s Algorithm	Optimized technique for Maximum Subarray Sum.	Maximum Subarray Sum, Maximum Sum Circular Subarray.

2. Linked Lists

Focuses on pointer manipulation without using extra space.

Pattern / Technique	Description	Common Problems
Fast & Slow Pointers	Moving two pointers at different speeds (usually 1x and 2x) to detect cycles or find midpoints.	Linked List Cycle (Floyd’s Cycle Finding), Middle of the Linked List, Happy Number.
In-place Reversal	Reversing links strictly $O(1)$ space.	Reverse a Linked List, Reverse Linked List II (sub-list), Reverse Nodes in k-Group.
Merge Technique	Merging two sorted lists.	Merge Two Sorted Lists, Sort List (Merge Sort implementation).

3. Stacks & Queues

Essential for processing nested structures and order-dependent problems.

Pattern / Technique	Description	Common Problems
Monotonic Stack	Keeping the stack sorted (increasing/decreasing) to find the "next greater/smaller" element efficiently.	Next Greater Element, Daily Temperatures, Largest Rectangle in Histogram.
Parentheses Matching	Using a stack to validate nested structures.	Valid Parentheses, Minimum Remove to Make Valid Parentheses.
Queue via Stacks	Implementing Queue using Stacks and vice versa.	Implement Queue using Stacks.

4. Hashing (HashMaps & Sets)

The "Swiss Army Knife" of interviews. Used to reduce time complexity from $O(N^2)$ to $O(N)$.

Pattern / Technique	Description	Common Problems
Frequency Map	Counting occurrences of elements.	Top K Frequent Elements (with Heap), Valid Anagram, Group Anagrams.
Lookup / Caching	Storing seen elements for quick access.	Two Sum, Longest Consecutive Sequence.

5. Trees (Binary Trees & BST)

Requires strong recursion skills.

Pattern / Technique	Description	Common Problems
DFS (Pre/In/Post)	Depth-First Search for path finding or validating properties.	Path Sum, Validate BST, Lowest Common Ancestor (LCA), Diameter of Binary Tree.
BFS (Level Order)	Breadth-First Search using a Queue.	Binary Tree Level Order Traversal, Binary Tree Right Side View, Zigzag Level Order Traversal.
Morris Traversal	Advanced: Traversing tree with $O(1)$ space (no recursion stack).	Recover Binary Search Tree (Optimization).

6. Heaps (Priority Queue)

Used whenever you need the "Min/Max" or "Top K" elements.

Pattern / Technique	Description	Common Problems
Top K Elements	keeping a heap of size K to find top elements.	Kth Largest Element in an Array, Top K Frequent Words.
Two Heaps	Maintaining a Min-Heap and Max-Heap simultaneously (often for Median).	Find Median from Data Stream, Sliding Window Median.
K-Way Merge	Merging multiple sorted lists using a Min-Heap.	Merge K Sorted Lists, Kth Smallest Element in a Sorted Matrix.

7. Graphs

The most intimidating but systematic topic. Focus on "Traversals".

Pattern / Technique	Description	Common Problems
Island Pattern (Matrix DFS/BFS)	Traversing a grid to find connected components.	Number of Islands, Max Area of Island, Rotting Oranges.
Union Find (Disjoint Set)	efficiently grouping elements and detecting cycles in undirected graphs.	Number of Provinces, Redundant Connection, Graph Valid Tree.
Topological Sort	Linear ordering of vertices (dependencies). Uses Indegree + Queue.	Course Schedule I & II, Alien Dictionary.
Dijkstra’s Algorithm	Shortest path in weighted graphs.	Network Delay Time, Cheapest Flights Within K Stops.

8. Advanced Data Structures

Differentiators for Senior / FAANG roles.

Pattern / Technique	Description	Common Problems
Trie (Prefix Tree)	Efficient string search and prefix matching.	Implement Trie, Word Search II.
Segment Tree / BIT	Range queries with updates.	Range Sum Query - Mutable.

9. Dynamic Programming (DP)

Optimization problems dealing with "Max/Min/Ways to do X".

Pattern / Technique	Description	Common Problems
0/1 Knapsack	Decision making: Include item or not.	Partition Equal Subset Sum, Target Sum.
Unbounded Knapsack	Include item multiple times.	Coin Change, Coin Change II, Rod Cutting.
Longest Common Subsequence	String comparison logic.	LCS, Edit Distance, Longest Palindromic Subsequence.
Palindromic DP	Expanding from center or checking substrings.	Longest Palindromic Substring, Palindrome Partitioning.

10. Other Essential Patterns

Binary Search: Not just for finding numbers, but for Search Space Reduction (e.g., Koko Eating Bananas, Capacity To Ship Packages Within D Days).
Merge Intervals: Handling overlapping time ranges (e.g., Merge Intervals, Insert Interval, Meeting Rooms II).
Bit Manipulation: XOR tricks (e.g., Single Number, Sum of Two Integers).
Backtracking: Brute force for combinations/permutations (e.g., Subsets, Permutations, N-Queens).