Leveling Up on Grid Partition Problem with Frequency Arrays

Day 99: Square Root Decomposition & Prefix Multiplications ⚡ Problem 3655: XOR After Range Multiplication Queries II Yesterday’s brute force approach hit a wall today with a TLE (Time Limit Exceeded). The constraints were significantly tighter, requiring a more sophisticated optimization. The Strategy: Square Root Decomposition To handle the queries efficiently, I split the problem based on the step size k: • Large Steps (k ≥ √N): For large gaps, the number of updates is small enough that direct simulation still works within time limits. • Small Steps (k < √N): This is where the magic happens. For small k, I used a Difference Array technique modified for multiplications. • Modular Inverse & Prefix Products: Instead of updating every index, I marked the start (L) and end (R) of the range. I used modInverse to "cancel out" the multiplication after the range ended. A final prefix product pass (jumping by k) applied all updates in O(N) time. Technical Highlights: • Fermat's Little Theorem: Used modPow(x, MOD - 2) to calculate the modular inverse for division. • Complexity: Reduced the worst-case runtime from O(Q⋅N) to O((Q+N)√N). One day away from 100, but the focus remains on the problem in front of me. Consistency isn't about the destination; it's about the quality of the journey. 🚀 #LeetCode #Java #Algorithms #DataStructures #SquareRootDecomposition #DailyCode

Day 86: Matrix Symmetry & Cyclic Shifts 🔄 Problem 2946: Matrix Similarity After Cyclic Shifts Today’s challenge was about verifying if a matrix stays identical after shifting even rows left and odd rows right by k positions. The Strategy: • Modulo Optimization: Used k %= n to skip redundant full rotations. • Direct Mapping: Instead of shifting elements, I mathematically calculated their new positions. ∘ Even Rows: Compared mat[i][j] with mat[i][(j + k) % n]. ∘ Odd Rows: Compared mat[i][j] with mat[i][(j - k + n) % n]. • Single Pass: Verified similarity in O(M⋅N) time without extra space. Using modular arithmetic to "simulate" movement is a clean, efficient way to handle wrap-around logic without reallocating memory. 🚀 #LeetCode #Java #Algorithms #Matrix #DailyCode

📌 Median of Two Sorted Arrays Platform: LeetCode #4 Difficulty: Hard ⚙️ Approach • Apply binary search on the smaller array for efficiency • Define search space from 0 to n1 • Partition both arrays such that: – Left half contains (n1 + n2 + 1) / 2 elements – Right half contains remaining elements • Identify boundary elements: – l1, l2 → left side elements – r1, r2 → right side elements • Check valid partition: – l1 <= r2 and l2 <= r1 • If valid: – For even length → median = average of max(left) and min(right) – For odd length → median = max(left) • If not valid: – If l1 > r2, move left – Else move right 🧠 Logic Used • Binary Search on partition index • Dividing arrays into balanced halves • Handling edge cases using boundary values • Achieving optimal O(log(min(n1, n2))) time complexity 🔗 GitHub: https://lnkd.in/g_3x55n8 ✅ Day 36 Completed – Revised advanced binary search and partition-based problem. #100DaysOfCode #Java #DSA #ProblemSolving #CodingJourney #Algorithms #DataStructures #LeetCode #CodingPractice #CodeEveryDay #BinarySearch #ArrayProblems

🚀 Day 55 of #100DaysOfCode – Rotate Image Today I worked on an interesting matrix problem: Rotate Image (90° clockwise) 🔄 💡 Key Learning: Instead of using extra space, the challenge is to rotate the matrix in-place. 🧠 Approach I used: 1️⃣ Transpose the matrix (convert rows → columns) 2️⃣ Reverse each row This combination effectively rotates the matrix by 90° clockwise without using extra memory. 📌 Example: Input: [[1,2,3], [4,5,6], [7,8,9]] Output: [[7,4,1], [8,5,2], [9,6,3]] ⚡ Complexity: Time: O(n²) Space: O(1) (in-place) 💻 Implemented in Java and successfully passed all test cases ✅ This problem really helped me strengthen my understanding of matrix manipulation and in-place algorithms. #LeetCode #DataStructures #Java #CodingPractice #ProblemSolving #Algorithms #100DaysOfCode

🚀 Day 8/100 — #100DaysOfLeetCode Another day, another concept unlocked 💻🔥 ✅ Problem Solved: 🔹 LeetCode 73 — Set Matrix Zeroes 💡 Problem Idea: If any element in a matrix is 0, its entire row and column must be converted to 0 — and the challenge is to do this in-place without using extra space. 🧠 Algorithm & Tricks Learned: Instead of using extra arrays, we can use the first row and first column as markers. First pass → mark rows and columns that should become zero. Second pass → update the matrix based on those markers. Carefully handle the first row and first column separately to avoid losing information. ⚡ Key Insight: The matrix itself can act as storage, reducing extra memory usage. 📊 Complexity Analysis: Time Complexity: O(m × n) → traverse matrix twice Space Complexity: O(1) → solved in-place without extra data structures This problem taught me how small optimizations can significantly improve space efficiency. Learning to think beyond brute force every day 🚀 #100DaysOfLeetCode #LeetCode #DSA #MatrixProblems #Algorithms #Java #ProblemSolving #CodingJourney #LearningInPublic

Day 12 of #100DaysOfCode — Sliding Window Today, I worked on the problem “Max Consecutive Ones III” LeetCode. Problem Summary Given a binary array, the goal is to find the maximum number of consecutive 1s if you can flip at most k zeros. Approach At first glance, this problem looks like a brute-force or restart-based problem, but the optimal solution lies in the Sliding Window technique. The key idea is to maintain a window [i, j] such that: The number of zeros in the window does not exceed k Expand the window by moving j Shrink the window by moving i whenever the constraint is violated Instead of restarting the window when the condition breaks, we dynamically adjust it. Key Logic Traverse the array using pointer j Count the number of zeros in the current window If zeros exceed k, move pointer i forward until the window becomes valid again At every step, update the maximum window size Why This Works This approach ensures: Each element is processed at most twice Time Complexity: O(n) Space Complexity: O(1) The most important learning here is understanding how to dynamically adjust the window instead of resetting it, which is a common mistake while applying sliding window techniques. In sliding window problems, always focus on expanding and shrinking the window efficiently rather than restarting the computation. #100DaysOfCode #DSA #SlidingWindow #LeetCode #Java #ProblemSolving #CodingJourney #DataStructures #Algorithms

Day 63/75 — Rotate Array Today’s problem was about rotating an array to the right by k steps. Approach: • Use reversal algorithm for optimal in-place rotation • Reverse entire array • Reverse first k elements • Reverse remaining elements Key logic: k = k % n; reverse(nums, 0, n - 1); reverse(nums, 0, k - 1); reverse(nums, k, n - 1); Time Complexity: O(n) Space Complexity: O(1) A classic array problem that reinforces in-place manipulation techniques. 63/75 🚀 #Day63 #DSA #Arrays #InPlace #Java #Algorithms #LeetCode

🧠 Day 212 — Maximum Distance Between Valid Pairs 📏⚡ Today solved a solid two-pointer optimization problem on sorted arrays. 📌 Problem Goal Given two non-increasing arrays: ✔️ Find indices (i, j) such that ✔️ i ≤ j and nums1[i] ≤ nums2[j] ✔️ Maximize the distance (j - i) 🔹 Core Idea Use two pointers to efficiently explore valid pairs: ✔️ Start both pointers at the beginning ✔️ Expand j to find valid matches ✔️ Move i only when condition breaks 🔹 Key Observation ✔️ Arrays are sorted in non-increasing order → huge advantage ✔️ If nums1[i] > nums2[j], move i forward ✔️ Otherwise, update answer and try expanding j 🧠 Key Learning ✔️ Two-pointer technique works best on sorted data ✔️ Avoid brute force → think in terms of pointer movement ✔️ Maintain valid window while maximizing distance 💡 Big Realization Whenever you see: 👉 “Maximize/minimize distance” 👉 “Sorted arrays” Think: ➡️ Can I solve this using two pointers instead of nested loops? 🚀 Momentum Status: Strong grip on array + pointer patterns. On to Day 213. #DSA #TwoPointers #Arrays #Optimization #LeetCode #Java #CodingJourney #ConsistencyWins

Day 105: Circular Arrays & Shortest Paths 🔄 Problem 2515: Shortest Distance to Target String in a Circular Array Today’s challenge involved finding the minimum steps to reach a target string in a circular array, allowing movement in both directions. The Strategy: • Bidirectional Search: Since the array is circular, the distance can be calculated in two ways: moving forward or moving backward. • Modular Arithmetic: I used (dist + n) % n to handle the wrap-around logic seamlessly, ensuring the index stays within bounds regardless of the direction. • Optimization: By iterating once through the array and comparing the distances for every occurrence of the target, I maintained an O(N) time complexity. Sometimes the most elegant way to handle a "circular" problem is simply embracing the symmetry of the path. 🚀 #LeetCode #Java #Algorithms #ProblemSolving #DailyCode

#100DaysOfCode | Day 2 of my LeetCode challenge. Today’s problem: 1365. How Many Numbers Are Smaller Than the Current Number. While the problem seems simple, it’s a perfect example of how choosing the right data structure can drastically change performance. Here is how I broke it down: 1. The Brute Force Approach The most simple and easy way is to use nested loops to compare every number with every other number. Logic: For each element, loop through the entire array and count smaller values. Time Complexity: O(N^2) Space Complexity: O(N) (to store the result) 2. The Sorting + HashMap Approach A more scalable way is to sort the numbers. In a sorted array, a number's index is equal to the count of numbers smaller than it. Logic: Clone the array, sort it, and store the first occurrence of each number in a HashMap. Time Complexity: O(N log N) (due to sorting) Space Complexity: O(N) (to store the map) Use - Works for any range of numbers (including very large or negative ones). 3. The Frequency Array (Counting Sort Logic) Since the problem constraints were small (0 to 100), this is the most optimized solution. Logic: Count the frequency of each number using an array of size 101, then calculate a running prefix sum. Time Complexity: O(N) (Linear time) Space Complexity: O(1) (The frequency array size is constant) #LeetCode #100DaysOfCode #Java #SoftwareEngineering #DataStructures #Algorithms