Smallest Balanced Index in Array

🚀 DSA Challenge – Day 194 Problem: Largest Component Size by Common Factor 🔗🔢 Today’s problem is a powerful application of Union-Find (Disjoint Set Union) combined with number theory (factorization). 🧠 Problem Summary You are given an array of unique positive integers nums. We construct a graph where: 👉 Each number is a node 👉 An edge exists between two numbers if they share a common factor > 1 🎯 Goal: Return the size of the largest connected component in this graph. 💡 Key Insight Instead of explicitly building the graph (which would be expensive), we use: 🔥 Union-Find to group connected numbers Key observation: 👉 If two numbers share a factor, they belong to the same component 👉 So we can connect numbers via their prime factors ⚙️ Approach 1️⃣ For each number, compute its prime factors 2️⃣ Maintain a map: factor → index of number 3️⃣ For every factor of a number: If factor already seen → union current index with previous index Else → store it in the map 4️⃣ After processing all numbers: Find the root parent of each node Count size of each component 5️⃣ Return the maximum component size 📈 Complexity Time Complexity: 👉 Factorization: ~O(n √max(nums)) 👉 Union-Find operations: ~O(n α(n)) Space Complexity: O(n) ✨ Why This Problem Is Important This problem teaches a powerful pattern: 🔥 Connect elements indirectly using shared properties Instead of: ❌ Comparing every pair (O(n²)) We use: ✅ Factor mapping + Union-Find 💡 Key Learnings: ➡️ DSU for grouping problems ➡️ Prime factorization in graph problems ➡️ Avoiding explicit graph construction This pattern appears in: ➡️ Connected components ➡️ Grouping by similarity ➡️ Graph problems with hidden relationships 🔖 #DSA #100DaysOfCode #Day194 #UnionFind #DSU #Graphs #NumberTheory #LeetCode #Algorithms #ProblemSolving #CodingChallenge #InterviewPrep #Python #SoftwareEngineering #DeveloperJourney #TechCommunity #CodingLife

🚀 DSA Challenge – Day 189 Problem: Decode String 🔐📜 Today’s problem is a classic stack-based parsing question that tests your ability to handle nested structures. 🧠 Problem Summary You are given an encoded string s. The encoding rule is: 👉 k[encoded_string] → repeat encoded_string exactly k times Constraints: k is a positive integer The string may contain nested patterns Input is always valid (well-formed brackets, no extra spaces) 🎯 Goal: Return the decoded string. 💡 Key Insight The presence of nested brackets makes recursion possible, but using a stack is more intuitive. 👉 Whenever we encounter ], we know a complete pattern is ready to decode. We then: 1️⃣ Extract the string inside the brackets 2️⃣ Extract the number k before it 3️⃣ Repeat the string k times 4️⃣ Push it back to the stack ⚙️ Approach 1️⃣ Traverse the string character by character. 2️⃣ If the character is not ], push it onto the stack. 3️⃣ When encountering ]: Pop characters until '[' → this gives the substring Pop digits to form the number k Repeat the substring k times Push the result back to the stack 4️⃣ At the end, join everything in the stack. 📈 Complexity Time Complexity: O(n) Space Complexity: O(n) ✨ Why This Problem Is Important This problem highlights a key pattern: 🔥 Stack for parsing nested expressions Similar patterns appear in: ➡️ Valid Parentheses ➡️ Basic Calculator problems ➡️ Expression evaluation ➡️ XML/JSON parsing Understanding how to process nested structures using a stack is crucial for many real-world problems. 🔖 #DSA #100DaysOfCode #Day189 #Stack #Strings #Parsing #LeetCode #Algorithms #ProblemSolving #CodingChallenge #InterviewPrep #Python #SoftwareEngineering #DeveloperJourney #TechCommunity #CodingLife

🚀 DSA Challenge – Day 199 Problem: All Paths From Source to Target 🛣️📍 Today’s problem is a classic DFS + Backtracking question on Directed Acyclic Graphs (DAGs). 🧠 Problem Summary You are given: 👉 A DAG represented as an adjacency list graph 👉 Nodes labeled from 0 → n-1 🎯 Goal: Return all possible paths from: ➡️ Source node 0 ➡️ Target node n-1 💡 Key Insight Since the graph is a DAG: 👉 No cycles → safe to explore all paths using DFS This becomes a path generation problem. ⚙️ Approach 1️⃣ Use DFS (Depth First Search) 2️⃣ Maintain a current path list 3️⃣ Start from node 0 4️⃣ For each node: Add it to the path Explore all neighbors recursively 5️⃣ If you reach node n-1: ✅ Add the current path to result 6️⃣ Backtrack: Remove last node and explore other paths 📌 Why Backtracking? 👉 We reuse the same path list 👉 Undo choices after exploring each branch 📈 Complexity Time Complexity: O(2ⁿ × n) (in worst case) Space Complexity: O(n) (recursion stack) ✨ Why This Problem Is Important This problem builds a strong foundation in: 🔥 DFS traversal 🔥 Backtracking patterns 🔥 Path exploration in graphs 💡 Key Learnings: ➡️ DAG ensures no infinite loops ➡️ Backtracking helps explore all possibilities efficiently ➡️ Path problems = build → explore → undo This pattern appears in: ➡️ All root-to-leaf paths ➡️ Word Ladder variations ➡️ Path sum problems ➡️ Graph traversal with constraints 🔖 #DSA #100DaysOfCode #Day199 #DFS #Backtracking #Graphs #DAG #LeetCode #Algorithms #ProblemSolving #CodingChallenge #InterviewPrep #Python #SoftwareEngineering #DeveloperJourney #TechCommunity #CodingLife

🚀 DSA Challenge – Day 196 Problem: Minimum Number of Vertices to Reach All Nodes 🧭📊 Today’s problem is a clean and powerful application of graph intuition using indegree. 🧠 Problem Summary You are given: 👉 A Directed Acyclic Graph (DAG) with n nodes 👉 A list of directed edges 🎯 Goal: Find the smallest set of vertices from which all nodes are reachable. 💡 Key Insight In a DAG: 👉 If a node has incoming edges, it can be reached from another node 👉 If a node has NO incoming edges (indegree = 0), it must be included in the answer 🔥 Why? Because: ➡️ No other node can reach it ➡️ It has to be a starting point ⚙️ Approach 1️⃣ Initialize an indegree array/map for all nodes 2️⃣ Traverse edges: For each edge (u → v) 👉 Increment indegree[v] 3️⃣ Collect all nodes with: 👉 indegree == 0 4️⃣ Return them as the answer 📈 Complexity Time Complexity: O(n + e) Space Complexity: O(n) ✨ Why This Problem Is Important This problem highlights a fundamental graph concept: 🔥 Nodes with indegree 0 are entry points Key takeaway: ➡️ In DAG problems, always check indegree/outdegree patterns ➡️ Helps in: Topological sorting Dependency resolution Task scheduling 💡 Real-world analogy: Think of tasks: 👉 Tasks with no dependencies must be started manually 👉 Everything else can be reached through them 🔖 #DSA #100DaysOfCode #Day196 #Graphs #DAG #Indegree #LeetCode #Algorithms #ProblemSolving #CodingChallenge #InterviewPrep #Python #SoftwareEngineering #DeveloperJourney #TechCommunity #CodingLife

🚀 DSA Day — Merge Two Sorted Arrays (LeetCode 88) Today I worked on a classic problem that looks simple but teaches an important optimization technique 👇 🔹 Problem Statement You are given two sorted arrays and need to merge them into one sorted array in-place. Example: nums1 = [1, 7, 8, 0, 0, 0], m = 3 nums2 = [2, 5, 6], n = 3 ✅ Output: [1, 2, 5, 6, 7, 8] 🔸 Approach 1: Brute Force ✔ Copy nums2 into nums1 ✔ Sort the entire array ⏱ Time Complexity: O((m+n) log(m+n)) 👉 Simple but not efficient 🔸 Approach 2: Optimized (Two Pointers) 💡 Key Idea: Start filling from the end ✔ Compare last elements of both arrays ✔ Place the larger one at the end ✔ Move pointers accordingly ⏱ Time Complexity: O(m+n) 📦 Space Complexity: O(1) 🔥 Why this works? Because nums1 already has extra space at the end — we use it smartly without shifting elements. 💻 Code Snippet (Optimized) https://lnkd.in/g9Z7yf3d def merge(nums1, m, nums2, n): i = m - 1 j = n - 1 k = m + n - 1 while i >= 0 and j >= 0: if nums1[i] > nums2[j]: nums1[k] = nums1[i] i -= 1 else: nums1[k] = nums2[j] j -= 1 k -= 1 while j >= 0: nums1[k] = nums2[j] j -= 1 k -= 1 🎯 Key Takeaway 👉 Always think from the end when dealing with in-place array problems. #DSA #Python #CodingInterview #LeetCode #ProblemSolving #SoftwareEngineering #LearnInPublic

✅ Day 82 of 100 Days LeetCode Challenge Problem: 🔹 #2906 – Construct Product Matrix 🔗 https://lnkd.in/gdb7GZNB Learning Journey: 🔹 Today’s problem required constructing a matrix where each cell contains the product of all other elements except itself, modulo 12345. 🔹 I flattened the 2D matrix into a 1D list to simplify processing. 🔹 Then I used the prefix and postfix product technique: • pre[i] → product of all elements before index i • post[i] → product of all elements after index i 🔹 Multiplying pre[i] * post[i] gives the required result for each position. 🔹 Finally, I mapped the computed values back into the original matrix shape. Concepts Used: 🔹 Prefix Product 🔹 Postfix Product 🔹 Array Flattening 🔹 Modular Arithmetic Key Insight: 🔹 Using prefix and postfix arrays avoids recomputing products for every cell, reducing time complexity. 🔹 This is an extension of the classic “product of array except self” problem. Complexity: 🔹 Time: O(n × m) 🔹 Space: O(n × m) #LeetCode #Algorithms #DataStructures #CodingInterview #100DaysOfCode #SoftwareEngineering #Python #ProblemSolving #LearningInPublic #TechCareers

Recursion as Divide-and-Conquer: Why Tree Depth is One Line of Code Computing tree depth iteratively requires explicit stack management and level tracking. But recognizing the recursive structure — a tree's depth equals 1 plus the maximum of its subtrees' depths — collapses the solution to a single expression. This isn't just code golf; it's recognizing that the problem structure mirrors the data structure, making recursion the natural fit. When Recursion Wins: Problems where the solution for the whole directly composes from solutions to parts (tree operations, divide-and-conquer algorithms, dynamic programming with optimal substructure) are recursion's sweet spot. The implementation mirrors the mathematical definition. Contrast this with problems requiring explicit state tracking across iterations — there, iteration dominates. The Hidden Cost: This elegant recursion hits O(h) stack space. For balanced trees (h = log n), negligible. For skewed trees (h = n), potential stack overflow. Production systems handling untrusted tree data often need iterative solutions with explicit stack allocation to bound memory and prevent crashes. Elegance has limits. Time: O(n) visit each node once | Space: O(h) worst-case recursion depth #RecursionPatterns #DivideAndConquer #TreeAlgorithms #CodeSimplicity #SpaceComplexity #Python #AlgorithmDesign #SoftwareEngineering

🚀 DSA Challenge – Day 185 Problem: Magical String ✨🔢 Today’s problem is a fascinating simulation + pattern generation problem. The challenge lies in constructing a sequence that describes itself. 🧠 Problem Summary A magical string s consists only of the characters '1' and '2'. It has a special property: 👉 If you group consecutive identical characters and record their lengths, 👉 The resulting sequence of counts recreates the string itself. Example: Magical string begins as: 1221121221221121122... Grouping the characters: 1 | 22 | 11 | 2 | 1 | 22 | 1 | 22 | 11 | ... Counting group lengths gives: 1 2 2 1 1 2 1 2 2 ... Concatenating these counts recreates the same magical string. 🎯 Goal: Given an integer n, return the number of '1's in the first n characters of the magical string. 💡 Key Insight Instead of computing groups directly, we build the string gradually. Important observations: 1️⃣ The sequence starts with "1, 2, 2". 2️⃣ Each value in the sequence tells how many times the next number should repeat. 3️⃣ The next number always alternates between 1 and 2. Example pattern: 1 → one 1 2 → two 2s 2 → two 1s 1 → one 2 and so on... This allows us to generate the magical string dynamically until we reach length n. ⚙️ Approach 1️⃣ Start with the initial sequence: ["1", "2", "2"] 2️⃣ Maintain a pointer that reads how many times the next value should repeat. 3️⃣ Alternate between 1 and 2 while appending new elements. 4️⃣ Continue generating until the string length reaches n. 5️⃣ Count how many '1's appear in the first n characters. 📈 Complexity Time Complexity: O(n) Space Complexity: O(n) ✨ Why This Problem Is Interesting This problem is tricky because it requires understanding a self-referential sequence. It strengthens concepts like: 🔥 Simulation-based construction 🔥 Pattern recognition 🔥 Controlled sequence generation Problems like this often appear in interviews to test your ability to translate rules into iterative logic. 🔖 #DSA #100DaysOfCode #Day185 #Simulation #Patterns #LeetCode #Algorithms #ProblemSolving #CodingChallenge #InterviewPrep #Python #SoftwareEngineering #DeveloperJourney #TechCommunity #CodingLife

🚀 DSA Challenge – Day 191 Problem: Longest Consecutive Sequence 🔢📈 Today’s problem is a classic example of achieving O(n) performance using smart data structures. 🧠 Problem Summary You are given an unsorted array nums. 🎯 Goal: Find the length of the longest sequence of consecutive integers. Constraints: 👉 Must run in O(n) time 👉 Elements can be in any order Example: nums = [100, 4, 200, 1, 3, 2] Longest consecutive sequence → [1, 2, 3, 4] Answer → 4 💡 Key Insight Sorting would take O(n log n), which violates the constraint. Instead, we use a set for O(1) lookups. 👉 The trick is to only start counting when we find the beginning of a sequence. How do we identify a sequence start? 👉 If num - 1 is NOT in the set → it's the start of a sequence. ⚙️ Approach 1️⃣ Insert all elements into a set. 2️⃣ Iterate through each number: If num - 1 exists → skip (not a sequence start) Otherwise → start counting the sequence 3️⃣ Keep expanding: Check num + 1, num + 2, ... until sequence breaks 4️⃣ Track the maximum length. 📈 Complexity Time Complexity: O(n) Space Complexity: O(n) ✨ Why This Problem Is Important This problem highlights a powerful idea: 🔥 Use a HashSet to simulate sorting behavior efficiently Key takeaway: ➡️ Avoid redundant work by identifying valid starting points ➡️ Convert problems into O(1) lookup scenarios This pattern appears in: ➡️ Longest substring problems ➡️ Sequence detection ➡️ Hash-based optimizations 🔖 #DSA #100DaysOfCode #Day191 #HashSet #Arrays #LeetCode #Algorithms #ProblemSolving #CodingChallenge #InterviewPrep #Python #SoftwareEngineering #DeveloperJourney #TechCommunity #CodingLife

🚀 DSA Challenge – Day 187 Problem: Longest Happy Prefix 😊🔤 Today’s problem explores a classic string hashing / pattern matching concept used in many advanced string algorithms. 🧠 Problem Summary A string is called a happy prefix if: 👉 It is a non-empty prefix of the string 👉 It is also a suffix of the string 👉 It cannot be the entire string itself 🎯 Goal: Given a string s, return the longest happy prefix. If none exists, return "". Example idea: s = "level" Prefix candidates: l, le, lev, leve Suffix candidates: evel, vel, el, l The longest match is "l". 💡 Key Insight A brute-force approach would compare every prefix with every suffix, leading to O(n²) complexity. Instead, we use Rolling Hash (Polynomial Hashing). We compute simultaneously: Prefix hash from the left Suffix hash from the right If both hashes match at some index, we have found a prefix that also appears as a suffix. We track the longest such match. ⚙️ Approach 1️⃣ Initialize: prefixHash suffixHash power for polynomial hashing 2️⃣ Iterate through the string (excluding the last character). 3️⃣ Update: Prefix hash moving left → right Suffix hash moving right → left 4️⃣ If hashes match: Update the length of the current longest happy prefix. 5️⃣ Return the substring corresponding to that length. 📈 Complexity Time Complexity: O(n) Space Complexity: O(1) ✨ Why This Problem Is Important This problem introduces an important technique: 🔥 Rolling Hash for String Matching Similar concepts appear in algorithms like: ➡️ Rabin–Karp ➡️ Pattern matching problems ➡️ String border detection ➡️ Longest prefix-suffix problems Understanding this technique helps in solving many advanced string problems efficiently. 🔖 #DSA #100DaysOfCode #Day187 #StringHashing #RollingHash #Strings #LeetCode #Algorithms #ProblemSolving #CodingChallenge #InterviewPrep #Python #SoftwareEngineering #DeveloperJourney #TechCommunity #CodingLife