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