Crack Hard Problems: Stacks & Two Pointers

📌 Today’s Progress

First time facing a hard problem—and honestly, after solving it, the solution felt much simpler than expected.
Key realization: Understanding the question before attempting to solve it makes a huge difference.
Covered Stack, Two Pointers, and Sliding Window problems today.
Took quite a few breaks, but overall, it was a pretty productive day!

📝 Problems Solved Today

Stack

1️⃣ Daily Temperatures (Medium)
💡 Concept: Monotonic Stack
🔍 Approach:

Used a decreasing stack to track temperatures and find how many days until a warmer temperature.
If the current temperature is higher than the top of the stack, pop elements and calculate the difference.
⏳ Time Complexity: O(n)

2️⃣ Car Fleet (Medium)
💡 Concept: Stack + Sorting
🔍 Approach:

Sorted cars by position and iterated from the back, maintaining a stack to track the fleets.
If a car reaches the destination after another, it forms a new fleet.
⏳ Time Complexity: O(n log n)

3️⃣ Largest Rectangle in Histogram (Hard)
💡 Concept: Monotonic Stack
🔍 Approach:

Used a stack to track bar heights, calculating max areas whenever we encountered a smaller bar.
Popped elements from the stack to determine the widest possible rectangle.
⏳ Time Complexity: O(n)

Two Pointers

4️⃣ Valid Palindrome (Easy)
💡 Concept: Two Pointers
🔍 Approach:

Filtered out non-alphanumeric characters and used two pointers to compare characters from both ends.
⏳ Time Complexity: O(n)

5️⃣ Two Sum II - Sorted Array (Medium)
💡 Concept: Two Pointers
🔍 Approach:

Used two pointers, starting at both ends, moving them closer based on sum comparison with the target.
⏳ Time Complexity: O(n)

6️⃣ 3Sum (Medium)
💡 Concept: Sorting + Two Pointers
🔍 Approach:

Sorted the array and used a fixed pointer with two moving pointers to find unique triplets summing to zero.
⏳ Time Complexity: O(n²)

7️⃣ Container With Most Water (Medium)
💡 Concept: Two Pointers
🔍 Approach:

Used two pointers moving inward to maximize water storage while maintaining the widest possible width.
⏳ Time Complexity: O(n)

8️⃣ Trapping Rain Water (Hard)
💡 Concept: Two Pointers
🔍 Approach:

Maintained two pointers tracking the max left and right boundaries to calculate trapped water efficiently.
⏳ Time Complexity: O(n)

Sliding Window

9️⃣ Best Time to Buy and Sell Stock (Easy)
💡 Concept: Sliding Window (Optimized as a One-Pass Solution)
🔍 Approach:

Used a single pass to track the minimum price so far and update the maximum profit dynamically.
The key was to keep an eye on the lowest buying price and sell whenever we found a higher price that increased profit.
⏳ Time Complexity: O(n)

🔟 Longest Substring Without Repeating Characters (Medium)
💡 Concept: Sliding Window + HashSet
🔍 Approach:

Used a moving window and a HashSet to track unique characters.
If a duplicate was found, moved the left pointer until uniqueness was restored.
⏳ Time Complexity: O(n)

🚀 Takeaways

🔹 Tackling a hard problem gave a huge confidence boost. It was intimidating at first, but once broken down, the logic clicked.
🔹 Recognizing problem patterns (stacks, two pointers, sliding window) makes solving easier.
🔹 Breaking down the problem before jumping into code is key. Saves time and avoids confusion.

Even with a few breaks, today was a solid grind! On to the next one. 🔥

Day 6: Cracking My First Hard Problem & Leveling Up with Stacks, Two Pointers & Sliding Window 🚀

Table of contents