- Prefix Sum Algorithm
- Difference Array Technique
- Range Sum Query
- Kadane’s Algorithm
- Maximum Prefix Sum
In this session, students will understand how to optimize array-related problems using Prefix Sum techniques. The session will focus on reducing unnecessary repeated calculations and improving time complexity from brute-force approaches to optimized solutions.
Students will also learn:
- How Prefix Sum works internally
- How Range Queries are solved efficiently
- How Kadane’s Algorithm is used to find maximum subarray sums
- How optimization techniques improve coding performance in interviews and competitive programming
| Concept | LeetCode Problem No. | Problem Title |
|---|---|---|
| Prefix Sum | 1480 | Running Sum of 1D Array |
| Range Sum Query | 303 | Range Sum Query – Immutable |
| Kadane’s Algorithm | 53 | Maximum Subarray |
| Prefix Sum + Hashing | 560 | Subarray Sum Equals K |
| Difference Array Technique | 370 | Range Addition |
- Fixed Size Sliding Window
- Variable Size Sliding Window
- Maximum Sum Subarray
- Longest Subarray Problems
- Minimum Window Problems
This session will focus on solving subarray and substring problems efficiently using Sliding Window techniques. Students will learn how to replace nested loop approaches with optimized window-based solutions.
The session will include:
- Understanding fixed and variable window patterns
- Solving longest and minimum window problems
- Learning optimization strategies frequently asked in interviews
- Building logical thinking for medium-level DSA problems
| Concept | LeetCode Problem No. | Problem Title |
|---|---|---|
| Fixed Size Sliding Window | 643 | Maximum Average Subarray I |
| Variable Size Sliding Window | 209 | Minimum Size Subarray Sum |
| Longest Subarray / Substring | 3 | Longest Substring Without Repeating Characters |
| Minimum Window Problem | 76 | Minimum Window Substring |
| Sliding Window Optimization | 239 | Sliding Window Maximum |