Vicky Sharma

🧵 Day 100 of my #100DaysOfCode challenge 🚀 Today I worked on the Largest Rectangle in Histogram problem. Sharing the approach I used 👇

🔍 Problem Insight: Given heights of histogram bars, find the maximum rectangular area that can be formed using contiguous bars. Brute force works… but there’s a much better way 👀

🐢 Brute Force Approach (O(n²)) For every bar: → Extend to the right → Keep track of minimum height → Compute area for each possible width ✔️ Simple ❌ Too slow for large inputs

⚡ Optimal Approach — Monotonic Stack (O(n)) Key idea: For each bar, find • Previous Smaller Element (left boundary) • Next Smaller Element (right boundary) These boundaries decide how far the bar can expand.

📐 Area Formula: For every index i width = right[i] - left[i] - 1 area = height[i] * width Track the maximum area across all bars. Each bar is pushed & popped only once → O(n) time 🔥

🧠 Why Stack Works? The monotonic stack keeps indices in increasing height order. As soon as a smaller bar appears, we finalize the area for taller bars. Clean logic + high efficiency ✨

✅ This problem reinforced how powerful monotonic stacks are for: • Histogram problems • Stock Span • Next/Previous Greater or Smaller • Sliding Window variations

📌 Full implementation & notes available here 👇 🔗 GitHub Repo: github.com/Sharmavicky/Ds… #DSA #CodingJourney #Cplusplus #BuildInPublic

🧵 Day 99 of my #100DaysOfCode challenge 🚀 Today I solved the 3Sum Closest problem using an optimized approach. Sharing my thought process below 👇

🔍 Problem Overview Given an array of integers and a target value, find three numbers whose sum is closest to the target. The goal is accuracy + efficiency ⚡

❌ Brute Force Idea Try all possible triplets and compare their sums with the target. This works, but it takes O(n³) time — not practical for large inputs.

✅ Optimized Approach (Two Pointers) To improve : 1️⃣ Sort the array 2️⃣ Fix one element 3️⃣ Use two pointers (left & right) for the remaining part 4️⃣ Move pointers based on whether the current sum is smaller or larger than the target This reduces the time complexity to O(n²) 🚀

🧠 Key Insight Sorting helps us intelligently move pointers instead of checking every combination. At each step, we update the closest sum based on the absolute difference from the target. Simple logic → big optimization 🔥

📌 Final Thoughts This problem is a great example of how ➡️ sorting + two pointers ➡️ can drastically improve performance. Another solid pattern added to my DSA toolkit 💪

📂 Full solution with implementation is available on my GitHub 👇 🔗 GitHub Repo: github.com/Sharmavicky/Ds… #100DaysOfCode #DSA #cpp #CodingJourney #BuildInPublic

🧵 Day 98 of my #100DaysOfCode challenge 🚀 Today I worked on the Zigzag Conversion problem and focused on understanding the pattern simulation approach. Here’s the idea 👇

🔍 Problem in short: Given a string and number of rows, arrange characters in a zigzag pattern and then read row-wise. Example pattern (numRows = 3): Row 0 → going down Row 1 → middle Row 2 → going up

🧠 Key Insight: Instead of building the zigzag visually, we can simulate the movement. ✔️ Maintain a currentRow ✔️ Use a direction flag (goingDown) ✔️ Reverse direction at top row (0) and bottom row (numRows − 1)

⚙️ Approach: 1️⃣ Create a list of strings for each row 2️⃣ Traverse the input string character by character 3️⃣ Add each character to the current row 4️⃣ Change direction when hitting first or last row 5️⃣ Concatenate all rows to get the final result Efficient & clean 💡

📈 Why this works well: • Avoids complex index math • No extra 2D matrix needed • Time Complexity → O(n) • Space Complexity → O(n) A great example of pattern simulation ✨