Scribd
Upload
7 views10 pages

DSA Patterns Basics

The document outlines fundamental data structure and algorithm patterns, including Sliding Window, Two Pointer Technique, and Prefix Sum, each with specific use cases. It also covers algorithms like Kadane’s for maximum subarray sums, Merge Intervals for scheduling, and methods for cycle detection using Fast and Slow Pointers. Additionally, it discusses Binary Search, Backtracking, Dynamic Programming, and Graph Traversal techniques such as BFS and DFS.

Uploaded by

Tanvi Shah
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
7 views10 pages

DSA Patterns Basics

The document outlines fundamental data structure and algorithm patterns, including Sliding Window, Two Pointer Technique, and Prefix Sum, each with specific use cases. It also covers algorithms like Kadane’s for maximum subarray sums, Merge Intervals for scheduling, and methods for cycle detection using Fast and Slow Pointers. Additionally, it discusses Binary Search, Backtracking, Dynamic Programming, and Graph Traversal techniques such as BFS and DFS.

Uploaded by

Tanvi Shah
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

DSA Patterns - Fundamentals Guide

1. Sliding Window Pattern

Used for contiguous subarrays or substrings. Maintain a window using two pointers. Expand and
shrink based on conditions. Useful for maximum sum, longest substring without repeating
characters, etc.
2. Two Pointer Technique

Often used in sorted arrays. Two indices move toward each other or in the same direction.
Common in pair sum problems, removing duplicates, and reversing arrays.
3. Prefix Sum

Store cumulative sums to answer range queries efficiently. Useful in subarray sum equals K and
range sum problems.
4. Kadane’s Algorithm

Find maximum subarray sum in linear time. At each step decide whether to extend the current
subarray or start a new one.
5. Merge Intervals

Sort intervals and merge overlapping ones. Used in scheduling and meeting room problems.
6. Fast and Slow Pointers

Used for cycle detection in linked lists or arrays. Slow moves one step, fast moves two steps.
7. Binary Search Pattern

Divide and conquer approach on sorted arrays. Reduces time complexity to O(log n).
8. Backtracking

Used for generating permutations, combinations, subsets. Try possibilities and backtrack when
invalid.
9. Dynamic Programming

Break problems into overlapping subproblems. Use memoization or tabulation to optimize.


10. Graph Traversal (BFS/DFS)

Used for traversal in trees and graphs. BFS uses queue, DFS uses recursion or stack.

You might also like