DEV Community: M Umair Ullah

🔥 “Stack Explained: The Secret Weapon Behind LeetCode Monotonic Problems”

M Umair Ullah — Thu, 04 Sep 2025 06:19:39 +0000

Mastering Stack Data Structure – From Basics to LeetCode Practice

Stacks are one of the most fundamental data structures in computer science and play a critical role in problem-solving, algorithms, and real-world systems. In this post, I’ll walk you through what a stack is, why we need it, important algorithms, and how I’m practicing LeetCode stack problems to master this concept. I’ll also share my GitHub repository link at the end where I upload all my practice codes.

📌 What is a Stack?

A stack is a linear data structure that follows the principle of LIFO (Last In, First Out).

Imagine stacking plates: you can only take out the plate on the top.
The same rule applies to a stack: Insertions (push) and deletions (pop) happen only at one end (top).

Basic Operations:

push(x): Insert element x at the top.
pop(): Remove the top element.
top()/peek(): Get the top element without removing it.
isEmpty(): Check if stack is empty.

⚡ Why Do We Need a Stack?

Stacks may sound simple, but they are powerful and used everywhere:

Expression Evaluation: Balanced Parentheses, Infix → Postfix conversion.
Backtracking: Undo/redo in editors, recursion call stack.
Monotonic Stack Problems: Next Greater Element, Stock Span, Daily Temperatures.
System Design: Function calls in memory are handled using a call stack.

🔑 Important Stack Problem References

Here are the must-practice problems (with links) that cover all the essential stack patterns:

🟢 Easy

🟡 Medium

🔴 Hard

⏱️ Time & Space Complexity Analysis

Operation	Time Complexity	Space Complexity
Push	O(1)	O(1)
Pop	O(1)	O(1)
Peek/Top	O(1)	O(1)
Search	O(n)	O(1)
Next Greater Element / Daily Temperatures	O(n)	O(n)

👉 Most stack-based problems (like NGE, Daily Temperatures) are O(n) because each element is pushed and popped at most once.

📚 My LeetCode Practice Plan

To fully master stacks, I’m solving these problems step by step:

Easy Level: Warm up with Valid Parentheses, Min Stack.
Medium Level: Focus on monotonic stack problems (NGE, Daily Temperatures, Stock Span).
Hard Level: Move on to Histogram and Matrix-based problems.

This ensures I cover all core algorithms involving stacks.

📂 GitHub Repository

I’m uploading all my stack solutions (brute force + optimized stack approach) to my GitHub repo.

👉 Check it out here: My GitHub Repo – Stack Practice

✨ Conclusion

Stacks are simple but powerful. By practicing problems like Next Greater Element, Daily Temperatures, Histogram problems, you’ll not only master the stack but also build a strong foundation for advanced algorithms and interview prep.

💡 My approach: I’m practicing every problem type, pushing solutions to GitHub, and writing blogs to keep track of my journey.

🔥 If you’re also practicing, try out these problems, optimize your solutions, and let’s grow together!

🔑 “Mastering Strings in Competitive Programming: Algorithms, Challenges & Solutions”

M Umair Ullah — Sat, 23 Aug 2025 04:44:08 +0000

🧵 Strings in DSA – A Complete Guide with Problems, Algorithms & Solutions

Strings are one of the most fundamental yet tricky data structures in programming.

They look simple, but once you dive deeper, you’ll realize they can create some of the hardest algorithmic challenges.

In this blog post, I’ll walk you through:

What makes strings tricky
Common string-related problems
Famous algorithms to solve them
Important practice questions
📌 And finally, my GitHub repository with full implementations and explanations of all major string algorithms in C++

🔰 Introduction to Strings

A string is simply a sequence of characters.

But when solving problems, strings become complex because of:

Searching patterns inside a larger string
Comparing multiple substrings efficiently
Handling overlapping characters
Optimizing time complexity for large inputs

For beginners, brute-force methods often fail due to TLE (Time Limit Exceeded) in coding contests.

That’s where string algorithms come to the rescue. 🚀

⚡ Problems We Face in String Questions

Here are some common categories of string problems you’ll encounter in coding interviews and competitive programming:

Pattern Searching Problems
- Example: Find if a substring exists in a given string.
- Naive approach = O(n*m) (very slow for large strings).
- ✅ Solution: KMP Algorithm, Rabin-Karp, Z Algorithm
Prefix & Suffix Problems
- Example: Find the longest prefix which is also a suffix.
- ✅ Solution: KMP Prefix Function, Z Algorithm
Palindrome Problems
- Example: Longest Palindromic Substring, Palindrome Partitioning.
- ✅ Solution: Manacher’s Algorithm, Dynamic Programming
String Hashing Problems
- Example: Compare substrings quickly.
- ✅ Solution: Rabin-Karp, Polynomial Hashing, Rolling Hash
Lexicographical Problems
- Example: Smallest/Largest rotation of a string.
- ✅ Solution: Suffix Arrays, Suffix Automaton
Edit Distance & Transformation Problems
- Example: Convert one string to another in minimum operations.
- ✅ Solution: Dynamic Programming (DP), Levenshtein Distance
Substring Counting & Matching
- Example: Count distinct substrings, repeated substrings.
- ✅ Solution: Suffix Array, Trie, Hashing

🧠 Popular String Algorithms

Here’s a quick list of must-know algorithms for solving string problems efficiently:

Naive Pattern Searching – baseline method
Sliding Window on Strings – efficient substring/window-based problems
Two-Pointer Technique on Strings – optimal traversal and comparison
Hashing on Strings – rolling hash & substring matching
KMP Algorithm (Knuth–Morris–Pratt) – efficient pattern searching
Z Algorithm – linear-time substring search
Rabin-Karp Algorithm – string matching using hashing

I’ve implemented all these algorithms with step-by-step explanations and C++ code in my GitHub repository.

🎯 Important String Questions to Practice

Here are some classic string problems (must-do for interviews & CP):

Longest Palindromic Substring
Count Distinct Substrings of a String
Smallest and Largest Lexicographical Rotation
Find All Occurrences of a Pattern in a Text
Check if Two Strings are Anagrams
Minimum Edit Distance (Levenshtein Distance)
Repeated Substring Pattern
Longest Prefix Suffix (LPS) Problem
Count Number of Palindromic Substrings
Find All Substrings of a String (Brute Force + Optimized)

📚 Complete Implementations & Explanations

I didn’t want to make a separate post for each algorithm here.

Instead, I’ve compiled all string algorithms, with detailed explanations and C++ implementations, on my GitHub repo.

👉 Check out the full collection here:

🔗 My GitHub Repository on String Algorithms

✅ Conclusion

Strings may look easy, but solving string problems efficiently requires powerful algorithms.

Once you master KMP, Z, Manacher, Suffix Arrays, and Hashing, you’ll be able to tackle almost any string-related question in coding interviews and competitions.

If you’re preparing for interviews, CP, or a strong DSA foundation, bookmark this post and practice the problems listed above.

And whenever you’re stuck, visit my GitHub repo for ready-to-use C++ code with explanations.

🚀 Let’s master Strings and crack those coding interviews!

Binary Search on Answers — Crack the Hardest Problems in Log Time

M Umair Ullah — Tue, 12 Aug 2025 05:58:22 +0000

🚀 Binary Search on Answers – The Complete Guide with Examples

📌 Introduction
Binary Search is not just for sorted arrays!
There’s a powerful pattern called "Binary Search on Answers" — where instead of searching inside an array, we search in the range of possible answers to a problem.

This technique is widely used in optimization problems like:

Minimize the maximum workload
Minimize days to finish a task
Minimize the speed to complete something
Allocate tasks with constraints

If your brute force approach is checking answers from 1 to maxPossibleValue, you can often replace it with Binary Search to drastically speed things up.

📖 Definition

Binary Search on Answers is an algorithmic technique where:

You define the search space as all possible values of the answer.

You check feasibility of a middle value using a helper function.

`If the answer is possible, search the left half (to minimize).
If the answer is not possible, search the right half (to increase).`

🪜 Naive Approach (Brute Force)

Iterate over all possible values of the answer.
For each value, check if it satisfies the problem constraints.
Take the smallest valid value (or largest if maximizing).
Drawback: Too slow when the answer space is huge (e.g., 1e9).

⚡ Optimized Approach (Binary Search)

Instead of checking every answer, cut the search space in half each time.
Use a helper function isFeasible() to check if the mid value works.
Achieves O(log(maxPossibleValue) × N) time complexity.

⏳ Time & Space Complexity

Brute Force O(N × maxValue) O(1)
Optimized (BS) O(N × log(maxValue)) O(1)

💡 Example Problem – Koko Eating Bananas

Problem Statement

Koko loves to eat bananas. She can decide her eating speed k bananas/hour.
Given piles and h, find the minimum k to eat all bananas before guards return.

🛠 Brute Force Approach

cpp

#include <bits/stdc++.h>
using namespace std;

// Check if Koko can eat all bananas at speed k in h hours
bool canEatAll(vector<int>& piles, int k, int h) {
    long long totalHours = 0;
    for (int bananas : piles) {
        totalHours += (bananas + k - 1) / k; // ceil division
    }
    return totalHours <= h;
}

int minEatingSpeedBruteForce(vector<int>& piles, int h) {
    int maxPile = *max_element(piles.begin(), piles.end());
    for (int k = 1; k <= maxPile; k++) {
        if (canEatAll(piles, k, h)) {
            return k;
        }
    }
    return maxPile;
}

int main() {
    vector<int> piles = {3, 6, 7, 11};
    int h = 8;
    cout << "Brute Force Result: " << minEatingSpeedBruteForce(piles, h) << endl;
    return 0;
}

⚡ Optimized Approach (Binary Search)

cpp

#include <bits/stdc++.h>
using namespace std;

bool canEatAll(vector<int>& piles, int k, int h) {
    long long totalHours = 0;
    for (int bananas : piles) {
        totalHours += (bananas + k - 1) / k;
    }
    return totalHours <= h;
}

int minEatingSpeedOptimized(vector<int>& piles, int h) {
    int low = 1, high = *max_element(piles.begin(), piles.end());
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (canEatAll(piles, mid, h)) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return low;
}

int main() {
    vector<int> piles = {3, 6, 7, 11};
    int h = 8;
    cout << "Optimized Result: " << minEatingSpeedOptimized(piles, h) << endl;
    return 0;
}

📝 Step-by-Step Explanation

Define Search Space: Eating speed ranges from 1 to max(piles).
Check Feasibility: If she can finish at speed mid, try smaller speed.
Shrink Search Space: Binary search reduces the range quickly.

🔥 Important Practice Questions

Koko Eating Bananas – LeetCode #875
Capacity to Ship Packages Within D Days – LeetCode #1011
Minimum Number of Days to Make m Bouquets – LeetCode #1482
Split Array Largest Sum – LeetCode #410
Book Allocation Problem – GFG

🤝 My Open Source Contribution

I’ve implemented these problems in my open-source GitHub repository:
📂 GitHub Repo: Check Out.

🎯 Key Takeaways

Use binary search on answers when brute force is iterating over possible values.
Always identify the search space & feasibility function.
It’s a game changer for optimization problems.`

The Logic Behind 0s, 1s, and 2s (DNF)

M Umair Ullah — Sun, 03 Aug 2025 06:07:10 +0000

🚩 Mastering the Dutch National Flag Algorithm in C++

Sorting 0s, 1s, and 2s in a single pass? That's the power of the Dutch National Flag Algorithm, an elegant algorithm designed by computer scientist Edsger Dijkstra. It's an essential technique in your DSA toolbox!

📌 Problem Statement

You're given an array consisting only of 0s, 1s, and 2s. Your task is to sort the array in-place in a single pass so that:

All 0s appear first
All 1s appear next
All 2s appear last

Input: nums = [2, 0, 2, 1, 1, 0]

Output: nums = [0, 0, 1, 1, 2, 2]

🤔 Real-Life Analogy

Imagine you have a bucket of red, white, and blue balls. You want to group them together in the order of colors — this is exactly what the Dutch National Flag problem is about!

📚 Understanding the Concept

The Dutch National Flag problem can be solved by maintaining three pointers:

low: to track the position where the next 0 should be placed.
mid: the current element being evaluated.
high: to track the position where the next 2 should go.

The idea is to:

Swap 0s to the beginning.
Leave 1s in the middle.
Swap 2s to the end.

🧠 Table to Understand Swapping:

Index	Before Action	After Action (if nums[mid] == 0)
0	2	0
1	0	2
	swap(nums[low], nums[mid])
	++low, ++mid	++low, ++mid

🌀 Naive Approach

Use a counting sort-like method.

🧾 Steps:

Count the number of 0s, 1s, and 2s.
Overwrite the original array with counted values.

⏱ Time: O(n)

🧠 Space: O(1)

cpp
void sortColors(vector<int>& nums) {
    int zero = 0, one = 0, two = 0;
    for (int num : nums) {
        if (num == 0) zero++;
        else if (num == 1) one++;
        else two++;
    }

    int i = 0;
    while (zero--) nums[i++] = 0;
    while (one--) nums[i++] = 1;
    while (two--) nums[i++] = 2;
}

⚡ Optimized One-Pass Approach (Dutch National Flag Algorithm)

🚀 Algorithm Steps:

Initialize low = 0, mid = 0, and high = n - 1.
While mid <= high, check:
If nums[mid] == 0: swap with nums[low], increment low and mid.
If nums[mid] == 1: just increment mid.
If nums[mid] == 2: swap with nums[high], decrement high.

✅ Time Complexity: O(n)
✅ Space Complexity: O(1)

💻 Code:

cpp

void sortColors(vector<int>& nums) {
    int low = 0, mid = 0, high = nums.size() - 1;

    while (mid <= high) {
        if (nums[mid] == 0) {
            swap(nums[low], nums[mid]);
            low++; mid++;
        }
        else if (nums[mid] == 1) {
            mid++;
        }
        else {
            swap(nums[mid], nums[high]);
            high--;
        }
    }
}

🧪 Dry Run Example

Input: [2, 0, 2, 1, 1, 0]
Initial: low = 0, mid = 0, high = 5

Step 1: swap(nums[0], nums[5]) -> [0, 0, 2, 1, 1, 2]
low = 0, mid = 0, high = 4

Step 2: nums[0] == 0 => swap(nums[0], nums[0]) => low++, mid++`

Final: [0, 0, 1, 1, 2, 2]

🔗 Related Problems to Practice

Sort Colors
Sort Array by Parity
Wiggle Sort
Rainbow Sort

🎯 When to Use Dutch National Flag?

When the array contains 3 distinct categories or values.
You want to sort in-place with constant space.
Common in segregation problems, such as even/odd, 0s/1s, red/blue/green, etc.

🚀 Open Source Contribution

I'm solving DSA problems in C++ and uploading them algorithm-wise to GitHub.
Feel free to check it out, use the solutions, or contribute!

👉 📁 DSA-in-C++ GitHub Repository

What I Wish I Knew Before Learning the Two Pointer Algorithm

M Umair Ullah — Sat, 02 Aug 2025 07:04:47 +0000

🚀 Mastering the Two Pointers Technique in DSA

The Two Pointers technique is one of the most efficient and elegant solutions for solving array and string problems that involve searching, partitioning, or comparison. This guide will walk you through the complete concept of the Two Pointers technique, its motivation, real-world applications, variations, problem patterns, and code examples.

🔍 What is the Two Pointers Technique?

The Two Pointers technique involves using two variables (usually indices) that move through the data structure (like an array or string) in a coordinated way to solve a problem in linear or near-linear time.

Usually applied to sorted arrays or strings.
Used to avoid nested loops and reduce time complexity from O(n^2) to O(n) or O(n log n).
Pointers can move:
- From both ends toward the center (inward)
- From start to end (one slow, one fast)
- Sliding over a fixed or dynamic window

🎯 Motivation

Two Pointers is widely used because:

It reduces brute-force complexity
It is elegant, easy to debug, and memory efficient
It covers core patterns for sliding window, partitioning, merging, etc.

🔧 Variations of Two Pointers

Type	Description	Examples
Opposite Ends	One pointer from start, one from end	Container With Most Water, Two Sum II
Same Direction	Both pointers start from one end	Remove Duplicates, Move Zeroes
Sliding Window	Two pointers define window	Longest Substring Without Repeating Characters

📚 Common Problem Examples

1. Two Sum II (Sorted Array)

vector<int> twoSum(vector<int>& numbers, int target) {
    int i = 0, j = numbers.size() - 1;
    while (i < j) {
        int sum = numbers[i] + numbers[j];
        if (sum == target) return {i + 1, j + 1};
        else if (sum > target) j--;
        else i++;
    }
    return {};
}

2. Container With Most Water

int maxArea(vector<int>& height) {
    int l = 0, r = height.size() - 1, maxWater = 0;
    while (l < r) {
        int area = (r - l) * min(height[l], height[r]);
        maxWater = max(maxWater, area);
        if (height[l] < height[r]) l++;
        else r--;
    }
    return maxWater;
}

3. Move Zeroes

void moveZeroes(vector<int>& nums) {
    int i = 0;
    for (int j = 0; j < nums.size(); j++) {
        if (nums[j] != 0) swap(nums[i++], nums[j]);
    }
}

4. 4Sum Problem (Nested Two Pointers)

vector<vector<int>> fourSum(vector<int>& nums, long long target) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    int n = nums.size();

    for (int i = 0; i < n; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        for (int j = i + 1; j < n; j++) {
            if (j > i + 1 && nums[j] == nums[j - 1]) continue;
            int l = j + 1, r = n - 1;
            long long sum = target - nums[i] - nums[j];
            while (l < r) {
                long long curr = nums[l] + nums[r];
                if (curr < sum) l++;
                else if (curr > sum) r--;
                else {
                    res.push_back({nums[i], nums[j], nums[l], nums[r]});
                    while (l < r && nums[l] == res.back()[2]) l++;
                    while (l < r && nums[r] == res.back()[3]) r--;
                }
            }
        }
    }
    return res;
}

🧠 Pattern Recognition

Partitioning Arrays: Move all negative/positive/zero elements to one side.
Sorting Problems: Merge sorted arrays, sort colors (Dutch National Flag).
Searching Problems: Two Sum, 3Sum, 4Sum, Closest Sum.
Window-based problems: Longest substring with no repeating characters.

🌎 Real-World Applications

Network Buffers: Optimizing streaming packet flow.
Image Processing: Windowed filtering, edge detection.
Bioinformatics: DNA strand comparison.
Finance: Max profit window in stock prices.

🔥 Bonus: Open Source Contributions

If you're looking to contribute to open source using Two Pointers logic:

Explore LeetCode-style repositories like The-Algorithms/C++
Improve test coverage or write explanations in Striver’s SDE Sheet
Participate in community-driven DSA content at Codeforces or CodeStudio

🧑‍💻 Final Thoughts

Two Pointers is a cornerstone of your DSA foundation. Once you master it:

You reduce unnecessary complexity.
Improve runtime drastically.
Get closer to acing coding interviews at FAANG and top startups.

"Elegance in problem-solving often starts with two simple pointers."

Open Conntribution

Check out my Github Repo

Happy Coding 👨‍💻🎯

From Brute Force to Kadane’s: Solving the Maximum Subarray Problem Efficiently

M Umair Ullah — Thu, 31 Jul 2025 07:07:46 +0000

🚀 Mastering Kadane's Algorithm: The Ultimate Guide to Maximum Subarray Sum

Kadane's Algorithm is one of the most elegant and widely asked Dynamic Programming techniques in coding interviews and DSA contests. If you're tackling problems involving maximum sum of contiguous subarrays, then this is a must-have in your toolbox.

💡 What is the Problem?

You're given an array of integers (which may contain both positive and negative numbers). You need to find the maximum sum of any contiguous subarray.

🧠 Real-World Analogy

Imagine you're tracking your profit/loss daily in a month. You want to find the most profitable streak of consecutive days. Some days might have loss (negative), some profit (positive), but you must find the contiguous stretch that gives you the maximum net gain.

📊 Example

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

🔍 Step-by-Step Intuition

Start with a sum of 0 and a variable to track the maximum sum so far.
Iterate through each number:
Add it to your current sum.
If the current sum is greater than the max, update max.
If current sum becomes negative, reset it to 0 (because a negative sum won't help going forward).

🐢 Brute-Force Approach (Naive Method)

cpp
// Time Complexity: O(n^2)
int maxSubArray(vector<int>& nums) {
    int n = nums.size();
    int maxSum = INT_MIN;

    for (int i = 0; i < n; ++i) {
        int currSum = 0;
        for (int j = i; j < n; ++j) {
            currSum += nums[j];
            maxSum = max(maxSum, currSum);
        }
    }

    return maxSum;
}

❌ Inefficient for large arrays.
✅ Good for understanding the concept.

⚡ Optimized Approach: Kadane’s Algorithm

cpp

// Time Complexity: O(n)
// Space Complexity: O(1)

int maxSubArray(vector<int>& nums) {
    int currSum = 0, maxSum = INT_MIN;

    for (int i = 0; i < nums.size(); i++) {
        currSum += nums[i];
        maxSum = max(maxSum, currSum);

        if (currSum < 0)
            currSum = 0;
    }

    return maxSum;
}

🧪 Practice Examples

Try running the algorithm on:

nums = [5,4,-1,7,8] → Output: 23

nums = [-1,-2,-3,-4] → Output: -1

nums = [1] → Output: 1

nums = [8, -19, 5, -4, 20] → Output: 21

🔁 Related LeetCode Problems to Practice

** Problem**

Maximum Subarray
Maximum Product Subarray
Maximum Sum Circular Subarray
Contiguous Array

💼 Add It to Your Portfolio

This is one of the most interview-favorite problems asked by:

Google
Amazon
Microsoft
Netflix
Adobe

💻 Open Source GitHub Solutions

🔗 Check out my full Kadane’s Algorithm solution with explanations here:
👉 GitHub Repository

✨ Wrapping Up

Kadane’s Algorithm is your go-to solution when you're dealing with subarrays and maximum sums. It’s blazing fast (O(n)), elegant, and powerful. Practice the problems, understand the variations, and you'll master it in no time!

🧠 Sliding Window Pattern: The Secret Sauce for Efficient Algorithms

M Umair Ullah — Tue, 29 Jul 2025 07:25:13 +0000

🚀 Mastering the Sliding Window Technique in C++: Crack DSA Like a Pro!

When you're tackling arrays or strings in competitive programming or coding interviews, efficiency is king. That’s where the Sliding Window technique comes in — a game-changing approach that helps you move from brute-force to optimized solutions.

In this guide, we’ll dive deep into:

💡 What is Sliding Window?
🧠 Why use it?
🧱 Brute Force vs Optimized Approaches
📊 Time & Space Complexities
🧪 Real-world Examples
🔗 My GitHub Repository for Open Source Contribution

🧠 What is Sliding Window?

Sliding Window is a technique for solving problems involving linear data structures like arrays and strings. It involves creating a window (usually a subarray or substring) and moving it across the input to find a solution — without recalculating everything inside the window.

🤕 The Brute Force Way (Naive Approach)

Problem Example:

Find the maximum sum of a subarray of size k.

Naive Approach (O(n*k)):

cpp
int maxSumBruteForce(vector<int>& nums, int k) {
    int n = nums.size();
    int maxSum = INT_MIN;
    for (int i = 0; i <= n - k; i++) {
        int sum = 0;
        for (int j = 0; j < k; j++) {
            sum += nums[i + j];
        }
        maxSum = max(maxSum, sum);
    }
    return maxSum;
}

Time Complexity: O(n*k)
Space Complexity: O(1)

🚀 Optimized Sliding Window Approach

cpp

int maxSumSlidingWindow(vector<int>& nums, int k) {
    int windowSum = 0, maxSum = INT_MIN;
    for (int i = 0; i < k; i++) windowSum += nums[i];
    maxSum = windowSum;

    for (int i = k; i < nums.size(); i++) {
        windowSum += nums[i] - nums[i - k];
        maxSum = max(maxSum, windowSum);
    }
    return maxSum;
}

Time Complexity: O(n)
Space Complexity: O(1)

This approach avoids recalculating sums by adding the next element and removing the first element of the previous window.

🧪 Real Interview Examples Using Sliding Window

🔥 Maximum Sum Subarray of Size K
🍎 Fruit Into Baskets
🥇 Longest Subarray of 1s After Deleting One Element
🧮 Count Number of Nice Subarrays
💼 Minimum Size Subarray Sum

📚 Use-Cases of Sliding Window

Find the max/min/average of a subarray
Count distinct elements in a subarray
Longest substring with at most k distinct characters
Smallest window that satisfies a condition

⚙️ Template Code (Variable-Size Window):

cpp

int solve(vector<int>& nums) {
    int i = 0, j = 0, answer = 0;
    unordered_map<int, int> freq;

    while (j < nums.size()) {
        freq[nums[j]]++;

        // If condition violated
        while (freq.size() > k) {
            freq[nums[i]]--;
            if (freq[nums[i]] == 0) freq.erase(nums[i]);
            i++;
        }

        answer = max(answer, j - i + 1);
        j++;
    }

    return answer;
}

👨‍💻 Open Source Contribution

All of my DSA solutions using Sliding Window (including the LeetCode/Striver/Nudecode-150 ones) are available in my GitHub repo:

🔗 GitHub Repository:** 👉 Click Here to Explore My Solutions

Make sure to ⭐ star the repo and follow me for more updates!**

⏱️ O(N) to O(1): How Prefix Sum Will Change Your Code Forever

M Umair Ullah — Tue, 29 Jul 2025 07:16:14 +0000

🚀 Mastering Prefix Sum in C++: From Naive to Optimized

The Prefix Sum technique is one of the most powerful tools in array-based problems. It reduces time complexity significantly and is widely used in competitive programming, interviews, and DSA questions.

🔍 What is Prefix Sum?

The prefix sum of an array is a new array prefix[] where:

prefix[i] = arr[0] + arr[1] + ... + arr[i]

In simple terms, each index holds the cumulative sum from the start to that point.

🧠 Why Use Prefix Sum?

Prefix Sum is useful when you’re asked to compute sum of elements in a subarray multiple times efficiently.

Instead of recalculating the sum for every query, you precompute the prefix sum and answer each query in O(1).

🐢 Brute Force Approach (Naive)

❌ Time Complexity: O(N * Q)

For each query, you iterate over the subarray and calculate the sum.

cpp
int rangeSum(vector<int>& arr, int l, int r) {
    int sum = 0;
    for (int i = l; i <= r; i++) {
        sum += arr[i];
    }
    return sum;
}

⚡ Optimized Approach using Prefix Sum

✅ Time Complexity: O(N) preprocessing + O(1) per query
📘 Formula:
`prefix[0] = arr[0]

prefix[i] = prefix[i-1] + arr[i]

sum of range (l, r) = prefix[r] - prefix[l-1]`


cpp
#include <iostream>
#include <vector>
using namespace std;

class PrefixSum {
public:
    vector<int> computePrefixSum(vector<int>& arr) {
        vector<int> prefix(arr.size());
        prefix[0] = arr[0];

        for (int i = 1; i < arr.size(); i++) {
            prefix[i] = prefix[i - 1] + arr[i];
        }

        return prefix;
    }

    int rangeSum(vector<int>& prefix, int l, int r) {
        if (l == 0) return prefix[r];
        return prefix[r] - prefix[l - 1];
    }
};

int main() {
    vector<int> arr = {2, 4, 6, 8, 10};
    PrefixSum ps;
    vector<int> prefix = ps.computePrefixSum(arr);

    cout << "Sum of elements from index 1 to 3: "
         << ps.rangeSum(prefix, 1, 3) << endl; // Output: 18

    return 0;
}

📊 Time & Space Complexity

Operation Time Complexity Space Complexity
Brute Force Query O(N) O(1)
Prefix Preprocess O(N) O(N)
Prefix Query O(1) O(N)

💎 Real Use Cases of Prefix Sum

Count number of subarrays with a given sum
Range sum queries
2D Prefix Sum (matrix)
Sliding window enhancements
Difference arrays (range update queries)

🧪 Example Problem

Problem: Given an array arr[], and multiple queries of the form (L, R), compute the sum of elements from index L to R.

Input: arr = [1, 3, 2, 5, 4] Queries: (1, 3) => 3+2+5 = 10 (0, 4) => 1+3+2+5+4 = 15

Using prefix sum: Precompute prefix array once, and answer in O(1) for each query.

📦 GitHub Repository
🌟 Check out the full repository with all problems solved using Prefix Sum in C++ here:
👉 My GitHub DSA Repository - Prefix Sum

Maximum sum rectangle in a 2D matrix.

M Umair Ullah — Fri, 25 Jul 2025 07:55:48 +0000

Problem Statement

Given a 2D matrix of integers, find the maximum sum rectangle within the matrix using the prefix sum technique.

Example
Input:

matrix = [ [ 1, 2, -1, -4, -20], [-8, -3, 4, 2, 1], [ 3, 8, 10, 1, 3], [-4, -1, 1, 7, -6] ]
Output:

29

Approach (2D Prefix Sum + Submatrix Sum Calculation)

Key Idea:
Construct a 2D prefix sum matrix, where prefix[i][j] represents the sum of all elements in the submatrix from (0,0) to (i,j).

For any submatrix (r1, c1) to (r2, c2), the sum can be found in O(1) using the prefix matrix:

submatrix_sum = prefix[r2][c2] - prefix[r1-1][c2] - prefix[r2][c1-1] + prefix[r1-1][c1-1]
Iterate over all pairs of (r1, r2) and (c1, c2) to find the maximum sum submatrix.

Steps:

Build a 2D prefix sum matrix in O(rows × cols).
For every pair of top-left (r1, c1) and bottom-right (r2, c2) corners, calculate the submatrix sum using the prefix matrix.
Keep track of the maximum sum found.

C++ Code (Prefix Sum)


#include <bits/stdc++.h>
using namespace std;

int maxSumRectanglePrefix(vector<vector<int>>& matrix) {
    int rows = matrix.size();
    int cols = matrix[0].size();

    // Build prefix sum matrix
    vector<vector<int>> prefix(rows + 1, vector<int>(cols + 1, 0));
    for (int i = 1; i <= rows; i++) {
        for (int j = 1; j <= cols; j++) {
            prefix[i][j] = matrix[i-1][j-1] 
                         + prefix[i-1][j] 
                         + prefix[i][j-1] 
                         - prefix[i-1][j-1];
        }
    }

    int maxSum = INT_MIN;

    // Iterate over all submatrices
    for (int r1 = 1; r1 <= rows; r1++) {
        for (int c1 = 1; c1 <= cols; c1++) {
            for (int r2 = r1; r2 <= rows; r2++) {
                for (int c2 = c1; c2 <= cols; c2++) {
                    int currSum = prefix[r2][c2]
                                - prefix[r1-1][c2]
                                - prefix[r2][c1-1]
                                + prefix[r1-1][c1-1];
                    maxSum = max(maxSum, currSum);
                }
            }
        }
    }
    return maxSum;
}

int main() {
    vector<vector<int>> matrix = {
        { 1,  2, -1, -4, -20},
        {-8, -3,  4,  2,   1},
        { 3,  8, 10,  1,   3},
        {-4, -1,  1,  7,  -6}
    };
    cout << "Maximum Sum Rectangle = " << maxSumRectanglePrefix(matrix) << endl;
    return 0;
}

Complexity Analysis

Time Complexity: O(rows² × cols²) (because we consider all submatrices).

Space Complexity: O(rows × cols) (for the prefix matrix).

Open Source Contribution

I am building an open-source repository of DSA solutions in C++, organized algorithm-wise for easier learning.
Feel free to explore, star ⭐, and contribute to my repository:
👉 DSA in C++ – GitHub Repository

LC:370 Range Addition.

M Umair Ullah — Fri, 25 Jul 2025 07:44:58 +0000

Problem Statement

You are given an integer n and an array of m update operations, where each update operation is represented as a triplet:

[startIndex, endIndex, inc].

Initially, you have an array nums of length n filled with 0.

For each update [startIndex, endIndex, inc], add inc to each element of nums in the range startIndex <= i <= endIndex.

Return the final nums array after applying all the operations.

Example
Input:

n = 5 updates = [[1, 3, 2], [2, 4, 3], [0, 2, -2]]

Output:

[-2, 0, 3, 5, 3]

*Explanation:
*
`Start with [0, 0, 0, 0, 0]

Apply [1, 3, 2] → [0, 2, 2, 2, 0]

Apply [2, 4, 3] → [0, 2, 5, 5, 3]

Apply [0, 2, -2] → [-2, 0, 3, 5, 3]`

Approach (Difference Array + Prefix Sum)

A naive approach would update each element in [startIndex..endIndex] individually for every update, resulting in O(m * n) time.

Instead, we use a Difference Array:

For an update [l, r, inc], we do:

diff[l] += inc

diff[r + 1] -= inc (if r + 1 < n)

After all updates, we take the prefix sum of the diff array to construct the final nums.

This reduces the complexity toO(n + m).

C++ Solution Code


#include <bits/stdc++.h>
using namespace std;

vector<int> getModifiedArray(int n, vector<vector<int>>& updates) {
    vector<int> diff(n, 0);

    // Apply difference array updates
    for (auto& u : updates) {
        int start = u[0], end = u[1], val = u[2];
        diff[start] += val;
        if (end + 1 < n) diff[end + 1] -= val;
    }

    // Build final array by taking prefix sums
    vector<int> result(n, 0);
    int runningSum = 0;
    for (int i = 0; i < n; i++) {
        runningSum += diff[i];
        result[i] = runningSum;
    }
    return result;
}

int main() {
    int n = 5;
    vector<vector<int>> updates = {{1, 3, 2}, {2, 4, 3}, {0, 2, -2}};
    vector<int> res = getModifiedArray(n, updates);

    cout << "Final Array: ";
    for (int x : res) cout << x << " ";
    cout << endl;
    return 0;
}

Complexity Analysis

Time Complexity: O(n + m)

Space Complexity: O(n)

Open Source Contribution

Subarray Sum Divisible By K.

M Umair Ullah — Mon, 21 Jul 2025 09:05:38 +0000

🧠 Intuition:

The key insight is that:

If the difference between two prefix sums is divisible by k, then the subarray between those two indices has a sum divisible by k.

This is where modular arithmetic helps:
If prefixSum[j] % k == prefixSum[i] % k, then prefixSum[j] - prefixSum[i] is divisible by k.

🔍 Approach (Prefix Sum + HashMap):

Prefix Sum: Keep a running sum (prefixSum) while iterating through the array.

Modulo Operation: For each prefix sum, compute mod = prefixSum % k.

Normalization: Handle negative remainders by converting them into positive:if (mod < 0) mod += k;

HashMap: Use a map to store frequency of each mod value seen so far.

If the same mod has occurred before, it means a subarray ending at current index has a sum divisible by k.

Count: Increase count by the frequency of the current mod seen before.

Initialization: Start with prefixMap[0] = 1 to handle cases where a subarray from the beginning is divisible by k.

📊 Time and Space Complexity:

Metric Value Explanation
🕒 Time Complexity O(n) Single pass through array
🧠 Space Complexity O(k) Hash map stores at most k unique remainders

✅ Example:

Input:

`nums = [4, 5, 0, -2, -3, 1], k = 5
Prefix sum steps:

Prefix sum = 4 → 4 % 5 = 4

Prefix sum = 9 → 9 % 5 = 4 → Found a match (same mod as before)

Prefix sum = 9 → 9 % 5 = 4 → Another match

Prefix sum = 7 → 7 % 5 = 2

Prefix sum = 4 → 4 % 5 = 4 → More matches!

Prefix sum = 5 → 5 % 5 = 0 → New match`
Answer: 7 valid subarrays.

Code

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
      int cnt = 0, pf = 0;
      unordered_map<int, int>mp;

      mp[0] = 1;

      for(int num : nums){
        pf += num;

        int mod = pf % k;

        if(mod < 0){
            mod += k;
        }

        if(mp.find(mod) != mp.end()){
            cnt += mp[mod];
            mp[mod]++;
        }else{
            mp[mod] = 1;
        }
      }
      return cnt;
    }
};

📁 Organized DSA Repository
I've started a DSA-in-C++ GitHub repository where all problems are sorted algorithm-wise into folders like:

Arrays → Prefix Sum, Sliding Window, Two Pointers
Linked List
HashMap & Sets
Stack & Queues
Trees, Graphs, and more...

📌 This solution belongs to the folder:
https://github.com/UmairDevloper/DSA-in-C-.git

Max Consecutive Ones III

M Umair Ullah — Mon, 21 Jul 2025 09:01:12 +0000

🧠 Intuition:
We are given a binary array

(0s and 1s),
and an integer k which represents the maximum number of 0s we can flip to 1s.
We need to find the maximum number of consecutive 1s in the array if we are allowed to flip at most k 0s.

This is a sliding window problem. The idea is to maintain a window [left, right] such that at most k zeros are in the window. As we expand the window to the right, if the count of zeros exceeds k, we shrink it from the left until we have at most k zeros again.

🔍 Approach (Using Sliding Window):
Initialize two pointers: left = 0 and right = 0, and a variable zeros = 0 to count the number of 0s in the current window.

Start expanding the window by moving right:

If nums[right] == 0, increment zeros.

While zeros > k, shrink the window from the left:

If nums[left] == 0, decrement zeros.

Move left++.
At each step, calculate the window length: right - left + 1 and track the maximum.

Complexity
Time complexity:
O(n)

Space complexity:
O(1)

Code

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
       int n = nums.size();
       int left = 0;

       for(int right = 0;right<n;right++){
        if(nums[right] == 0){
            k--;
        }

        if(k < 0){
            if(nums[left] == 0){
                k++;
            }
            left++;
        }
       }

       return n - left;
    }
};

📁 Organized DSA Repository
I've started a DSA-in-C++ GitHub repository where all problems are sorted algorithm-wise into folders like:

Arrays → Prefix Sum, Sliding Window, Two Pointers
Linked List
HashMap & Sets
Stack & Queues
Trees, Graphs, and more...

📌 This solution belongs to the folder: https://github.com/UmairDevloper/DSA-in-C-.git