DSA Notes

Hub Algorithm vs Data Structure - Key Differences Real-World Applications of DSA Time and Space Complexity Overview What is DSA? Data Structures and Algorithms Why Learn Data Structures and Algorithms Asymptotic Analysis - Understanding Algorithm Growth Best, Average, and Worst Case Analysis Big O Notation - Upper Bound Analysis Big Omega Notation - Lower Bound Analysis Big Theta Notation - Tight Bound Analysis Space Complexity - Memory Analysis Time Complexity Examples and Analysis Array Interview Problems and Solutions Array Operations - Insert, Delete, Search Array Rotation Techniques Array Searching Techniques Arrays - Fundamental Data Structure Dynamic Arrays - Flexible Sizing Multidimensional Arrays - 2D and Beyond Sliding Window Technique for Arrays Anagram Problems - Character Rearrangement Palindrome Problems and Solutions Pattern Searching in Strings String Interview Problems Collection String Matching Algorithms - Pattern Searching String Operations - Concatenation, Substring, Manipulation String Data Structure - Fundamentals Circular Linked List - Ring Structure Doubly Linked List - Bidirectional Traversal Linked List Interview Problems Linked List - Data Structure Fundamentals Linked List Operations - Insert, Delete, Reverse Reverse Linked List - Iterative and Recursive Singly Linked List - Implementation and Operations Balanced Parentheses - Stack Application Infix, Prefix, Postfix Expressions - Stack Application Stack Implementation Techniques Stack Interview Problems and Solutions Stack Data Structure - LIFO Principle Stack using Arrays - Static Implementation Stack using Linked Lists - Dynamic Implementation Circular Queue - Efficient Space Usage Deque (Double Ended Queue)Priority Queue - Custom Ordering Queue Applications - Real-World Use Cases Queue Implementation - Array and Linked List Queue Interview Problems and Solutions Queue Data Structure - FIFO Principle AVL Tree - Self-Balancing Binary Search Tree Binary Search Tree (BST)Binary Tree - Structure and Operations Fenwick Tree (Binary Indexed Tree)Red-Black Tree - Another Balanced BST Segment Tree - Range Query Data Structure Tree Interview Problems Collection Tree Data Structure Fundamentals Tree Traversals - Inorder, Preorder, Postorder, Level Order Heap Data Structure Heap Operations Heap Interview Problems Max-Heap Min-Heap Implementation and Use Cases Priority Queue using Heap Bellman-Ford Algorithm Breadth-First Search (BFS) Algorithm Depth-First Search (DFS) Algorithm Dijkstra\Floyd-Warshall Algorithm Graph Interview Problems Graph Data Structure Fundamentals Graph Representation Methods Kruskal\Minimum Spanning Tree (MST)Prim\Shortest Path Algorithms: Complete Comparison Topological Sorting Union-Find (Disjoint Set Union)Separate Chaining Collision Handling Hash Functions Hashing Fundamentals Hashing Interview Problems Open Addressing Bubble Sort - Simple Sorting Algorithm Counting Sort - Non-Comparison Sorting Heap Sort - Heap Based Sorting Insertion Sort - Build Sorted Array Merge Sort - Divide and Conquer Quick Sort - Partition Based Sorting Radix Sort - Digit Based Sorting Selection Sort - Selection Based Sorting Sorting Algorithms Comparison - Choosing the Right Algorithm Sorting Algorithms - Fundamentals and Concepts Binary Search - Efficient Searching Interpolation Search - Intelligent Searching Linear Search - Sequential Search Algorithm Search Algorithms Comparison Searching Algorithm Interview Problems Ternary Search Algorithm Backtracking with Recursion Recursion Fundamentals - Base Case and Recurrence Recursion Problems and Solutions Recursion Tree - Visualizing Function Calls Recursion vs Iteration - Comparing Approaches Tail Recursion - Optimization Technique Dynamic Programming Interview Problems Dynamic Programming Fundamentals Fibonacci with Dynamic Programming 0/1 Knapsack Problem Longest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Matrix Chain Multiplication Memoization (Top-Down Dynamic Programming)Tabulation (Bottom-Up Dynamic Programming)Activity Selection Problem Fractional Knapsack Greedy Interview Problems Greedy Algorithm Fundamentals Huffman Coding — Data Structures & Algorithms Job Sequencing with Deadlines Backtracking Fundamentals Backtracking Practice Problems N-Queens Problem Rat in a Maze Subset Generation Sudoku Solver Codeforces Guide for Competitive Programmers Common Competitive Programming Techniques Contest Strategies for Competitive Programming Competitive Programming Introduction Fast Input/Output for Competitive Programming LeetCode Guide for Interview Preparation Bit Manipulation - Advanced Techniques Bloom Filter - Probabilistic Data Structure Computational Geometry - Algorithms and Techniques Disjoint Set Union (DSU) - Union Find Randomized Algorithms - Probabilistic Computing Skip List - Probabilistic Balanced Structure Suffix Array - String Indexing Trie - Prefix Tree for Efficient Searching Autocomplete System Using Trie Library Management System Using DSA Route Finder Using Graphs Mini Search Engine Project Social Network Analysis Using Graphs Essential Coding Patterns for Interviews DSA Cheatsheet: Quick Reference Essential DSA Interview Questions FAANG DSA Sheet: Company-Specific Patterns and Problems Problem Solving Strategies for Coding Interviews Complexity Cheatsheet Important Algorithms Summary Best Practice Platforms for DSA Recommended Books for DSA

Common Competitive Programming Techniques

Essential algorithmic techniques every competitive programmer must know: two pointers, sliding window, binary search on answer, prefix sums, difference arrays, and bit manipulation.

Overview

These six techniques form the bread and butter of competitive programming. They appear in 70%+ of contest problems either directly or as building blocks for more complex solutions. Master these, and you can solve most Div 2 A-C problems on Codeforces.

Two Pointers

The two-pointer technique uses two indices that move through an array in a coordinated way, typically reducing an O(n²) brute force to O(n).

Pattern 1: Converging Pointers

Used when searching for pairs in a sorted array:

Example

// Find two numbers that sum to target in a sorted array bool twoSum(vector<int>& arr, int target) { int left = 0, right = arr.size() - 1; while (left < right) { int sum = arr[left] + arr[right]; if (sum == target) return true; else if (sum < target) left++; else right--; } return false; }

Pattern 2: Same-Direction Pointers

Used for problems involving subarrays or removing duplicates:

Example

// Remove duplicates from sorted array in-place int removeDuplicates(vector<int>& nums) { if (nums.empty()) return 0; int slow = 0; for (int fast = 1; fast < nums.size(); fast++) { if (nums[fast] != nums[slow]) { slow++; nums[slow] = nums[fast]; } } return slow + 1; }

When to Use

Array is sorted (or can be sorted without losing information)
Looking for pairs/triplets with a target sum
Merging two sorted arrays
Partitioning problems

Sliding Window

A special case of two pointers where you maintain a "window" over a contiguous subarray, expanding the right boundary and shrinking the left boundary as needed.

Fixed-Size Window

Example

// Maximum sum subarray of size k int maxSumSubarray(vector<int>& arr, int k) { int windowSum = 0, maxSum = INT_MIN; for (int i = 0; i < arr.size(); i++) { windowSum += arr[i]; if (i >= k) windowSum -= arr[i - k]; // Remove leftmost if (i >= k - 1) maxSum = max(maxSum, windowSum); } return maxSum; }

Variable-Size Window (Shrinkable)

Example

// Smallest subarray with sum >= target int minSubArrayLen(int target, vector<int>& nums) { int left = 0, sum = 0, minLen = INT_MAX; for (int right = 0; right < nums.size(); right++) { sum += nums[right]; while (sum >= target) { minLen = min(minLen, right - left + 1); sum -= nums[left++]; } } return minLen == INT_MAX ? 0 : minLen; }

Variable-Size Window (Non-Shrinkable)

A clever variant where the window only grows or slides but never shrinks — useful for "find the longest" problems:

Example

// Longest substring with at most k distinct characters int longestWithKDistinct(string s, int k) { unordered_map<char, int> freq; int left = 0, maxLen = 0; for (int right = 0; right < s.size(); right++) { freq[s[right]]++; while (freq.size() > k) { freq[s[left]]--; if (freq[s[left]] == 0) freq.erase(s[left]); left++; } maxLen = max(maxLen, right - left + 1); } return maxLen; }

Binary Search on Answer

When the problem asks "what is the minimum/maximum value X such that condition(X) is true?", and condition is monotonic (once true, stays true), you can binary search on X.

Template

Example

// Find minimum X in [lo, hi] such that check(X) is true int lo = MIN_POSSIBLE, hi = MAX_POSSIBLE; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (check(mid)) hi = mid; // mid might be answer, search left else lo = mid + 1; // mid is too small } // lo == hi == answer

Classic Example: Minimum Days to Make M Bouquets

Example

// Can we make m bouquets of k adjacent flowers by day `days`? bool canMake(vector<int>& bloomDay, int m, int k, int days) { int bouquets = 0, consecutive = 0; for (int bloom : bloomDay) { if (bloom <= days) { consecutive++; if (consecutive == k) { bouquets++; consecutive = 0; } } else { consecutive = 0; } } return bouquets >= m; } int minDays(vector<int>& bloomDay, int m, int k) { int lo = 1, hi = *max_element(bloomDay.begin(), bloomDay.end()); while (lo < hi) { int mid = lo + (hi - lo) / 2; if (canMake(bloomDay, m, k, mid)) hi = mid; else lo = mid + 1; } return lo; }

How to Recognize

"Minimize the maximum" or "Maximize the minimum"
Feasibility is monotonic: if X works, X+1 also works (or vice versa)
You can write a check(X) function that runs in O(n) or O(n log n)

Prefix Sums

Prefix sums let you compute the sum of any subarray in O(1) after O(n) preprocessing.

Example

// Build prefix sum array vector<int> prefix(n + 1, 0); for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + arr[i]; // Sum of arr[l..r] = prefix[r+1] - prefix[l] int rangeSum = prefix[r + 1] - prefix[l];

2D Prefix Sums

For matrix subregion queries:

Example

// Build 2D prefix sum vector<vector<int>> pre(m+1, vector<int>(n+1, 0)); for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) pre[i][j] = mat[i-1][j-1] + pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1]; // Sum of rectangle (r1,c1) to (r2,c2) — 0-indexed inputs int rectSum = pre[r2+1][c2+1] - pre[r1][c2+1] - pre[r2+1][c1] + pre[r1][c1];

Difference Arrays

The inverse of prefix sums. When you need to add a value to an entire range [l, r] multiple times, do it in O(1) per update and reconstruct the array at the end.

Example

// Add val to all elements in range [l, r] void rangeAdd(vector<int>& diff, int l, int r, int val) { diff[l] += val; if (r + 1 < diff.size()) diff[r + 1] -= val; } // Reconstruct original array from difference array vector<int> reconstruct(vector<int>& diff) { vector<int> arr(diff.size()); arr[0] = diff[0]; for (int i = 1; i < diff.size(); i++) arr[i] = arr[i-1] + diff[i]; return arr; }

Use case: Q queries each adding a value to range [l, r]. Naive is O(Q * N). With difference arrays: O(Q + N).

Bit Manipulation

Bits let you encode sets, toggle states, and perform arithmetic tricks in O(1).

Essential Operations

cpp example

x & (x - 1)    // Remove lowest set bit (Brian Kernighan)
x | (1 << i)   // Set bit i
x & ~(1 << i)  // Clear bit i
x ^ (1 << i)   // Toggle bit i
x & (-x)       // Isolate lowest set bit
__builtin_popcount(x)  // Count set bits
__builtin_clz(x)       // Count leading zeros

Subset Enumeration with Bitmasks

Example

// Iterate over all subsets of a set represented as bitmask for (int mask = 0; mask < (1 << n); mask++) { // mask represents a subset for (int i = 0; i < n; i++) { if (mask & (1 << i)) { // Element i is in this subset } } }

XOR Properties

a ^ a = 0 (self-cancellation)
a ^ 0 = a (identity)
XOR of all elements finds the unique element in "every element appears twice except one"

cpp example

int findSingle(vector<int>& nums) {
    int result = 0;
    for (int x : nums) result ^= x;
    return result;
}

Summary Table

Technique	Time Saved	When to Use
Two Pointers	O(n²) → O(n)	Sorted array, pair finding
Sliding Window	O(n²) → O(n)	Contiguous subarray optimization
Binary Search on Answer	Varies	Monotonic feasibility function
Prefix Sums	O(n) per query → O(1)	Range sum queries
Difference Arrays	O(n) per update → O(1)	Range update queries
Bit Manipulation	O(n) → O(1)	Set operations, subset enumeration

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Common Competitive Programming Techniques.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Data Structures & Algorithms topic.

Search Terms

data-structures-algorithms, data structures & algorithms, data, structures, algorithms, competitive, programming, common

Related Data Structures & Algorithms Topics

Continue learning this concept

PreviousCodeforces Guide for Competitive Programmers NextContest Strategies for Competitive Programming

DSA Notes

Common Competitive Programming Techniques

Essential algorithmic techniques every competitive programmer must know: two pointers, sliding window, binary search on answer, prefix sums, difference arrays, and bit manipulation.

Overview

Two Pointers

The two-pointer technique uses two indices that move through an array in a coordinated way, typically reducing an O(n²) brute force to O(n).

Pattern 1: Converging Pointers

Used when searching for pairs in a sorted array:

Example

Pattern 2: Same-Direction Pointers

Used for problems involving subarrays or removing duplicates:

Example

When to Use

Array is sorted (or can be sorted without losing information)
Looking for pairs/triplets with a target sum
Merging two sorted arrays
Partitioning problems

Sliding Window

A special case of two pointers where you maintain a "window" over a contiguous subarray, expanding the right boundary and shrinking the left boundary as needed.

Fixed-Size Window

Example

Variable-Size Window (Shrinkable)

Example

Variable-Size Window (Non-Shrinkable)

A clever variant where the window only grows or slides but never shrinks — useful for "find the longest" problems:

Example

Binary Search on Answer

When the problem asks "what is the minimum/maximum value X such that condition(X) is true?", and condition is monotonic (once true, stays true), you can binary search on X.

Template

Example

Classic Example: Minimum Days to Make M Bouquets

Example

How to Recognize

"Minimize the maximum" or "Maximize the minimum"
Feasibility is monotonic: if X works, X+1 also works (or vice versa)
You can write a check(X) function that runs in O(n) or O(n log n)

Prefix Sums

Prefix sums let you compute the sum of any subarray in O(1) after O(n) preprocessing.

Example

2D Prefix Sums

For matrix subregion queries:

Example

Difference Arrays

The inverse of prefix sums. When you need to add a value to an entire range [l, r] multiple times, do it in O(1) per update and reconstruct the array at the end.

Example

Use case: Q queries each adding a value to range [l, r]. Naive is O(Q * N). With difference arrays: O(Q + N).

Bit Manipulation

Bits let you encode sets, toggle states, and perform arithmetic tricks in O(1).

Essential Operations

cpp example

x & (x - 1)    // Remove lowest set bit (Brian Kernighan)
x | (1 << i)   // Set bit i
x & ~(1 << i)  // Clear bit i
x ^ (1 << i)   // Toggle bit i
x & (-x)       // Isolate lowest set bit
__builtin_popcount(x)  // Count set bits
__builtin_clz(x)       // Count leading zeros

Subset Enumeration with Bitmasks

Example

XOR Properties

a ^ a = 0 (self-cancellation)
a ^ 0 = a (identity)
XOR of all elements finds the unique element in "every element appears twice except one"

cpp example

int findSingle(vector<int>& nums) {
    int result = 0;
    for (int x : nums) result ^= x;
    return result;
}

Summary Table

Technique	Time Saved	When to Use
Two Pointers	O(n²) → O(n)	Sorted array, pair finding
Sliding Window	O(n²) → O(n)	Contiguous subarray optimization
Binary Search on Answer	Varies	Monotonic feasibility function
Prefix Sums	O(n) per query → O(1)	Range sum queries
Difference Arrays	O(n) per update → O(1)	Range update queries
Bit Manipulation	O(n) → O(1)	Set operations, subset enumeration

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Common Competitive Programming Techniques.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Data Structures & Algorithms topic.

Search Terms

data-structures-algorithms, data structures & algorithms, data, structures, algorithms, competitive, programming, common

Related Data Structures & Algorithms Topics

Continue learning this concept

PreviousCodeforces Guide for Competitive Programmers NextContest Strategies for Competitive Programming