Longest Common Prefix in Array of Strings

🚀 Day 43 of #100DaysOfCode Today’s problem focused on Strings + Arrays with a clean optimization trick — 🧵 Longest Common Prefix 📌 Problem Summary Given an array of strings, the goal is to find the longest prefix shared by all strings. If no common prefix exists, return an empty string. At first glance, it feels like a brute-force string comparison problem — but there’s a smarter way 💡 🧠 My Approach: Sorting + Boundary Comparison Key insight: After sorting the array of strings lexicographically: The first and last strings will be the most different The common prefix of the entire array must be the common prefix of just these two strings Steps: Sort the array Compare characters of the first and last strings Stop when characters mismatch Extract the prefix till that point This avoids unnecessary comparisons across all strings and keeps the solution elegant and efficient ✨ ⚙️ Complexity Analysis ⏱ Time: O(n log n + m) 💾 Space: O(1) (ignoring sort internals) (n = number of strings, m = length of shortest string) 🔥 Key Learning Sorting can simplify problems that seem comparison-heavy Often, extreme cases (first & last) reveal global properties Clean logic > brute force ✅ Solution accepted successfully with fast runtime, keeping the momentum strong 💪 Onward to Day 44 — consistency builds mastery 🚀 #100DaysOfCode #LeetCode #Strings #Arrays #Java #DSA #ProblemSolving #CodingJourney #Consistency

🚀 Day 67 of #100DaysOfCode Today’s problem focused on 2D Prefix Sum optimization — Range Sum Query 2D – Immutable (NumMatrix) 📊 At first glance, this problem looks like repeated matrix traversal, but the real win comes from preprocessing smartly. 📌 Problem Summary You’re given a 2D matrix and multiple queries asking for the sum of elements inside a sub-rectangle. Brute force would be too slow for repeated queries. 🧠 My Approach: Prefix Sum (Row-wise) Precompute prefix sums for each row For every query, calculate the sum in O(rows) time using prefix subtraction Avoid recalculating sums for every query This transforms repeated heavy computation into a fast query process ⚡ ⚙️ Time & Space Complexity Preprocessing: O(rows × cols) Each Query: O(rows) Space: O(rows × cols) 🔥 Key Learning Prefix sums are not limited to 1D arrays— they scale beautifully to 2D problems and are extremely powerful for range queries. Another solid step forward in mastering optimization techniques 💪 On to Day 68 🚀 #Day67 #100DaysOfCode #Java #LeetCode #PrefixSum #DSA #ProblemSolving #CodingJourney

🚀 Day 16 - 100Days of DSA Problem Statement : ✅ Sum of subarrays of size K ✅ Average of subarrays of size K At first, calculating the sum or average of every subarray looked simple… but using nested loops makes it slow and inefficient for large inputs. That’s when I learned about the Sliding Window technique – a powerful optimization used in many real-world and interview problems. 🧠 Approach: Sliding Window Technique 1️⃣ Create a window of size k 2️⃣ Calculate the sum of the first window 3️⃣ Slide the window one step at a time 4️⃣ Subtract the element going out 5️⃣ Add the element coming in Code template to solve similar problems: int maxSum=0,windowSum=0; List<Integer> list = new ArrayList<>(); for(int right=0;right<size;right++) { maxSum = maxSum+arr[right]; } list.add(maxSum); for(int right=size;right<arr.length;right++) { maxSum+=arr[right]; maxSum-=arr[right-size]; list.add(maxSum); } ⏱ Time & Space Complexity Time Complexity: 🟢 O(n) – each element is processed once Space Complexity: 🟢 O(1) – only a few variables used (constant extra space) #Day16 #SlidingWindow #DSA #Java #ProblemSolving #CodingJourney #JavaDeveloper #BackendDevelopment #Algorithms #Consistency

#200DaysOfCode – Day 111 Word Search Problem: Given a 2D grid of characters and a word, determine whether the word exists in the grid. The word must be formed using adjacent cells (up, down, left, right), and each cell can be used only once. Example: Input: board = [[A, B, C, E], [S, F, C, S], [A, D, E, E]] word = "ABCCED" Output: true My Approach: Used DFS (Depth First Search) starting from every cell. Matched characters step-by-step with the given word. Marked cells as visited during the path to avoid reuse. Applied backtracking to explore all possible directions safely. Time Complexity: O(m × n × 4^L) Space Complexity: O(L) (recursion stack) Grid problems often look complex, but breaking them down with DFS + backtracking makes the logic clear and manageable. Patience and careful state handling are the real keys here #takeUforward #100DaysOfCode #Java #LeetCode #ProblemSolving #Backtracking #DFS #DataStructures #Algorithms #CodeNewbie #Consistency

Day 33/100 – LeetCode Challenge ✅ Problem: #1292 Maximum Side Length of a Square with Sum Less than or Equal to Threshold Difficulty: Medium Language: Java Approach: Prefix Sum + Binary Search on Square Size Time Complexity: O(m × n × log(min(m, n))) Space Complexity: O(m × n) Key Insight: Use 2D prefix sum to quickly compute sum of any square submatrix in O(1). For each cell, binary search the maximum square side length starting at that cell with sum ≤ threshold. Solution Brief: Built prefix sum matrix psum for O(1) submatrix sum queries. For each possible starting cell, used binary search to find largest valid square. Tracked global maximum side length across all positions. Optimizing submatrix queries with prefix sum. #LeetCode #Day33 #100DaysOfCode #BinarySearch #Java #Algorithm #CodingChallenge #ProblemSolving #MaxSquareSide #MediumProblem #PrefixSum #Matrix #Optimization #DSA

🚀 Day 57 of #100DaysOfCode Solved LeetCode Problem #2943 – Maximize Area of Square Hole in Grid. This problem focused on identifying the largest possible square that can be formed after removing horizontal and vertical bars from a grid. The key was to analyze consecutive gaps efficiently and translate them into the maximum square area. Key Learnings: -> Sorting input arrays to simplify gap analysis -> Tracking longest consecutive segments in both dimensions -> Understanding how grid constraints map directly to square geometry -> Writing clean, optimal logic for interval-based problems Language Used: Java -> Runtime: 4 ms (Beats 100.00%) -> Memory: 45.45 MB (Beats 50.00%) Consistent problem-solving, sharper logic, one day at a time 🚀 #LeetCode #Arrays #Geometry #Java #ProblemSolving #100DaysOfCode

📅 Day 62 of #100DaysOfLeetCode 🔢 Problem: 1458. Max Dot Product of Two Subsequences 🟥 Difficulty: Hard 🧠 Problem Summary Given two integer arrays, find the maximum dot product between non-empty subsequences of equal length while preserving order. 💡 Key Insight This problem is a DP + subsequence variant similar to LCS, but with an important twist: 👉 The answer can be negative, so initializing DP with 0 will fail. 👉 We must ensure at least one pair is chosen. 🚀 Approach (Memoization / Top-Down DP) Use recursion with indices (i, j) At each step, consider: Pairing nums1[i] with nums2[j] Skipping an element from either array Use Math.max(0, previous) to avoid extending negative subsequences Memoize results to achieve O(n × m) complexity ⏱ Complexity Time: O(n × m) Space: O(n × m) #LeetCode #Java #ProblemSolving #CodingChallenge #100DaysOfCode #DSA #LearningEveryday

Day - 35 Isomorphic Strings The problem - Two strings s and t are isomorphic if the characters in s can be replaced to get t. All occurrences of a character must be replaced with another character while preserving the order. No two characters may map to the same character, but a character may map to itself. Example : s = "egg", t = "add" → true (e→a, g→d) s = "foo", t = "bar" → false (o cannot map to both a and r) Brute force - Try all possible character mappings, exponential complexity. Approach Used - Used Index Tracking Arrays •) Create two arrays of size 200 to store last seen index - indexS[200] tracks last position of each character in s. indexT[200] tracks last position of each character in t. •) Check if lengths are equal - if not, return false. •) Iterate through both strings (index i from 0 to len) •) Get characters: s.charAt(i) and t.charAt(i), check if indexS[s.charAt(i)] != indexT[t.charAt(i)] 1 - If different, the pattern doesn't match → return false. 2 - Update both arrays, indexS[s.charAt(i)] = i + 1, indexT[t.charAt(i)] = i + 1. •) If loop completes, return true. Complexity - Time - O(n), single pass through strings. Space - O(1), fixed-size arrays (200 elements). Note - Track the last position where each character appeared. If patterns don't match, strings aren't isomorphic! #DSA #Java #SoftwareEngineering #InterviewPrep #LearnToCode #CodeDaily #ProblemSolving

🚀 Day 46/50 – LeetCode POTD 🔍 3. Longest Substring Without Repeating Characters 📊 Medium 🧠 Key Idea (Sliding Window + Two Pointers) Whenever a problem asks for a substring without repeating characters, the best approach is 👉 Sliding Window. ✔️ Use two pointers: left (l) and right (r) ✔️ Use a boolean array (arr[128]) to track characters (ASCII set) ✔️ If the current character is not present in the window ➡️ expand the window (r++) ➡️ update the maximum length ✔️ If a duplicate character is found ➡️ shrink the window from the left (l++) ➡️ remove characters until the duplicate is gone ✔️ The window always contains unique characters 📌 Example s = "abcabcbb" ➡️ Longest substring = "abc" ➡️ Output = 3 ⚙️ How the Code Works (Java) arr[ch] = true → character exists in the current window On duplicate → move the left pointer and clear characters Track the answer using maxLen = Math.max(maxLen, r - l + 1) ⚙️ Complexity Analysis ⏱ Time Complexity: O(n) 💾 Space Complexity: O(1) (fixed-size array of 128 characters) 💡 Key Takeaway “Substring + uniqueness constraint” ➡️ Think Sliding Window ➡️ Two pointers give an optimal linear-time solution ➡️ Avoid brute force and nested loops 🔁 Consistency beats motivation 🚀 #LeetCode #DSA #SlidingWindow #TwoPointers #Strings #Java #ProblemSolving #CodingJourney #50DaysChallenge

🔥 Day 83/100 of Code – Substrings Containing All Three Characters: Counting with Minimal Valid Window! Today solved a substring counting problem by leveraging the "minimal valid window" property: ✅ Problem 1358: Number of Substrings Containing All Three Characters Task: Count substrings containing at least one a, b, and c. Approach: Sliding window with earliest valid start tracking: For each ending index r, find the smallest l such that s[l..r] contains all three chars Once found, all substrings starting from 0..l and ending at r are valid → add l+1 to count Use a frequency map or array to track counts of a,b,c and shrink window when possible Key Insight: If the minimal valid window ending at r starts at minStart, then any substring starting before minStart and ending at r also contains all three characters — giving minStart + 1 valid substrings per r. Complexity: O(n) time, O(1) space — efficient single pass. A smart counting trick that turns a "contain all" constraint into an elegant O(n) accumulation! 🔤🔢 #100DaysOfCode #LeetCode #Java #SlidingWindow #String #SubstringCounting #Algorithm