Scribd
Upload
18 views3 pages

DSA Patterns Guide

The document outlines various data structure and algorithm (DSA) patterns for problem-solving, including Pair Counting, Two Pointer, Sliding Window, and others. Each pattern is accompanied by clues, thought processes, and examples to illustrate its application. The guide serves as a reference for efficiently tackling algorithmic challenges.

Uploaded by

kavitarathore09
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
18 views3 pages

DSA Patterns Guide

The document outlines various data structure and algorithm (DSA) patterns for problem-solving, including Pair Counting, Two Pointer, Sliding Window, and others. Each pattern is accompanied by clues, thought processes, and examples to illustrate its application. The guide serves as a reference for efficiently tackling algorithmic challenges.

Uploaded by

kavitarathore09
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 Pattern Recognition Guide

1. Pair Counting Pattern (i < j)

• Clue: Count pairs (i, j), i < j, condition on A[i], A[j], n up to 10^5
• Think: Merge Sort Counting
• Examples: Inversion Count, Important Reverse Pairs, Count smaller elements after self

2. Two Pointer Pattern

• Clue: Sorted array, find pairs/triplets, sum problems, remove duplicates


• Think: Left & Right pointers
• Examples: Two Sum (sorted), 3Sum, Container with most water

3. Sliding Window Pattern

• Clue: Subarray, substring, contiguous, max/min length, at most k...


• Think: Expand right, shrink left
• Examples: Longest substring without repeating, Max sum subarray of size k

4. Binary Search on Answer

• Clue: Minimize maximum, maximize minimum, feasibility check, monotonic property


• Think: Binary search on result space
• Examples: Aggressive cows, Allocate books, Koko eating bananas

5. Greedy Pattern

• Clue: Minimum operations, intervals, only increment/decrement


• Think: Local optimal -> Global optimal
• Examples: Make array unique, Activity selection, Jump game

6. Prefix Sum Pattern

• Clue: Subarray sum, range queries, count subarrays


• Think: Cumulative sum + HashMap
• Examples: Subarray sum = k, Count subarrays divisible by k

7. Hashing Pattern

• Clue: Find duplicates, frequency, unsorted two sum


• Think: HashMap / HashSet

8. Monotonic Stack Pattern

• Clue: Next greater/smaller element, histogram problems


• Think: Stack maintaining order
• Examples: Stock span, Largest rectangle in histogram

9. Fast & Slow Pointer Pattern

• Clue: Cycle detection, middle of list


• Think: Floyd’s algorithm

10. Dynamic Programming Pattern

• Clue: Choices at each step, overlapping subproblems, ways to do something


• Think: State + Transition
• Examples: Knapsack, Longest Increasing Subsequence

You might also like