Two Pointers – Simplifying Subarrays and Strings the Smart Way

Hey Coders!

Today, we’ll break down a super useful technique in competitive programming: Two Pointers. It’s often used for problems involving subarrays, substrings, or sorted arrays where you need to optimize over indices without brute force.

Let’s go through a classic-style problem, explaining the idea, giving a dry run.

Problem Statement

You are given an array arr of length n and an integer k.
Find the number of distinct subarrays where the sum of elements is less than or equal to k.

Constraints: - 1 <= n <= 10^5 - 1 <= arr[i] <= 10^4 - 1 <= k <= 10^9

Intuition

Brute force using nested loops to calculate all subarrays and check their sum would result in O(n^2) time, which is too slow.

But we can notice something important: - All array elements are positive. - This means: if we increase the window size (i.e., the right pointer), the sum increases or stays the same. - So if the sum exceeds k, we can safely move the left pointer to reduce it.

This is the perfect setup for Two Pointers / Sliding Window.

Approach

1. Initialize two pointers: left = 0 and right = 0.
2. Maintain current_sum of elements between left and right.
3. For each right:

• Add arr[right] to current_sum.
• While current_sum > k, subtract arr[left] and move left forward.
• All subarrays ending at right and starting from left to right are valid. So we add (right - left + 1) to the answer.

This runs in O(n) time since each pointer moves at most n times.

Dry Run

Let’s say:
arr = [1, 2, 1], k = 3

• right = 0: sum = 1 → valid → subarrays: [1] → count += 1
• right = 1: sum = 3 → valid → subarrays: [1,2], [2] → count += 2
• right = 2: sum = 4 → remove arr[0]=1 → sum=3 → valid
  → subarrays: [2,1], [1] → count += 2

Total = 1 + 2 + 2 = 5

Binary Search on Answer – The Hidden Weapon in Competitive Programming

Hey Coders!

If you've ever struggled with problems where the constraints feel too large for brute force, yet too structured for standard binary search, you might be missing one powerful trick in your toolkit: Binary Search on Answer.

Problem Statement

You are given n books with pages[i] pages each. You want to distribute these books among k students such that:

• Each student gets contiguous books.
• The maximum number of pages assigned to a student is minimized.

Find the minimum value of the maximum pages that can be assigned to any student.

Constraints: - 1 <= n <= 10^5 - 1 <= pages[i] <= 10^4 - 1 <= k <= n

Intuition

At first glance, this seems greedy or DP. But notice the phrase "minimize the maximum" — this is a strong hint towards Binary Search on Answer.

Let’s understand what we are trying to minimize:
We want to minimize max_pages, i.e., the maximum number of pages assigned to a student.

Suppose we guess a value of max_pages = X.
Now, we try to check if we can assign books such that no student gets more than X pages. If yes, we try a smaller value. If not, we increase X.

This forms a monotonic function: - If X works, then all values greater than X also work.
- If X doesn’t work, all values smaller than X won’t work.

Approach

1. Define search space:

• low = max(pages[i]) (no student can get fewer than the largest book)
• high = sum(pages[i]) (one student takes all)

1. Binary Search:

• For mid = (low + high)/2, check if it's feasible to allocate books with max pages = mid.
• If yes, try smaller value (high = mid - 1)
• If not, try larger value (low = mid + 1)

1. Feasibility Check: Use greedy allocation:

• Keep assigning books to current student until adding one more exceeds mid.
• Then assign to next student.
• If we need more than k students, it’s not feasible.

Dry Run

Let’s say:
pages = [10, 20, 30, 40], k = 2

• Try mid = 60:
• Student 1: 10+20+30 = 60
• Student 2: 40
  → Works

• Try mid = 50:

• Student 1: 10+20 = 30
• Student 2: 30
• Student 3: 40
  → Not valid

So the answer lies between 51 and 60 → binary search continues.