Intersection of Two Arrays Solution in Java

🚀 Day 32 / 90 — DSA Challenge Today’s problem was a very interesting one: Split Array Largest Sum. At first glance, it looks like a typical array partitioning problem, but the real insight is recognizing that this problem can be solved efficiently using Binary Search on the Answer. 🔹 Problem Idea Given an array of integers and a value "k", the goal is to split the array into "k" subarrays such that the largest sum among those subarrays is minimized. Example: nums = [1,2,3,4,5], k = 2 Optimal split → "[1,2,3]" and "[4,5]" Largest sum = 9 🔹 Key Insight Instead of trying every possible split, we: 1️⃣ Use Binary Search on the possible maximum subarray sum 2️⃣ Check if we can split the array into "k" parts with that limit 3️⃣ Adjust the search range accordingly This reduces the complexity from an exponential brute force approach to an efficient O(n log(sum)) solution. 🔹 Concepts Practiced Today ✔ Binary Search on Answer ✔ Greedy partition checking ✔ Optimization problems with arrays ✔ Writing clean feasibility functions ("isPossible") 🔹 Takeaway Many array problems that ask to minimize the maximum value can often be solved using Binary Search on the Answer combined with a greedy validation function. Consistency is the real algorithm here. 32 days down, 58 more to go. #Day32 #90DaysOfDSA #DSAChallenge #LeetCode #BinarySearch #Java #ProblemSolving #SoftwareEngineering #CodingJourney Vignesh Reddy Julakanti

🔥 Day 364 – Daily DSA Challenge! 🔥 Problem: 🎯 Find K Closest Elements Given a sorted array arr, an integer k, and a target x, return the k closest elements to x in ascending order. 💡 Key Insight — Binary Search on Window Instead of checking each element, we binary search the starting index of a window of size k. Search space: Possible windows → [0 ... n - k] 🧠 Decision Logic At index mid, compare: Distance of left boundary → x - arr[mid] Distance of right boundary → arr[mid + k] - x We choose direction based on: ⚡ Algorithm Steps ✅ Initialize: left = 0, right = n - k ✅ Binary search: If left side is farther → shift right Else → move left ✅ Final window starts at left ✅ Collect k elements ⚙️ Complexity ✅ Time Complexity: O(log(n - k) + k) (binary search + result building) ✅ Space Complexity: O(k) 💬 Challenge for you 1️⃣ Why do we search on window positions instead of elements? 2️⃣ Can you solve this using a heap approach? 3️⃣ What if array was unsorted? #DSA #Day364 #LeetCode #BinarySearch #SlidingWindow #Arrays #Java #ProblemSolving #KeepCoding

🔥 Day 349 – Daily DSA Challenge! 🔥 Problem: 🧱 Pyramid Transition Matrix You are stacking blocks to form a pyramid. Each block is represented by a letter. Given a bottom row and a list of allowed triples "ABC" meaning: A B → C Return true if you can build the pyramid to the top. 💡 Key Insight — Bitmask + DFS Instead of storing allowed transitions as lists, we encode them using bitmasks. For each pair (A, B) we store possible top blocks using a bitmask. Conceptually: Example: ABC ABD mask[A][B] = {C, D} stored as bits. 🧠 Recursive Construction We build the pyramid row by row: 1️⃣ Current row → cur 2️⃣ Generate next row → next 3️⃣ For each adjacent pair (cur[i], cur[i+1]) check all possible blocks above 4️⃣ Recursively continue until: length = 1 → pyramid complete ⚡ Optimization Trick To extract possible blocks from bitmask: bit = m & -m This isolates the lowest set bit, letting us iterate through candidates efficiently. ⚙️ Complexity Let n be bottom length. ✅ Time Complexity: ~ O(7ⁿ) worst-case (pruned heavily) ✅ Space Complexity: O(n) recursion stack But pruning via allowed transitions keeps it practical. 💬 Challenge for you 1️⃣ Why does using bitmasks make transitions faster than lists? 2️⃣ How would you add memoization to avoid recomputing rows? 3️⃣ Can you solve this using DP with states instead of DFS? #DSA #Day349 #LeetCode #DFS #Bitmask #Backtracking #Java #ProblemSolving #KeepCoding

Day - 104 Recover Binary Search Tree The problem - You are given the root of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure. Follow up: A solution using O(n) space is pretty straight forward. Could you devise a constant O(1) space solution? Brute Force - Perform inorder traversal to collect all values in an array, identify the two swapped elements, store their positions, traverse the tree again to find and swap them back. This gives O(n) time and O(n) space for storing all node values. Approach Used - •) Declare first (first swapped node), second (second swapped node), prev (previous node in inorder traversal). •) Call helper function, helper(root). •) Swap the values, temp = first.val, first.val = second.val, second.val = temp. Helper Function - helper(TreeNode node) •) If node == null, return. •) Traverse left subtree, helper(node.left). •) If prev != null AND prev.val > node.val, - If first == null, set first = prev. - ⁠Set, second = node. •) Update, prev = node. •) Traverse right subtree, helper(node.right). Complexity - Time - O(n), where n is number of nodes. Space - O(h), recursion stack depth. Note - In a valid BST, inorder traversal produces a sorted sequence. When two nodes are swapped, it creates violations where prev.val > current.val. For adjacent swaps, there's one violation; for non-adjacent swaps, there are two. By tracking the first and second violating nodes during inorder traversal, we identify the swapped pair. The algorithm handles both cases by always updating second and only setting first once. #DSA #Java #SoftwareEngineering #InterviewPrep #LearnToCode #CodeDaily #ProblemSolving

🚀 **LeetCode Problem Solved – Max Consecutive Ones III** Today I solved **Problem 1004: Max Consecutive Ones III** using the **Sliding Window technique**. 🔹 **Problem Summary** Given a binary array `nums` containing 0s and 1s and an integer `k`, we are allowed to flip at most `k` zeros to ones. The goal is to determine the **maximum number of consecutive 1s** possible after performing at most `k` flips. 🔹 **Approach** Instead of checking every possible subarray, I used the **Sliding Window (Two Pointer) approach**: • Expand the window using the right pointer • Count the number of zeros in the window • If zeros exceed `k`, move the left pointer to maintain a valid window • Track the maximum window size 🔹 **Complexity** ⏱ Time Complexity: **O(n)** 💾 Space Complexity: **O(1)** 📊 **Result** ✔ 60 / 60 Testcases Passed ⚡ Runtime: **2 ms (Beats 99.93%)** Consistent practice with **Data Structures & Algorithms** helps build strong problem-solving skills and deeper understanding of algorithmic patterns. Always open to learning better approaches or optimizations! 💡 #LeetCode #DSA #Java #SlidingWindow #ProblemSolving #CodingJourney

Started the Merge Sort section today. Before understanding the full algorithm, the first thing was learning how to merge two already sorted arrays into one sorted array. This small piece of logic is actually the core operation behind Merge Sort. Things that became clear : - using two pointers to traverse both arrays - always placing the smaller element first - continuing until both arrays are fully processed - overall time complexity becomes O(m + n) Main merge logic : static void merge(int[] a, int[] b, int[] c) { int i = 0, j = 0, k = 0; while (i < a.length && j < b.length) { if (a[i] <= b[j]) c[k++] = a[i++]; else c[k++] = b[j++]; } while (i < a.length) c[k++] = a[i++]; while (j < b.length) c[k++] = b[j++]; } What seemed like a small helper function is actually the heart of Merge Sort, because the entire algorithm depends on merging smaller sorted pieces correctly. Understanding this step made the later recursion part much easier to follow. Continuing deeper into Merge Sort and divide-and-conquer next. #dsa #algorithms #mergesort #sorting #java #learninginpublic

🚀 Day 42 of #100DaysOfCode Solved 1508. Range Sum of Sorted Subarray Sums on LeetCode 📊 🧠 Problem Insight: Given an array, we must compute the sum of all subarray sums, sort them, and return the sum of elements between indices left and right. ⚙️ Approach Used: 1️⃣ Generate all possible subarray sums using nested loops 2️⃣ Store them in an array of size n*(n+1)/2 3️⃣ Sort the subarray sums 4️⃣ Compute the sum of elements from index left-1 to right-1 5️⃣ Apply mod = 1e9 + 7 to avoid overflow This approach works well because the total number of subarrays is manageable for the given constraints. ⏱️ Time Complexity: O(n² log n) O(n²) to generate subarray sums O(n² log n) to sort them 📦 Space Complexity: O(n²) #100DaysOfCode #LeetCode #DSA #Arrays #Algorithms #Java #CodingPractice #InterviewPrep

📌 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

📘 DSA Journey — Day 26 Today’s focus: Binary Search fundamentals. Problems solved: • Binary Search (LeetCode 704) • Search a 2D Matrix (LeetCode 74) Concepts used: • Binary Search • Search space reduction • Index mapping in 2D arrays Key takeaway: In Binary Search, the idea is to repeatedly divide the search space in half. By comparing the target with the middle element, we eliminate half of the array each time, achieving O(log n) time complexity. In Search a 2D Matrix, the matrix can be treated as a flattened sorted array. Using index mapping: row = mid / cols col = mid % cols we can apply binary search directly on the matrix without extra space. These problems highlight how binary search is not limited to 1D arrays—it can be extended to structured data with proper transformations. Continuing to strengthen fundamentals and consistency in DSA problem solving. #DSA #Java #LeetCode #CodingJourney

🔥 Day 96 of #100DaysOfCode Today’s problem: LeetCode – Find Minimum in Rotated Sorted Array 🔄📉 📌 Problem Summary You are given a sorted array that has been rotated at some pivot. Example: Sorted array → [1,2,3,4,5] Rotated → [3,4,5,1,2] Goal 👉 Find the minimum element in the array. Example: Input: [3,4,5,1,2] Output: 1 🧠 Approach: Binary Search Since the array was originally sorted, we can use Binary Search to locate the rotation point. Key observation: If nums[l] < nums[r] → Subarray is already sorted → Minimum is nums[l] Otherwise: Compute middle index Compare with left boundary to decide which half to search ⚙️ Decision Logic 1️⃣ If left part is sorted → Minimum must be in right half 2️⃣ If left part is not sorted → Minimum is in left half 💡 Key Idea We are essentially searching for the rotation pivot, which contains the smallest value. ⏱ Time Complexity: O(log n) 💾 Space Complexity: O(1) 🚀 Performance Runtime: 0 ms Beats 100% submissions 🔥 Memory: 43.8 MB 🧠 Pattern Insight Common Binary Search variants: Search in Rotated Sorted Array Find Minimum in Rotated Array Peak Element Binary Search on Answer Recognizing these patterns makes solving them much faster. Only 4 days left to complete #100DaysOfCode 🚀 Consistency paying off every day. On to Day 97 🔥 #100DaysOfCode #LeetCode #BinarySearch #RotatedArray #Java #DSA #InterviewPrep