Maximizing Graph Stability with Binary Search and DSU

🚀 LeetCode Daily Challenge 🔗 Problem: https://lnkd.in/gWPpdhN8 💡 My thought process: The algorithm goes through each cell in the grid and treats every cell as the top vertex of a rhombus. For every possible size of the rhombus, it calculates the positions of the left, right, and bottom vertices. Before adding up the values, it checks if these vertices stay within the grid boundaries. If any vertex is outside the grid, it’s not possible to create larger rhombuses from that position, so the loop stops. The calculate function finds the border sum of the rhombus. It starts at the top vertex and moves along the four edges: from top to left, left to bottom, bottom to right, and back to top. The traversal moves diagonally across the grid and continues until it reaches the exact target vertex. The condition i != target_row || j != target_col makes sure the loop keeps going until both coordinates match the goal. For each rhombus sum found, the algorithm updates three variables: sum1, sum2, and sum3. These hold the largest, second-largest, and third-largest distinct sums. It skips duplicate sums to store only unique values. The algorithm also handles single-cell rhombuses separately since they represent rhombuses of size zero. Finally, the function returns the largest distinct sum it found. If three exist, it returns all three. If there are fewer distinct sums, it returns only the ones available, listed in descending order. 👉 My Solution: https://lnkd.in/gYi2CDgR If you found this breakdown helpful, feel free to ⭐ the repo or connect with me on LinkedIn 🙂🚀 #️⃣ #leetcode #cpp #dsa #coding #problemsolving #engineering #BDRM #BackendDevWithRahulMaheswari

🚀 LeetCode Daily Challenge 🔗 Problem: https://lnkd.in/gK993p-S 💡 My thought process: The main function, minAbsDiff, goes through all possible top-left positions of the k × k submatrices. For each position (i, j), it calls the helper function solve to find the result for that submatrix and stores it in the answer matrix, which has a size of (m − k + 1) × (n − k + 1). The solve function collects all elements from the k × k submatrix starting at (i, j) and puts them into a set. This automatically sorts the elements and removes duplicates. If the set has only one unique element, the function returns 0 because all values are the same. If there are multiple unique elements, the function goes through the sorted set and calculates the absolute difference between each pair of consecutive elements. Since the set is sorted, the minimum absolute difference will be between adjacent elements. The smallest difference is tracked and returned. The overall time complexity is O((m − k + 1) × (n − k + 1) × k² log(k²)) because each submatrix requires inserting k² elements into a set and iterating through it. The space complexity is O(k²) for storing elements of each submatrix. 👉 My Solution: https://lnkd.in/gj6juuUU If you found this breakdown helpful, feel free to ⭐ the repo or connect with me on LinkedIn 🙂🚀 #️⃣ #leetcode #cpp #dsa #coding #problemsolving #engineering #BDRM #BackendDevWithRahulMaheswari

🚀 LeetCode Daily Challenge 🔗 Problem: https://lnkd.in/gbtaBXYW 💡 My thought process: The algorithm first calculates a normalized shift value using k % n. Shifting a row by its total length, n, returns the original configuration. Therefore, any shift k is the same as k modulo n. Instead of rotating memory physically or creating a temporary matrix, the code uses a virtual mapping strategy. It goes through each cell (i, j) and finds the index of the element that would be in that position after the shift. For even rows (left shift), to find the original value that moves into position j after a left shift, the code looks at the index (j - shift). It manages negative results by wrapping around with an addition of n. For odd rows (right shift), it checks the index (j + shift) % n. The function has a fail-fast mechanism; it returns false right away if it finds the first difference between a cell and its shifted counterpart. 👉 My Solution: https://lnkd.in/g5myRYRj If you found this breakdown helpful, feel free to ⭐ the repo or connect with me on LinkedIn 🙂🚀 #️⃣ #leetcode #cpp #dsa #coding #problemsolving #engineering #BDRM #BackendDevWithRahulMaheswari

🚀 LeetCode Daily Challenge 🔗 Problem: https://lnkd.in/gJUJE-YA 💡 My thought process: The provided code uses a backtracking approach to generate all possible strings of length n that satisfy the happy string condition: no two adjacent characters can be identical. The algorithm builds these strings in lexicographical order by exploring 'a', 'b', and then 'c'. The main logic is in the solve function, which acts as a recursive explorer. It takes the current string and the number of characters left to add. At each step, it tries appending 'a', 'b', and 'c'. Before adding a character, it checks for safety by ensuring that the character is not the same as the last one in the string. This prevents violating the happy constraint. Once a character is added, the function calls itself with n-1 to fill the next position. After finishing that branch of the search, it removes the character to backtrack and try the next alphabetical option. In the getHappyString function, the process starts by launching three separate recursive chains: one with 'a', one with 'b', and one with 'c'. Since the loops and initial calls follow alphabetical order, the allStrings vector is filled with every valid combination in sorted order. Finally, the code checks if the requested index k exists within the total count of generated strings. If k is within bounds, it returns the string at index k-1; otherwise, it returns an empty string. 👉 My Solution: https://lnkd.in/gKDqj84r If you found this breakdown helpful, feel free to ⭐ the repo or connect with me on LinkedIn 🙂🚀 #️⃣ #leetcode #cpp #dsa #coding #problemsolving #engineering #BDRM #BackendDevWithRahulMaheswari

🚀 LeetCode Daily Challenge 🔗 Problem: https://lnkd.in/gVK8xX3p 💡 My thought process: The solution uses a top-down dynamic programming approach with memoization. Each cell stores a pair of values: the maximum product and the minimum product achievable from that cell to the destination. The minimum value is necessary because multiplying two negative numbers can lead to a larger positive result later. The recursive function explores both possible moves—right and down—from the current cell and retrieves their stored results. For each direction, it considers both the maximum and minimum products returned and multiplies them by the current cell’s value. All combinations are evaluated, and the overall maximum and minimum are selected and stored in the DP table for that cell. Memoization ensures that each cell is computed only once, reducing the time complexity to O(m × n). The base case occurs at the bottom-right cell, where both maximum and minimum values equal the cell’s value. Invalid positions return sentinel values to indicate they should not be considered. Finally, the function checks the result from the starting cell. If the maximum product is negative, it returns -1. Otherwise, it returns the result modulo 1e9 + 7. 👉 My Solution: https://lnkd.in/gcKfTVNq If you found this breakdown helpful, feel free to ⭐ the repo or connect with me on LinkedIn 🙂🚀 #️⃣ #leetcode #cpp #dsa #coding #problemsolving #engineering #BDRM #BackendDevWithRahulMaheswari

Spent some time solving 3 really interesting LeetCode contest problems today, and each one reinforced a different core DSA pattern. What I enjoyed most was how these seemingly small problems were actually testing pattern recognition more than implementation. 1) Mirror Frequency Distance This problem was all about symmetry and frequency mapping. Approach That I Used: Count the frequency of each character in the string. Map each character to its mirror counterpart: a ↔ z, b ↔ y 0 ↔ 9, 1 ↔ 8 Iterate through only half the range to avoid double counting. Sum the absolute frequency differences for every mirror pair. 2) Integers With Multiple Sum of Two Cubes This one immediately reminded me of the Ramanujan number (1729) concept. Approach That I Used: Generate all valid cube pairs (a, b) where: a³ + b³ ≤ n Store the frequency of each generated sum in a hashmap. Any number appearing 2+ times has multiple distinct cube representations. Return all such integers in sorted order. 3) Minimum Increments to Maximize Special Indices The most interesting one of the three because it involved DP state compression. & it took me an hour to do this question Approach: Treat every valid index as a candidate peak. Compute the cost required to make it greater than both neighbors. Maintain two rolling states: choose current index as peak skip current index Optimize first for: maximum number of peaks minimum cost among those choices Biggest learning from today: Contest questions often look implementation-heavy, but the real skill lies in identifying the hidden reusable pattern: frequency symmetry pair generation DP The more patterns we recognize, the faster we grow as problem solvers. Consistency is the real game changer. #LeetCode #DSA #DynamicProgramming #CompetitiveProgramming #ProblemSolving #C++ #CodingJourney #SoftwareEngineering

🚀 𝐂𝐨𝐦𝐩𝐞𝐭𝐢𝐭𝐢𝐯𝐞 𝐏𝐫𝐨𝐠𝐫𝐚𝐦𝐦𝐢𝐧𝐠 | 𝐇𝐚𝐬𝐡𝐢𝐧𝐠 + 𝐏𝐫𝐞𝐟𝐢𝐱 𝐒𝐮𝐦 𝐎𝐩𝐭𝐢𝐦𝐢𝐳𝐚𝐭𝐢𝐨𝐧 | 𝐌𝐚𝐱𝐢𝐦𝐮𝐦 𝐒𝐮𝐦 𝐒𝐮𝐛𝐚𝐫𝐫𝐚𝐲 𝐰𝐢𝐭𝐡 𝐒𝐭𝐚𝐫𝐭 & 𝐄𝐧𝐝 𝐃𝐢𝐟𝐟𝐞𝐫𝐞𝐧𝐜𝐞 𝐢𝐬 𝐞𝐪𝐮𝐚𝐥 𝐭𝐨 𝐊 🔥 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝐒𝐭𝐚𝐭𝐞𝐦𝐞𝐧𝐭 : Given an array of size N, find the maximum sum subarray such that: 👉 The absolute difference between the first and last element of the subarray is exactly K 💡 Example: N = 8, K = 5 Array = [1, 5, -5, 8, 8, 8, 10, 15] ✅ Valid Subarray → [-5, 8, 8, 8, 10] ✅ Output → 34 ⚡ 𝐀𝐩𝐩𝐫𝐨𝐚𝐜𝐡 𝟏: 𝐁𝐫𝐮𝐭𝐞 𝐅𝐨𝐫𝐜𝐞 Try all possible subarrays Check if |start - end| = K Compute sum for valid subarrays ⏱ Time Complexity: O(N³) 📎 CODE LINK: https://lnkd.in/ddawDWMn 🚀 𝐀𝐩𝐩𝐫𝐨𝐚𝐜𝐡 𝟐: 𝐎𝐩𝐭𝐢𝐦𝐚𝐥 (𝐇𝐚𝐬𝐡𝐢𝐧𝐠 + 𝐏𝐫𝐞𝐟𝐢𝐱 𝐒𝐮𝐦) Maintain running prefix sum Use HashMap → store value → minimum prefix sum before it For each element, check: 👉 a[j] + K OR a[j] - K existed before Maximize subarray sum efficiently ⏱ Time Complexity: O(N) 📎 CODE LINK: https://lnkd.in/dNYpAjJ9 🎯 𝐊𝐞𝐲 𝐓𝐚𝐤𝐞𝐚𝐰𝐚𝐲: Using Hashing + Prefix Sum, we reduce complexity from O(N³) → O(N) This is a powerful pattern for subarray problems 🔥 #CompetitiveProgramming #DSA #Coding #Hashing #PrefixSum #Cpp #ProblemSolving

🚀 Day 529 of #750DaysOfCode 🚀 Today I solved LeetCode 3600 – Maximize Spanning Tree Stability with Upgrades (Hard). 🧠 Problem Summary: We are given a graph with mandatory and optional edges, each having a strength value. We can upgrade at most k optional edges, where each upgrade doubles the strength. The goal is to build a valid spanning tree such that the minimum strength among selected edges is maximized. This problem combines multiple advanced concepts: ✔ Spanning Tree ✔ Union Find (DSU) ✔ Binary Search on Answer ✔ Greedy selection ✔ Graph connectivity 💡 Approach: • Use Binary Search to guess the maximum possible stability. • For each value, try to build a spanning tree using DSU (Union-Find). • Include all mandatory edges first. • Use optional edges, upgrading when needed (up to k times). • Check if we can connect all nodes without cycles. 📚 Learned today: Binary Search on Answer in Graph problems DSU for cycle detection Handling constraints with greedy strategy Hard level MST variation Consistency + Hard problems = Growth 📈 #LeetCode #HardProblem #Graphs #DSU #BinarySearch #Algorithms #Java #CodingChallenge #ProblemSolving #SoftwareEngineer #750DaysOfCode

🚀 LeetCode Daily Challenge 🔗 Problem: https://lnkd.in/eC4nGYRx 💡 My thought process: The code checks if two strings can be made equal by swapping characters only between indices that have the same parity. This means characters at even indices can only move among even positions, while those at odd indices can only move among odd positions. To manage this, the code first goes through the first string and records the frequency of characters separately for even and odd indices using two unordered maps. This captures how many times each character appears in each parity group. Next, it goes through the second string. For each character, it checks if it exists in the corresponding parity map. If the current index is even, it checks the even map; if odd, it checks the odd map. When it finds a match, it decreases the frequency and removes the entry from the map if it reaches zero. If a character isn’t found in the required parity map, the function returns false right away. This approach is necessary because checking overall character frequency isn’t enough due to the swapping restrictions. Since characters can’t move between even and odd indices, both parity groups must have identical frequency distributions in both strings. Using separate maps ensures that this rule is enforced. If all characters from the second string match with the corresponding parity groups from the first string, the function returns true, confirming that the transformation is possible. 👉 My Solution: https://lnkd.in/erhV7_HJ If you found this breakdown helpful, feel free to ⭐ the repo or connect with me on LinkedIn 🙂🚀 #️⃣ #leetcode #cpp #dsa #coding #problemsolving #engineering #BDRM #BackendDevWithRahulMaheswari

Upsolved an interesting problem from a recent LeetCode contest: 3628. Maximum Number of Subsequences After One Insertion At first glance, it looks simple — but the real challenge is in structuring the thinking correctly. 🧠 Key Idea We are allowed to insert at most one character, so the optimal solution must come from evaluating all possible insertion scenarios: - Insert "L" - Insert "C" - Insert "T" Instead of brute force, we break the problem into counting subsequences efficiently. 🔍 Observations A valid subsequence follows: L → C → T So we reverse-engineer what each insertion needs: 1️⃣ Insert "L" To maximize impact, "L" should contribute to as many "CT" pairs as possible. 👉 Compute from right to left: - Count of "T" - Then count of "CT" So: New subsequences = existing LCT + total CT 2️⃣ Insert "T" Now we want maximum "LC" pairs. 👉 Compute from left to right: - Count of "L" - Then count of "LC" So: New subsequences = existing LCT + total LC 3️⃣ Insert "C" This is the most interesting case. We insert "C" at every possible position (n+1 positions), and for each position: - Count of "L" before it - Count of "T" after it 👉 Contribution: L_before × T_after We take the maximum over all positions. ⚙️ Final Strategy - Precompute: - Prefix count of "L" - Suffix count of "T" - Track: - "LC" and "CT" counts - Existing "LCT" count - Evaluate all 3 insertion options ⏱️ Complexity - Time: O(n) - Space: O(n) (can be optimized further) Also, a subtle bug I hit initially: 👉 For "C" insertion, you must consider all n+1 positions, not just internal indices. How can the Space Complexity be optimized further? Please let me know in the comments, I'm all ears. #LeetCode #DSA #Algorithms #CodingInterview #SoftwareEngineering