Generate Phone Number Combinations with Java

Day - 73 Valid Parentheses The problem - Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. A string is valid if: open brackets are closed by the same type of brackets, open brackets are closed in the correct order, and every close bracket has a corresponding open bracket. Brute Force - Repeatedly scan the string and remove valid pairs like "()", "{}", "[]" until no more pairs can be removed. If the string becomes empty, it's valid. This gives O(n²) time complexity due to multiple passes and string manipulation. Approach Used - •) Create a Stack<Character> to track opening brackets •) Create a HashMap<Character, Character> to map closing to opening brackets, ')' → '(' , '}' → '{' and ']' → ‘[‘. •) Process each character, Iterate through each character c in the string, 1 - If c is an opening bracket, push it onto the stack. 2 - If c is a closing bracket, - Check if stack is empty, return false. - ⁠Pop from stack and check if it matches mapping.get(c), if mismatch → return false. •) Final Validation, 1 - After processing all characters, check if stack is empty. 2 - Empty stack means all brackets matched correctly. 3 - Non-empty stack means unmatched opening brackets remain. Complexity - Time - O(n), single pass through the string, each character processed once and stack operations (push/pop) are O(1). Space - O(n), stack can hold up to n/2 opening brackets in worst case. Note - Stack naturally handles nested structures with LIFO (Last-In-First-Out) behavior. Each closing bracket must match the most recent unmatched opening bracket. HashMap enables O(1) lookup for matching pairs, making validation efficient. #DSA #Java #SoftwareEngineering #InterviewPrep #LearnToCode #CodeDaily #ProblemSolving

Day - 86 Binary Tree Preorder Traversal The problem - Given the root of a binary tree, return the preorder traversal of its nodes' values. In preorder traversal, we visit nodes in the order: Root → Left → Right. Brute Force - Store all nodes in an array using level-order traversal, then manually rearrange them in preorder sequence. This gives O(n²) time complexity due to repeated searching and rearranging, which is highly inefficient. Approach Used - •) Initialize ans = new ArrayList<>(). •) If root == null, return empty ans. •) Call helper function - preorder(root, ans). •) Return ans. Helper Function - •) If root != null, 1 - Add current node value: ans.add(root.val). 2 - Recursively traverse left subtree, preorder(root.left, ans). 3 - Recursively traverse right subtree, preorder(root.right, ans). Complexity - Time - O(n), where n = number of nodes. Space - O(h), where h = height of tree. Note - Preorder traversal naturally follows a recursive pattern: process the current node (Root), then recursively process the left subtree (Left), and finally the right subtree (Right). The recursion stack implicitly handles backtracking, making the implementation clean and straightforward. #DSA #Java #SoftwareEngineering #InterviewPrep #LearnToCode #CodeDaily #ProblemSolving

🔥 Day 315 – Daily DSA Challenge! 🔥 Problem: 🔗 Insertion Sort List Given the head of a singly linked list, sort the list using the Insertion Sort algorithm and return the sorted list. 💡 Key Insights: 🔹 This is the linked-list version of Insertion Sort. 🔹 Unlike arrays, linked lists allow O(1) insertions once the position is found. 🔹 A dummy node simplifies edge cases (like inserting at the head). 🔹 We iteratively take nodes from the original list and insert them into the correct position in the sorted part. 🔹 At every step, the list starting from dummy remains sorted. ⚡ Optimized Plan: ✅ Create a dummy node to act as the sorted list’s head ✅ Traverse the original list node by node ✅ For each node: Find its correct position in the sorted list Insert it there ✅ Continue until all nodes are processed ✅ Return dummy.next as the sorted head ✅ Time Complexity: O(n²) (worst case, already reverse sorted) ✅ Space Complexity: O(1) (in-place sorting) 💬 Challenge for you: 1️⃣ Why is insertion sort more suitable for linked lists than arrays? 2️⃣ How does the performance change if the list is nearly sorted? 3️⃣ Can you optimize this further by tracking the last sorted node? #DSA #Day315 #LeetCode #LinkedList #Sorting #InsertionSort #Java #ProblemSolving #KeepCoding #100DaysOfCode

🔥 Day 309 – Daily DSA Challenge! 🔥 Problem: 🔁 Permutations II Given an array nums that may contain duplicate numbers, return all unique permutations in any order. 💡 Key Insights: 🔹 This is a backtracking problem with an extra twist — duplicates. 🔹 Sorting the array upfront is the key to handling duplicates cleanly. 🔹 Use a used[] boolean array to track which elements are already in the current permutation. 🔹 The golden rule to skip duplicates 👇     👉 If the current number is the same as the previous one and the previous one is not used, skip it. 🔹 This ensures we only generate unique permutations. ⚡ Optimized Plan: ✅ Sort the input array ✅ Use backtracking to build permutations ✅ Track used elements with a boolean array ✅ Add permutation to result when its size equals nums.length ✅ Skip duplicates using:     if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue; ✅ Backtrack after each recursive call ✅ Time Complexity: O(n! × n) (due to copying permutations) ✅ Space Complexity: O(n) (recursion stack + used array) 💬 Challenge for you: 1️⃣ Why does the condition !used[i - 1] matter for avoiding duplicates? 2️⃣ How would this solution change if all numbers were unique? 3️⃣ Can you generate permutations iteratively instead of using recursion? #DSA #Day309 #LeetCode #Permutations #Backtracking #Recursion #Java #ProblemSolving #KeepCoding #100DaysOfCode

🔥 Day 82 of #100DaysOfCode Today’s problem: LeetCode: Permutation in String 🧠 📌 Problem Summary Given two strings s1 and s2, return true if s2 contains a permutation of s1. Example: s1 = "ab" s2 = "eidbaooo" Output → true (because "ba" exists in s2) 🧠 Approach: Sliding Window + Frequency Count (Optimized) Key Idea: If a permutation exists, then some substring of s2 must: Have the same length as s1 Have the same character frequency ⚙️ Steps: If s1.length() > s2.length() → return false Maintain: int[26] s1Count int[26] s2Count Fill both arrays for first window Slide window across s2 Compare frequency arrays To optimize comparison: Track a matches counter When all 26 characters match → permutation found ⏱ Time Complexity: O(n) 💾 Space Complexity: O(1) (fixed 26 letters) 💡 What I Learned Sliding window problems become easier when you convert strings into frequency arrays. Tracking “matches” instead of comparing arrays every time improves performance. This is a classic interview problem for FAANG-level companies. Consistency is compounding. Sliding window mastery getting sharper every day. 🔥 On to Day 83 🚀 #100DaysOfCode #LeetCode #SlidingWindow #Java #DSA #CodingJourney #InterviewPrep

Day - 78 Next Greater Element II The problem - Given a circular integer array nums (the next element of nums[nums.length - 1] is nums[0]), return the next greater number for every element in nums. The next greater number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, return -1 for this number. Brute Force - For each element, traverse the array circularly (wrap around using modulo) to find the first greater element. This gives O(n²) time complexity, as for each element we potentially scan the entire array. Approach Used - •) Initialize, create Stack<Integer> to maintain elements in decreasing order, create ans[] array of size n to store results, set n = nums.length. •) For each index i = 2 × n - 1 down to i = 0, 1 - Get current element: current = nums[i % n]. 2 - While stack is not empty AND st.peek() <= current, pop from stack. 3 - If i < n: ans[i] = st.isEmpty()arr ? -1 : st.peek(). 4 - Push current onto stack. •) Return ans[] array. Complexity - Time - O(n), each element pushed and popped from stack at most once across both passes. Space - O(n), for stack and result array. Note - By traversing the array twice (2n iterations) in reverse order, we simulate the circular nature of the array. The stack maintains elements in decreasing order, and for each element, the top of the stack is the next greater element. The modulo operation i % n handles the circular indexing, and we only store results during the second half of the traversal (when i < n). #DSA #Java #SoftwareEngineering #InterviewPrep #LearnToCode #CodeDaily #ProblemSolving

Day 20 of DSA Consistency – LeetCode 15 (3Sum) Today I solved the classic 3Sum problem. Problem: Find all unique triplets in an array such that a + b + c = 0. At first glance, brute force looks easy (O(n³)), but that’s useless for interviews. It will timeout. The correct approach is: • Sort the array • Fix one number • Use Two Pointers (2Sum technique) • Skip duplicates carefully This reduces the complexity to O(n²). Key learning: Most “hard” problems are just combinations of simpler patterns. 3Sum = Sorting + Two Pointers + Duplicate handling. Patterns > memorizing solutions. Code (Java): class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> res = new ArrayList<>(); Arrays.sort(nums); for (int i = 0; i < nums.length - 2; i++) { if (i > 0 && nums[i] == nums[i - 1]) continue; int left = i + 1, right = nums.length - 1; while (left < right) { int sum = nums[i] + nums[left] + nums[right]; if (sum == 0) { res.add(Arrays.asList(nums[i], nums[left], nums[right])); while (left < right && nums[left] == nums[left + 1]) left++; while (left < right && nums[right] == nums[right - 1]) right--; left++; right--; } else if (sum < 0) left++; else right--; } } return res; } } Time Complexity: O(n²) Space Complexity: O(1) Consistency matters more than speed. 20 days done. No breaks. #DSA #LeetCode #Java #ProblemSolving #CodingInterview #SoftwareEngineering #100DaysOfCode

Day - 87 Binary Tree Level Order Traversal The problem - Given the root of a binary tree, return the level order traversal of its nodes' values (i.e., from left to right, level by level). Each level should be represented as a separate list. Brute Force - Use recursive DFS to traverse the tree while tracking depth. Store nodes at each depth level in separate lists. This gives O(n) time but requires complex depth tracking and is less intuitive than an iterative approach. Approach Used - •) Create res = new ArrayList<>(), queue = new ArrayDeque<>(). •) If root == null, return empty res. •) Add root to queue. •) While queue is not empty, 1 - Get current level size: size = queue.size(). 2 - Create list = new ArrayList<>(). 3 - While size > 0, - Poll node from queue, node = queue.poll(). - ⁠If node.left != null, add to queue: queue.add(node.left). - ⁠If node.right != null, add to queue: queue.add(node.right). - ⁠Add node value to current level: list.add(node.val). - ⁠Decrement size—. 4 - Add current level to result, res.add(list). •) Return res. Complexity - Time - O(n), where n = number of nodes. Space - O(w), where w = maximum width of tree. Note - Use BFS with a queue to traverse level by level. By capturing the queue size at the start of each iteration, we know exactly how many nodes belong to the current level. Process all nodes in that level, adding their children to the queue for the next level. This naturally groups nodes by level without needing depth tracking. #DSA #Java #SoftwareEngineering #InterviewPrep #LearnToCode #CodeDaily #ProblemSolving

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 - 93 Binary Tree Right Side View The problem - Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom. Essentially, return the rightmost node at each level. Brute Force - Perform a complete level-order traversal storing all nodes at each level, then extract only the last node from each level. This gives O(n) time but stores all nodes unnecessarily, wasting O(n) space when we only need one node per level. Approach Used - •) Create result = new ArrayList<>(). •) If root == null, return empty result. •) Create queue = new LinkedList<>(). •) Add root to queue. •) While queue is not empty, 1 - Get current level size, size = queue.size(). 2 - For i = 0 to size - 1, - Poll node from queue, node = que.poll(). - ⁠If i == size - 1, add to result: result.add(current.val), this is the last node at current level. - ⁠If current.left != null, add to queue: queue.offer(current.left). - ⁠If current.right != null, add to queue: queue.offer(current.right). •) Return result. Complexity - Time - O(n), where n is number of nodes. Space - O(w), where w is maximum width of tree. Note - Use level-order BFS to traverse the tree level by level. By tracking the current level size, we can identify the last node processed in each level—this is the rightmost visible node. We only store this last node from each level, efficiently building the right side view in a single traversal. #DSA #Java #SoftwareEngineering #InterviewPrep #LearnToCode #CodeDaily #ProblemSolving