Deep Copy Linked List with Random Pointers in O(n) Time

Day - 63 Combination Sum III The problem - Find all combinations of k numbers that sum to n, using only numbers 1-9, each number used at most once. Example : k = 3, n = 7 → [[1,2,4]] Brute Force - Generate all C(9, k) combinations, check each sum, still needs to enumerate all combinations. Approach Used - •) Initialize: Call findCombination(k, 1, n, new ArrayList<>(), ans) (start with number 1). •) findCombination(k, num, target, lst, ans), •) If (target == 0 && k == 0), found valid combination, add new ArrayList(lst) to ans and return. •) Recursive case, for num to 9, 1 - If i > target || k <= 0, break. 2 - Add i to lst. 3 - Recurse with k - 1 (need one less number), i + 1 (next number to try), target - i (remaining sum). 4 - Backtrack: remove i from lst. Complexity - Time - O(C(9, k) × k), C(9,k) combinations, k time to copy each. Space - O(k), recursion depth. Note - Loop from 1-9, add number, recurse with k-1 and target-num. Backtrack when target == 0 && k == 0! #DSA #Java #SoftwareEngineering #InterviewPrep #LearnToCode #CodeDaily #ProblemSolving

𝐃𝐚𝐲 𝟏𝟓 – 𝐃𝐒𝐀 𝐉𝐨𝐮𝐫𝐧𝐞𝐲 | 𝐀𝐫𝐫𝐚𝐲𝐬 🚀 Today’s problem focused on grouping logic using arrays + hashing concepts 🗂️ and understanding different ways to build unique keys. 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝐒𝐨𝐥𝐯𝐞𝐝 • 🔤 Group Anagrams 🔹 𝐆𝐫𝐨𝐮𝐩 𝐀𝐧𝐚𝐠𝐫𝐚𝐦𝐬 𝐀𝐩𝐩𝐫𝐨𝐚𝐜𝐡 𝟏 – 𝐒𝐨𝐫𝐭𝐢𝐧𝐠 𝐁𝐚𝐬𝐞𝐝 • 🔄 Converted each word into a char array • 📊 Sorted the characters • 🔑 Used the sorted string as a key in HashMap • 📦 Grouped words sharing the same sorted key 𝐀𝐩𝐩𝐫𝐨𝐚𝐜𝐡 𝟐 – 𝐅𝐫𝐞𝐪𝐮𝐞𝐧𝐜𝐲 𝐀𝐫𝐫𝐚𝐲 𝐁𝐚𝐬𝐞𝐝 • 🔢 Created a frequency array of size 26 • 🧮 Built a unique key using character counts • ⚡ Used computeIfAbsent for cleaner insertion • 📌 Avoided sorting for better efficiency 𝐊𝐞𝐲 𝐋𝐞𝐚𝐫𝐧𝐢𝐧𝐠𝐬 • 🧠 Anagrams share identical character distributions • 🔑 The way you build the key defines performance • ⚡ Frequency-array approach avoids O(k log k) sorting • 📊 Combining arrays with hashing improves efficiency 🧠 𝐓𝐚𝐤𝐞𝐚𝐰𝐚𝐲 Even in array problems, sometimes the real power lies in how you represent the data 🔑 15 days consistent 🔥 On to Day 16 🚀 #DSA #Arrays #Strings #LeetCode #Java #ProblemSolving #DailyCoding #LearningInPublic #SoftwareDeveloper

Day - 65 Letter Combinations of Phone Number The problem - Given string of digits 2-9, return all possible letter combinations that the number could represent (like old phone keypads). Example : digits = "23" → ["ad","ae","af","bd","be","bf","cd","ce","cf"] Brute Force - Generate all combinations iteratively using nested loops - works but becomes unwieldy with variable input length. Approach Used - •)Create map, 2→"abc", 3→"def", 4→"ghi", 5→"jkl", 6→"mno", 7→"pqrs", 8→"tuv", 9→"wxyz" •) Handle edge case, if digits is null or empty, return empty list. •) Initialize, call backtrack(digits, 0, new StringBuilder(), res, map). •) Backtrack(digits, idx, comb, res, map), 1 - Base Condition, if idx == digits.length, add comb to res. 2 - Recursive case, get letters for current digit, String letters = map.get(digits.charAt(idx)). 3 - For each letter, append to comb, recurse with idx+1, backtrack(digits, idx + 1, comb, res, map). Remove last character, comb.deleteCharAt(comb.length() - 1). Complexity - Time - O(4^n × n), max 4 letters per digit, n to build each string. Space - O(n), recursion depth. Note - Use map for digit→letters. For each digit, try all its letters, recurse to next digit. #DSA #Java #SoftwareEngineering #InterviewPrep #LearnToCode #CodeDaily #ProblemSolving

Day - 82 Merge K Sorted Lists The problem - Given an array of k linked lists, each linked list is sorted in ascending order. Merge all the linked lists into one sorted linked list and return it. Brute Force - Collect all nodes from all lists into an array, sort the array, and create a new linked list from sorted values. This gives O(N log N) time complexity where N = total number of nodes, but requires O(N) extra space for the array. Approach Used - •) Create PriorityQueue<ListNode> (min heap) with comparator (a, b) -> a.val - b.val. •) Add the head of each non-null list to the heap. •) Create dummy node and res pointer for building result list. •) While heap is not empty, 1 - Poll the smallest node curr from heap. 2 - Attach curr to result list, res.next = curr. 3 - Move result pointer, res = res.next. 4 - If curr.next is not null, add it to heap. •) Return dummy.next. Complexity - Time - O(N log k), N = total number of nodes across all lists, processing N nodes, O(N), and each heap operation O(log k). Space - O(k), heap stores at most k elements. Note - Use a min heap to efficiently perform k-way merge. At each step, extract the minimum node from the heap (smallest among all list heads), add it to result, and insert its next node back into the heap. This maintains the invariant that the heap always contains the current smallest unprocessed node from each list. #DSA #Java #SoftwareEngineering #InterviewPrep #LearnToCode #CodeDaily #ProblemSolving

Day - 61 Subsets II The problem - Given array that may contain duplicates, return all possible unique subsets. Example : candidates = [10,1,2,7,6,1,5], target = 8 → [[1,1,6],[1,2,5],[1,7],[2,6]] Brute Force - Generate all combinations iteratively, still exponential, but less elegant than recursion. Approach Used - •) Sort the nums array.nums.lengthcktrack(0, nums, subset, res). •) Base case, if i == nums.length, reached end, add new ArrayList(subset) to res and return. •) Recursive First case, include nums[i], add to subset, recurse with i+1, backtrack (remove). •) Recursive Second case, exclude nums[i], recurse with i+1 (don't add). Complexity - Time - O(2^n), each element include/exclude. Space - O(n), recursion depth. Note - Sort array. After excluding an element, skip all duplicates before next recursion to avoid duplicate subsets. #DSA #Java #SoftwareEngineering #InterviewPrep #LearnToCode #CodeDaily #ProblemSolving

Group Anagrams — 49 🎯 Goal Group strings that are anagrams and return them as a list of groups. Anagram: Strings having the same characters with the same frequency (order does not matter). Core Intuition We need to group items based on a common property. Property here = same character composition Best data structure for grouping by a property → HashMap Approach 1 — Sorting (Brute / Standard) If we sort a string, all anagrams become identical. Example: eat → aet tea → aet ate → aet So we can: - Sort each string - Use the sorted string as the key - Store original strings as values in a HashMap Complexity Let: - N = number of strings - K = average string length Time Complexity: O(N × K log K) (because sorting each string takes K log K) Space Complexity: O(N × K) Worst case: if all strings are different, each gets stored separately in the HashMap. Trade-off Sorting is simple and clean, but: If strings are very large, sorting becomes expensive. Optimized Approach — Frequency Count To avoid sorting cost, we can use character frequency. This works when: - All characters are lowercase (or uppercase) - Fixed alphabet size (26) Idea - Create an array of size 26. - Traverse each string and count character frequency. - Convert this frequency array into a string. - Use that string as the HashMap key. Now: - Building key = O(K) - No sorting needed. Complexity Time Complexity: O(N × K) Space Complexity: O(N × K) Extra space used is constant (26-size array), but we gain better time performance. 🕸Trap Trying to use an array/list directly as a HashMap key. In Java: - Arrays do not implement "equals()" properly for value comparison. ✔ Always convert frequency array to a String before using it as a key. Trigger Whenever you see: Group items based on a property Think: HashMap + Generated Key If I missed anything or if you have a better approach, please feel free to add it in the comments 🙌 #DSA #LeetCode #Java #Algorithms #ProblemSolving #CodingJourney #InterviewPreparation #SoftwareEngineer

🚀 Day 20 of #100DaysOfCode 🌱 Topic: Binary Trees / Recursion ✅ Problem Solved: LeetCode 105 – Construct Binary Tree from Preorder and Inorder Traversal 🛠 Approach: Used preorder to identify the root node. Used inorder to split left and right subtrees. Stored inorder indices in HashMap for fast lookup. Recursively built left and right subtrees using calculated ranges. ⏱ Time Complexity: O(n) 📦 Space Complexity: O(n) (HashMap) #100DaysOfCode #Day20 #DSA #BinaryTree #Recursion #Java #LeetCode #ProblemSolving #CodingJourney #Consistency #LearningInPublic #SoftwareEngineering

Contains Duplicate — LeetCode 217 Hi all 👋 Today this is my first post related to a DSA problem. Goal Check whether an array contains duplicate numbers or not. n = Length of array idx = Index of array element Brute Force Approach Select each element and compare it with all other elements in the array. If any same value is found, return "true"; otherwise return "false". Time Complexity: O(n²) Space Complexity: O(1) Reason: every element is compared with others. Better Approach (Sorting) If we sort the array, duplicate elements come next to each other. After sorting, we simply compare adjacent elements. 🕸 Trap Empty array or single element array (idx < n-1) Time Complexity: O(n log n) Space Complexity: Depends on the sorting algorithm. Optimized Approach (Using Set) Before moving forward, let’s recall one important data structure — Set. A set: - Performs operations in average O(1) time - Does not allow duplicates Approach: - Traverse the array from the first element. - Check if the element already exists in the set. - If yes → duplicate found → return "true". - Otherwise, add the element to the set. The key idea: if we encounter the same element again, it means a duplicate exists. Time Complexity: O(n) Space Complexity: O(n) (in worst case when no duplicates exist) 🔁 Trade-off In real-world problems, we often optimize for time complexity. - If extra space is allowed → use Set (best time). - If space is restricted → prefer Sorting. Whenever you see duplicate or frequency type problems, think about: ➡️ Sorting ➡️ HashSet / HashMap If I missed anything or if you have a better approach, please feel free to add it in the comments. Thanks for reading 🙌 #DSA #LeetCode #Java #CodingJourney #DataStructures #Algorithms #ProblemSolving #SoftwareEngineer #TechLearning #InterviewPreparation

Day 11 of Daily DSA 🚀 Solved LeetCode 1394: Find Lucky Integer in an Array ✅ Approach: Iterated through the array and stored the frequency of each element using a HashMap. Then traversed the map to find integers whose value equals their frequency. Among all valid candidates, tracked and returned the maximum lucky integer. This approach ensures clarity and correctness with a straightforward counting strategy. ⏱ Complexity: • Time: O(n) — single pass to count + map traversal • Space: O(n) — extra space for frequency map 📊 LeetCode Stats: • Runtime: 5 ms (Beats 69.53%) ⚡ • Memory: 44.70 MB (Beats 99.01%) A good example of how HashMaps simplify frequency-based problems. #DSA #LeetCode #Java #HashMap #ProblemSolving #DailyCoding #Consistency