Time and Space Complexity in DSA

🚀 Day 109 DSA Problem Solving 📌 Problem Solved: Maximum Distance Between a Pair of Values 💡 Level: Medium 🧠 Problem Idea Given two non-increasing arrays, find the maximum distance (j - i) such that: i ≤ j nums1[i] ≤ nums2[j] 🔍 Key Learning Today reinforced a powerful pattern: 👉 When arrays are sorted, always think about Two Pointers before brute force. ⚙️ Approach Used Used Two Pointers (i, j) If condition satisfies → expand j to maximize distance Else → move i to find a smaller value ⏱ Time Complexity O(n + m) ✅ (No nested loops, super efficient) 💭 Real Journey Behind the Solution Initially, I thought about checking all pairs (brute force), but that would lead to TLE. Then I noticed both arrays are non-increasing, which unlocked the two-pointer optimization. This is a reminder that: 👉 Observing constraints carefully can completely change the approach. 📈 Concepts Practiced Two Pointers Greedy Thinking Array Traversal Optimization 🔥 Takeaway Not every problem needs complex logic—sometimes the smartest solution is just about moving pointers wisely. #Day109 #DSAJourney #LeetCode #Coding #Java #ProblemSolving

Day 38 of My DSA Journey Today I solved LeetCode 152 – Maximum Product Subarray on LeetCode. 📌 Problem Given an integer array nums, find the contiguous subarray that has the largest product, and return that product. Example: Input: [2,3,-2,4] Output: 6 → subarray [2,3] 🧠 Approach – Dynamic Programming (Tracking Max & Min) This problem is tricky because of negative numbers. Key Idea: • At each index, we maintain: maxProduct → maximum product ending at current index minProduct → minimum product ending at current index 👉 Why min? Because a negative number can turn a small (negative) product into a large positive one. Steps I followed: • Initialize maxProduct, minProduct, and ans with the first element • Traverse the array from left to right • If the current number is negative → swap max and min • Update: maxProduct = max(current, current × maxProduct) minProduct = min(current, current × minProduct) • Update the final answer using maxProduct ⏱ Time Complexity: O(n) — Single pass through the array 📦 Space Complexity: O(1) — No extra space used 💡 Key Learnings ✔ Handling negative numbers in product problems ✔ Using dynamic programming with state tracking ✔ Understanding why tracking both max & min is important This is one of those problems that looks simple but tests deep understanding of edge cases 🚀 Consistency continues — leveling up every day 💪 #100DaysOfCode #DSA #DynamicProgramming #Arrays #LeetCode #Java #ProblemSolving #CodingJourney #DeveloperJourney #Programming #SoftwareEngineering

🧩 𝗦𝘁𝗼𝗽 𝗦𝗲𝗮𝗿𝗰𝗵𝗶𝗻𝗴 𝗥𝗲𝗰𝘁𝗮𝗻𝗴𝗹𝗲𝘀: 𝗧𝗵𝗲 𝗛𝗶𝘀𝘁𝗼𝗴𝗿𝗮𝗺 𝗠𝗶𝗻𝗱𝘀𝗲𝘁 𝗧𝗵𝗮𝘁 𝗦𝗼𝗹𝘃𝗲𝘀 𝗧𝗵𝗶𝘀 𝗠𝗮𝘁𝗿𝗶𝘅 𝗜𝗻𝘁𝗲𝗿𝘃𝗶𝗲𝘄 𝗣𝗿𝗼𝗯𝗹𝗲𝗺 Solved an interesting problem today on 𝗟𝗲𝗲𝘁𝗖𝗼𝗱𝗲: 𝗙𝗶𝗻𝗱 𝘁𝗵𝗲 𝗮𝗿𝗲𝗮 𝗼𝗳 𝘁𝗵𝗲 𝗹𝗮𝗿𝗴𝗲𝘀𝘁 𝗿𝗲𝗰𝘁𝗮𝗻𝗴𝗹𝗲 𝗰𝗼𝗻𝘁𝗮𝗶𝗻𝗶𝗻𝗴 𝗼𝗻𝗹𝘆 𝟭’𝘀 𝗶𝗻 𝗮 𝗯𝗶𝗻𝗮𝗿𝘆 𝗺𝗮𝘁𝗿𝗶𝘅. At first glance, this looks like a classic 𝟮𝗗 𝗿𝗲𝗰𝘁𝗮𝗻𝗴𝗹𝗲 𝘀𝗲𝗮𝗿𝗰𝗵. But the elegant solution doesn’t search rectangles at all. It 𝗯𝘂𝗶𝗹𝗱𝘀 𝘁𝗵𝗲𝗺 𝘃𝗲𝗿𝘁𝗶𝗰𝗮𝗹𝗹𝘆. 🔄 𝗥𝗼𝘄 𝗯𝘆 𝗥𝗼𝘄 𝗧𝗿𝗮𝗻𝘀𝗳𝗼𝗿𝗺𝗮𝘁𝗶𝗼𝗻 For each row, treat the matrix like this: 1. ‘1’ → increase the column height 2. ‘0’ → reset the column height to 0 After processing a row, you don’t see a matrix anymore. You see a histogram. And now the question becomes: What’s the largest rectangle in this histogram? 🧠 𝗧𝗵𝗲 𝗖𝗹𝗲𝘃𝗲𝗿 𝗧𝘄𝗶𝘀𝘁 Instead of the usual stack approach, maintain three arrays: heights[] → current bar heights leftBoundaries[] → how far left this bar can extend rightBoundaries[] → how far right this bar can extend Two linear scans per row set these boundaries precisely. 📐 𝗔𝗿𝗲𝗮 𝗖𝗼𝗺𝗽𝘂𝘁𝗮𝘁𝗶𝗼𝗻 For every column: width = rightBoundaries[j] - leftBoundaries[j] area = heights[j] * width Update the maximum. Move to the next row. Repeat. 💡 𝗪𝗵𝘆 𝘁𝗵𝗶𝘀 𝘄𝗼𝗿𝗸𝘀 𝗯𝗲𝗮𝘂𝘁𝗶𝗳𝘂𝗹𝗹𝘆 Because for every row, we already know: 1. Continuous height of 1’s above 2. Maximum width possible at that height So we compute the best rectangle in constant time per column. ⚙️ 𝗖𝗼𝗺𝗽𝗹𝗲𝘅𝗶𝘁𝘆 Time: O(rows × cols) Space: O(cols) Optimal. Clean. Elegant. ✨ 𝗧𝗮𝗸𝗲𝗮𝘄𝗮𝘆 Sometimes the best way to solve a 2D problem is to 𝘀𝘁𝗼𝗽 𝘁𝗵𝗶𝗻𝗸𝗶𝗻𝗴 𝗶𝗻 𝟮𝗗. #Algorithms #DataStructures #LeetCode #Java #CodingInterview #InterviewPrep #DSA #ProblemSolving #CodingLife #Developers #SoftwareEngineer #TechInterview #Programming #LearnToCode #CodeNewbie #CompetitiveProgramming #100DaysOfCode #Debugging #Optimization #LogicBuilding #STEM

🧱 𝗜 𝗦𝗼𝗹𝘃𝗲𝗱 𝗮 “𝗩𝗶𝘀𝘂𝗮𝗹” 𝗣𝗿𝗼𝗯𝗹𝗲𝗺 𝗨𝘀𝗶𝗻𝗴 𝗢𝗻𝗹𝘆 𝗮 𝗦𝘁𝗮𝗰𝗸 — 𝗡𝗼 𝗚𝗲𝗼𝗺𝗲𝘁𝗿𝘆 𝗡𝗲𝗲𝗱𝗲𝗱 Today’s problem looked visual and innocent: 𝗚𝗶𝘃𝗲𝗻 𝗯𝗮𝗿 𝗵𝗲𝗶𝗴𝗵𝘁𝘀 𝗼𝗳 𝗮 𝗵𝗶𝘀𝘁𝗼𝗴𝗿𝗮𝗺 (𝘄𝗶𝗱𝘁𝗵 = 𝟭), 𝗳𝗶𝗻𝗱 𝘁𝗵𝗲 𝗹𝗮𝗿𝗴𝗲𝘀𝘁 𝗿𝗲𝗰𝘁𝗮𝗻𝗴𝗹𝗲 𝗮𝗿𝗲𝗮. This is the classic problem from 𝗟𝗲𝗲𝘁𝗖𝗼𝗱𝗲 — and it’s a beautiful lesson in how 𝗺𝗼𝗻𝗼𝘁𝗼𝗻𝗶𝗰 𝘀𝘁𝗮𝗰𝗸𝘀 𝗰𝗼𝗻𝘃𝗲𝗿𝘁 𝗴𝗲𝗼𝗺𝗲𝘁𝗿𝘆 𝗶𝗻𝘁𝗼 𝗶𝗻𝗱𝗶𝗰𝗲𝘀. 🧠 𝗧𝗵𝗲 𝗡𝗮𝗶𝘃𝗲 𝗧𝗵𝗼𝘂𝗴𝗵𝘁 (𝗮𝗻𝗱 𝘄𝗵𝘆 𝗶𝘁 𝗳𝗮𝗶𝗹𝘀) For every bar i, try expanding left and right until you hit a smaller bar. That’s O(n) per index -> O(n²). Too slow for n=10^5. So the real question becomes: For each bar, how far can it extend without hitting a smaller height? That is the entire problem. 💡 𝗞𝗲𝘆 𝗜𝗱𝗲𝗮 — 𝗡𝗲𝗮𝗿𝗲𝘀𝘁 𝗦𝗺𝗮𝗹𝗹𝗲𝗿 𝗘𝗹𝗲𝗺𝗲𝗻𝘁𝘀 For every index i: 1. Find the first smaller bar on the left 2. Find the first smaller bar on the right A monotonic increasing stack gives both in linear time. ▶️ 𝗟𝗲𝗳𝘁 𝗦𝗰𝗮𝗻 (𝗟 -> 𝗥) Pop until the top is strictly smaller. That index defines the left boundary. ◀️ 𝗥𝗶𝗴𝗵𝘁 𝗦𝗰𝗮𝗻 (𝗥 -> 𝗟) Same logic to get the right boundary. Now each bar knows the exact range where it is the minimum. ⏱️ 𝗖𝗼𝗺𝗽𝗹𝗲𝘅𝗶𝘁𝘆 Each index pushed/popped once → O(n) Space → O(n) ✨ 𝗟𝗲𝗮𝗿𝗻𝗶𝗻𝗴𝘀 1. “Nearest smaller element” is a powerful pattern 2. Monotonic stacks turn nested loops into linear scans 3. Think: If this bar is the minimum, how wide can the rectangle be? A visual problem, solved with clean stack discipline. #DataStructures #Algorithms #MonotonicStack #Java #ProblemSolving #CodingInterview #Stack #DSA #LeetCode #Coding #Programmer #SoftwareEngineer #InterviewPrep #CompetitiveProgramming #100DaysOfCode #Tech #Learning #ProblemSolvingSkills

Code has always been a medium to express logic. And as such, it is never been the skill that defines a SWE. I could write simple Python programs when I was 8, and I am no prodigy. What differentiates a replaceable "programmer" from an engineer is their ability to think and architect a system. That will get EVEN MORE valuable with AI because companies will start pushing out softwares at a scale never seen before. If a good engineer (powered by Claude Code) can deliver 10x the output they did before, why would a company reduce its headcount of engineers? If they do, then their competitors could hire more skilled engineers and outcompete them. All that changes is the level of calibre that an engineer needs to enter the field, and I am all for it.

🚀 DSA Series #1 — Closest Target in Circular Array Today I solved an interesting problem involving circular arrays + shortest distance logic. 🧠 Key Insight: Instead of simulating movement, we can compute distance using modulo. 👉 Forward distance: (i - start + n) % n 👉 Backward distance: (start - i + n) % n Take the minimum of both — done in O(n) time ⚡ 📌 Complexity: O(n) time | O(1) space 💡 Learning: Circular problems often look tricky, but math simplifies everything. 🔥 Building consistency with: #DSA #Java #Coding #PlacementPreparation #100DaysOfCode If you’re on the same path, let’s connect and grow 🤝

🚀 Second Largest Element Problem Sometimes the simplest problems teach the most important lessons 💡 🧩 Problem: Find the second largest element in an array 👉 If it doesn’t exist, return -1 ⚡ My Approach: Instead of sorting (which costs more time ⏳), I used: ✔ First pass → Find the largest element ✔ Second pass → Find the second largest (≠ largest) 📊 Complexity: ⏱ Time: O(n) 📦 Space: O(1) 🧠 Key Learnings: ✔ Avoid unnecessary sorting 🚫 ✔ Think in terms of optimization first ✔ Edge cases matter (e.g., [10,10,10]) 🔥 Result: ✅ 1120 / 1120 Test Cases Passed 🎯 100% Accuracy #leetcode #dsa #java #arrays #algorithms #coding #programming #developers #softwareengineering #problemSolving #tech #codingjourney #100daysofcode

𝗢𝗿𝗱𝗲𝗿 𝗱𝗼𝗲𝘀𝗻’𝘁 𝗮𝗹𝘄𝗮𝘆𝘀 𝗰𝗼𝗺𝗲 𝗳𝗿𝗼𝗺 𝘀𝗼𝗿𝘁𝗶𝗻𝗴. Sometimes it grows from structure. 📚 Today I built 𝗦𝗺𝗮𝗿𝘁 𝗟𝗶𝗯𝗿𝗮𝗿𝘆 𝗕𝗼𝗼𝗸 𝗢𝗿𝗴𝗮𝗻𝗶𝘇𝗲𝗿 using 𝗧𝗿𝗲𝗲 𝗦𝗼𝗿𝘁 in 𝗝𝗮𝘃𝗮 𝗦𝘄𝗶𝗻𝗴 𝗚𝗨𝗜. 📌 Real-world idea: When books arrive in random order, instead of repeatedly comparing every title, the system: ✔ inserts books into a Binary Search Tree ✔ places smaller titles left and larger titles right ✔ uses In-Order Traversal to reveal sorted order ✔ organizes the catalog intelligently That is exactly how 𝗧𝗿𝗲𝗲 𝗦𝗼𝗿𝘁 works. 🚀 Today’s Build: 𝗦𝗺𝗮𝗿𝘁 𝗟𝗶𝗯𝗿𝗮𝗿𝘆 𝗕𝗼𝗼𝗸 𝗢𝗿𝗴𝗮𝗻𝗶𝘇𝗲𝗿 – 𝗧𝗿𝗲𝗲 𝗦𝗼𝗿𝘁 𝗶𝗻 𝗥𝗲𝗮𝗹 𝗟𝗶𝗳𝗲 Because 𝗗𝗦𝗔 becomes powerful when it solves systems people already use every day. I’m continuing my mission to turn algorithms into practical products, one project at a time. Which algorithm should I transform next? #Java #DSA #TreeSort #BinarySearchTree #Algorithms #JavaSwing #CodingProjects #Programming #SoftwareEngineer #LibraryManagement #LearnCoding #DataStructures #BuildInPublic #KapilNarula #TechProjects

=> Day 20/90 DSA Journey Solved: Count Odd Numbers in an Interval (LeetCode 1523) Instead of using loops, I applied a simple mathematical formula to achieve an O(1) solution. 🔹 Key Idea: Count of odd numbers between low and high can be calculated directly using: -> ((high + 1) / 2) - (low / 2) 🔹 Why this works: -> It efficiently counts odds up to high and subtracts odds before low. 🔹 Example: Input: low = 3, high = 7 Output: 3 (Odd numbers → 3, 5, 7) -> Time Complexity: O(1) -> Space Complexity: O(1) #Java #DSA #LeetCode #ProblemSolving #Coding #Optimization

💡 Back to Basics: A Pointer Lesson I Had to Relearn Today I hit one of those humbling moments every developer eventually faces. While working on a memory-mapped project, I got stuck calculating offsets between two memory blocks. I tried straightforward pointer subtraction—and then it clicked: 👉 Pointers aren’t just addresses. They carry context. Back in college, I knew this. Somewhere along the way, I forgot. --- 🧠 The Realization In C, pointer arithmetic is only valid when both pointers belong to the same array (object). ✔️ This is valid: &array1[5] - &array1[0]; // Result: 5 ❌ This is undefined behavior: &array2[0] - &array1[0]; Even if both arrays sit next to each other in memory, the compiler treats them as completely separate worlds. It’s not just about addresses—it’s about where those pointers came from. --- 🛠️ The Practical Workaround When you do need raw memory distance, you can strip away that context: int arr1[10]; int arr2[10]; // Undefined: // long dist = &arr2[0] - &arr1[0]; // Defined: long byte_dist = (char*)&arr2[0] - (char*)&arr1[0]; Casting to "char*" (or "uintptr_t") tells the compiler: «“Treat this as raw bytes, not structured objects.”» --- 🚀 Takeaway Sometimes the hardest bugs aren’t about complex systems—they’re about fundamentals we think we’ve already mastered. C has a way of reminding you: «You’re never really above the basics.» --- Curious—have you had a moment where a “simple” concept turned into a debugging rabbit hole? 👇 #CProgramming #SoftwareEngineering #EmbeddedSystems #MemoryManagement #LearningEveryday #CodingLife