🗓 Daily LeetCode Progress – Day 6

Problems Solved:

#42 Trapping Rain Water
#3 Longest Substring Without Repeating Characters

This continues my daily series (Day 6: Sliding Window + Two Pointers). Keeping the streak alive 🚀 — I’ve now solved and documented problems for 6 days straight. My focus today was on mastering two different applications of pointers: one for array water trapping and one for string window expansion.

💡 What I Learned

The two-pointer technique can adapt to very different problems:
- From both ends inward to compute trapped rain water.
- As a sliding window to track unique characters in a substring.
Practiced the importance of updating boundaries carefully (left_max, right_max, and left index).
Saw how optimizing pointer movement avoids unnecessary work and reduces time complexity.

🧩 #42 — Trapping Rain Water

Python (Two Pointers)

class Solution:
    def trap(self, height: List[int]) -> int:
        l, r = 0, len(height) - 1
        left_max = right_max = 0
        water = 0
        while l <= r:
            if height[l] <= height[r]:
                if height[l] >= left_max:
                    left_max = height[l]
                else:
                    water += left_max - height[l]
                l += 1
            else:
                if height[r] >= right_max:
                    right_max = height[r]
                else:
                    water += right_max - height[r]
                r -= 1
        return water

Why it works:
At each step, whichever side has the smaller boundary determines the possible trapped water. We move that pointer inward, updating max values and adding trapped water.

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

C++ (Two Pointers)

class Solution {
public:
    int trap(vector<int>& height) {
        int l = 0, r = (int)height.size() - 1;
        int left_max = 0, right_max = 0;
        int water = 0;
        while (l <= r) {
            if (height[l] <= height[r]) {
                if (height[l] >= left_max) {
                    left_max = height[l];
                } else {
                    water += left_max - height[l];
                }
                l += 1;
            } else {
                if (height[r] >= right_max) {
                    right_max = height[r];
                } else {
                    water += right_max - height[r];
                }
                r -= 1;
            }
        }
        return water;
    }
};

Why it works:
The same min-boundary principle applies. By always moving the smaller side inward, we ensure no trapped water is missed.

🧩 #3 — Longest Substring Without Repeating Characters

Python (Sliding Window)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        last = {}
        left, best = 0, 0
        for right, char in enumerate(s):
            if char in last and last[char] >= left:
                left = last[char] + 1
            last[char] = right
            best = max(best, right - left + 1)
        return best

Why it works:
Keep a window [left..right] that always remains free of duplicates. When a repeat occurs, move left to skip the last occurrence.

Time: O(n)
Space: O(min(n, σ)) where σ = charset size.

C++ (Sliding Window)

class Solution {
public:
    int lengthOfLongestSubstring(const std::string& s) {
        int left = 0, best = 0;
        std::vector<int> last(256, -1);

        for (int right = 0; right < (int)s.size(); ++right) {
            unsigned char ch = s[right];
            if (last[ch] >= left) {
                left = last[ch] + 1;
            }
            last[ch] = right;
            best = std::max(best, right - left + 1);
        }
        return best;
    }
};

Why it works:
A direct application of the sliding window: update left when a duplicate is detected, otherwise expand the window.

📸 Achievements

Trapping Rain Water (Python & C++):

Longest Substring Without Repeating Characters (Python & C++): Substring

📦 Complexity Recap

Trapping Rain Water: O(n) time, O(1) space
Longest Substring Without Repeating Characters: O(n) time, O(σ) space

📣 Join the Journey

Day 6 streak ✅ and counting! I’m solving and documenting problems daily in both Python and C++, highlighting patterns and performance insights. Follow along if you’re into algorithms and efficiency.

Links