Krupesh Patil’s Post

🚀 𝐂𝐨𝐦𝐩𝐞𝐭𝐢𝐭𝐢𝐯𝐞 𝐏𝐫𝐨𝐠𝐫𝐚𝐦𝐦𝐢𝐧𝐠 | 𝐋𝐢𝐧𝐞𝐚𝐫 𝐒𝐞𝐚𝐫𝐜𝐡 + 𝐆𝐫𝐞𝐞𝐝𝐲 𝐓𝐡𝐢𝐧𝐤𝐢𝐧𝐠 | 𝐌𝐢𝐧𝐢𝐦𝐮𝐦 𝐂𝐚𝐩𝐚𝐜𝐢𝐭𝐲 𝐁𝐨𝐱 📦 📌 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝐒𝐭𝐚𝐭𝐞𝐦𝐞𝐧𝐭: You are given: An integer array capacity[] An integer itemSize Each box can store the item only if: capacity[i] >= itemSize We need to return: ✅ The index of the box with the minimum valid capacity ✅ If multiple boxes have the same minimum capacity, return the smallest index ✅ Return -1 if no valid box exists 🧠 𝐊𝐞𝐲 𝐎𝐛𝐬𝐞𝐫𝐯𝐚𝐭𝐢𝐨𝐧𝐬 🔹 We only care about boxes whose capacity is greater than or equal to itemSize 🔹 Among all valid boxes, we need the one with: Minimum capacity Smallest index in case of ties 🔹 This can be solved efficiently using a single traversal ⚡ 𝐎𝐩𝐭𝐢𝐦𝐚𝐥 𝐀𝐩𝐩𝐫𝐨𝐚𝐜𝐡: Steps: 1️⃣ Traverse the array 2️⃣ Check whether the current box can store the item 3️⃣ Maintain: Minimum valid capacity found so far Corresponding index 4️⃣ Update answer whenever a smaller valid capacity is found ⏱️ Complexity Analysis ✅ Time Complexity: O(N) ✅ Space Complexity: O(1) 🔗 Optimal Approach Code https://lnkd.in/gGSb83Hh ------- I post DSA problems (1x daily) Hit the 🔔 icon → Select “𝐀𝐥𝐥” to get the link first Follow ( Krupesh Patil ) 💙 Like | ♻️ Repost | 💬 Comment ------- #CompetitiveProgramming #CPP #DataStructures #Algorithms #Coding #ProblemSolving #DSA #Programming #CodeNewbie #Developer

🚀 𝐂𝐨𝐦𝐩𝐞𝐭𝐢𝐭𝐢𝐯𝐞 𝐏𝐫𝐨𝐠𝐫𝐚𝐦𝐦𝐢𝐧𝐠 |𝐒𝐮𝐛𝐚𝐫𝐫𝐚𝐲 𝐒𝐮𝐦𝐬 𝐃𝐢𝐯𝐢𝐬𝐢𝐛𝐥𝐞 𝐛𝐲 𝐊 | 𝐄𝐟𝐟𝐢𝐜𝐢𝐞𝐧𝐭 𝐏𝐫𝐞𝐟𝐢𝐱 𝐒𝐮𝐦 + 𝐇𝐚𝐬𝐡𝐢𝐧𝐠 𝐚𝐩𝐩𝐫𝐨𝐚𝐜𝐡 📌 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝐒𝐭𝐚𝐭𝐞𝐦𝐞𝐧𝐭: Given an integer array nums and an integer k, return the number of non-empty subarrays whose sum is divisible by k. This problem looks tricky at first, but with the right observation, it can be solved in linear time ⚡ 🔍 𝐊𝐞𝐲 𝐎𝐛𝐬𝐞𝐫𝐯𝐚𝐭𝐢𝐨𝐧: If two prefix sums have the same remainder when divided by k, then the subarray between them will have a sum divisible by k. Mathematical Insight: If: prefixSum[i] % k == prefixSum[j] % k Then: (prefixSum[j] - prefixSum[i]) % k == 0 Which means the subarray between i+1 and j is divisible by k. ✅ 𝐎𝐩𝐭𝐢𝐦𝐚𝐥 𝐀𝐩𝐩𝐫𝐨𝐚𝐜𝐡 : 🔹 Prefix Sum + Hashing (Unordered Map) Steps: ✔️ Maintain running prefix sum ✔️ Compute remainder rem = sum % k ✔️ Handle negative remainders carefully ✔️ Store frequency of each remainder in hash map ✔️ If same remainder appears again → add previous frequency to answer ⏱️ Complexity Analysis Time Complexity: O(N) Space Complexity: O(K) (or O(N) in worst case) 💻 Optimal Code Link: https://lnkd.in/gvGn4E_7 ------- I post DSA problems (1x daily) Hit the 🔔 icon → Select “All” to get the link first Follow ( Krupesh Patil ) 💙 Like | ♻️ Repost | 💬 Comment ------- #PrefixSum #Hashing #ModuloArithmetic #SlidingWindow #CompetitiveProgramming #DSA #Cpp #ProblemSolving #Algorithms #Coding #DataStructures #Programmer

🚀 𝐇𝐚𝐬𝐡𝐢𝐧𝐠 + 𝐅𝐫𝐞𝐪𝐮𝐞𝐧𝐜𝐲 𝐂𝐨𝐮𝐧𝐭 = 𝐏𝐨𝐰𝐞𝐫𝐟𝐮𝐥 𝐒𝐭𝐫𝐢𝐧𝐠 𝐏𝐫𝐨𝐜𝐞𝐬𝐬𝐢𝐧𝐠 𝐓𝐞𝐜𝐡𝐧𝐢𝐪𝐮𝐞 𝐢𝐧 𝐂𝐨𝐦𝐩𝐞𝐭𝐢𝐭𝐢𝐯𝐞 𝐏𝐫𝐨𝐠𝐫𝐚𝐦𝐦𝐢𝐧𝐠 📌 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝐒𝐭𝐚𝐭𝐞𝐦𝐞𝐧𝐭: Given an array of strings, return all characters that appear in every string, including duplicates. Example: Input: ["bella","label","roller"] Output: ["e","l","l"] 🔍 𝐎𝐩𝐭𝐢𝐦𝐚𝐥 𝐀𝐩𝐩𝐫𝐨𝐚𝐜𝐡 (𝐇𝐚𝐬𝐡𝐢𝐧𝐠 + 𝐅𝐫𝐞𝐪𝐮𝐞𝐧𝐜𝐲 𝐂𝐨𝐮𝐧𝐭): Instead of comparing every character manually between strings, we use: ✅ Frequency Map (Hashing) ✅ Minimum Frequency Tracking ✅ Character-wise Processing from 'a' to 'z' 💡 Core Idea: Count frequency of each character in every word. Maintain the minimum occurrence of every character across all words. The minimum frequency tells how many times a character should appear in the final answer. ⚡ Why This Approach is Efficient? ✔ Avoids unnecessary comparisons ✔ Works efficiently even for larger inputs ✔ Uses constant alphabet size (26 lowercase letters) ⏱ Time Complexity: O(N * L) Where: N = number of words L = average length of each word Since alphabet size is fixed (26), the solution remains highly optimized 🚀 🧠 𝐊𝐞𝐲 - 𝐋𝐞𝐚𝐫𝐧𝐢𝐧𝐠: This problem is a great example of: Hashing Frequency Counting String Processing Minimum Frequency Logic Efficient Data Structure Usage 🔗 Code Link: https://lnkd.in/gqnyiFVJ #CompetitiveProgramming #DSA #Hashing #Cpp #Coding #ProblemSolving #Algorithms #Programming #Codeforces #DataStructures #SoftwareEngineering #Coding #Strings

🚀 𝐂𝐨𝐦𝐩𝐞𝐭𝐢𝐭𝐢𝐯𝐞 𝐏𝐫𝐨𝐠𝐫𝐚𝐦𝐦𝐢𝐧𝐠 | 𝐌𝐚𝐱 𝐍𝐮𝐦𝐛𝐞𝐫 𝐨𝐟 𝐊-𝐒𝐮𝐦 𝐏𝐚𝐢𝐫𝐬 𝐮𝐬𝐢𝐧𝐠 𝐇𝐚𝐬𝐡𝐢𝐧𝐠 + 𝐅𝐫𝐞𝐪𝐮𝐞𝐧𝐜𝐲 𝐂𝐨𝐮𝐧𝐭𝐢𝐧𝐠  Instead of checking every pair using brute force O(n²), we can optimize the solution using Hash Maps / Hashing and solve it in O(n) time complexity ⚡ 🔹 𝐊𝐞𝐲 𝐋𝐞𝐚𝐫𝐧𝐢𝐧𝐠 𝐏𝐨𝐢𝐧𝐭𝐬: ✅ Frequency counting using hashing ✅ Complement technique (partner = k - number) ✅ Handling duplicate values efficiently ✅ Avoiding double counting of pairs ✅ Optimized competitive programming approach 📌 𝐀𝐩𝐩𝐫𝐨𝐚𝐜𝐡 𝐔𝐬𝐞𝐝: • Store frequency of each element in an unordered map • For every number x, find its partner k - x • If both exist, form valid pairs • Special handling when x == partner • Count maximum operations efficiently ⏱ Time Complexity: O(n) 📦 Space Complexity: O(n) 🧠 Problem Solving Pattern: Hashing + Frequency Array + Pair Matching 💻 Optimal Approach Code Link: https://lnkd.in/gnPgiymY ------- I post DSA problems (1x daily) Hit the 🔔 icon → Select “𝐀𝐥𝐥” to get the link first Follow ( Krupesh Patil ) 💙 Like | ♻️ Repost | 💬 Comment ------- #CompetitiveProgramming #Coding #DSA #Hashing #Cpp #LeetCode #Programming #ProblemSolving #Algorithms #DataStructures #SoftwareEngineer #Developer #CodingJourney

🚀 𝐂𝐨𝐦𝐩𝐞𝐭𝐢𝐭𝐢𝐯𝐞 𝐏𝐫𝐨𝐠𝐫𝐚𝐦𝐦𝐢𝐧𝐠 | 𝐇𝐚𝐬𝐡𝐢𝐧𝐠 𝐓𝐞𝐜𝐡𝐧𝐢𝐪𝐮𝐞 + 𝐅𝐫𝐞𝐪𝐮𝐞𝐧𝐜𝐲 𝐌𝐚𝐩 | 𝐂𝐨𝐮𝐧𝐭 𝐍𝐮𝐦𝐛𝐞𝐫 𝐨𝐟 𝐏𝐚𝐢𝐫𝐬 𝐖𝐢𝐭𝐡 𝐀𝐛𝐬𝐨𝐥𝐮𝐭𝐞 𝐃𝐢𝐟𝐟𝐞𝐫𝐞𝐧𝐜𝐞 𝐊 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝐒𝐭𝐚𝐭𝐞𝐦𝐞𝐧𝐭:  Count Number of Pairs With Absolute Difference K Given an integer array nums and an integer k, we need to count the number of pairs (i, j) such that: i < j |nums[i] - nums[j]| == k At first glance, a brute-force solution using nested loops seems straightforward, but it results in O(n²) time complexity, but it is not efficient for larger constraints. 💡 𝐎𝐩𝐭𝐢𝐦𝐚𝐥 𝐀𝐩𝐩𝐫𝐨𝐚𝐜𝐡 𝐔𝐬𝐢𝐧𝐠 𝐇𝐚𝐬𝐡𝐢𝐧𝐠 To optimize the solution, I used a Hash Map / Frequency Map approach. ✅ Key Idea: While traversing the array: Check whether (currentElement - k) already exists. Check whether (currentElement + k) already exists. Add their frequencies to the answer. Store/update the current element frequency in the hash map. ⚡ Time Complexity O(n) — Single traversal using hashing. ⚡ Space Complexity O(n) — For storing frequencies in the hash map. 🧠 Concepts Used ✔️ Hashing ✔️ Frequency Map ✔️ Array Traversal ✔️ Optimization from Brute Force to Optimal 🔗 Optimal Approach Code Link 👉 https://lnkd.in/gBe4ubet ------- I post DSA problems (1x daily) Hit the 🔔 icon → Select “𝐀𝐥𝐥” to get the link first Follow ( Krupesh Patil ) 💙 Like | ♻️ Repost | 💬 Comment ------- #CompetitiveProgramming #DSA #Hashing #Cpp #Programming #Coding #ProblemSolving #DataStructures #Algorithms #FrequencyMap #SoftwareEngineering

🚀 𝐂𝐨𝐦𝐩𝐞𝐭𝐢𝐭𝐢𝐯𝐞 𝐏𝐫𝐨𝐠𝐫𝐚𝐦𝐦𝐢𝐧𝐠 | 𝐇𝐚𝐬𝐡𝐢𝐧𝐠 + 𝐒𝐭𝐫𝐢𝐧𝐠 𝐩𝐫𝐨𝐛𝐥𝐞𝐦 | 𝐅𝐢𝐫𝐬𝐭 𝐔𝐧𝐢𝐪𝐮𝐞 𝐂𝐡𝐚𝐫𝐚𝐜𝐭𝐞𝐫 𝐢𝐧 𝐚 𝐒𝐭𝐫𝐢𝐧𝐠 💡 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝐒𝐭𝐚𝐭𝐞𝐦𝐞𝐧𝐭: Given a string s, find the first non-repeating character and return its index. If every character repeats, return -1. 🧠 𝐎𝐩𝐭𝐢𝐦𝐚𝐥 𝐀𝐩𝐩𝐫𝐨𝐚𝐜𝐡 (𝐇𝐚𝐬𝐡𝐢𝐧𝐠) To solve this efficiently: ✅ First, count the frequency of every character using a hash map. ✅ Then traverse the string again and find the first character whose frequency is 1. ✅ Return its index immediately. This approach helps us solve the problem in O(N) time complexity, which is optimal for this constraint. ⚡ Why This Problem is Important? 🔹 Frequency Counting 🔹 Hashing Concepts 🔹 String Traversal 🔹 Optimization from Brute Force to Linear Time 📌 𝐊𝐞𝐲 𝐋𝐞𝐚𝐫𝐧𝐢𝐧𝐠 Instead of checking every character multiple times, hashing stores frequencies efficiently and avoids unnecessary repeated work. That’s the power of Hash Maps in Competitive Programming 💯 ⏱ Complexity Analysis ✔ Time Complexity: O(N) ✔ Space Complexity: O(1) 🔗 Optimal Approach Code Link: https://lnkd.in/gNKvMYUs #CompetitiveProgramming #DSA #Hashing #Cpp #Coding #Programming #LeetCode #ProblemSolving #SoftwareEngineering #CodingInterview #Algorithms #DataStructures #Developer #Strings #Learning #Tech

🚀𝐂𝐨𝐦𝐩𝐞𝐭𝐢𝐭𝐢𝐯𝐞 𝐏𝐫𝐨𝐠𝐫𝐚𝐦𝐦𝐢𝐧𝐠 | 𝐇𝐚𝐬𝐡𝐢𝐧𝐠 + 𝐓𝐰𝐨 𝐏𝐨𝐢𝐧𝐭𝐞𝐫 𝐀𝐩𝐩𝐫𝐨𝐚𝐜𝐡 | 𝐓𝐫𝐢𝐩𝐥𝐞𝐭 𝐒𝐮𝐦 𝐢𝐧 𝐀𝐫𝐫𝐚𝐲 🔍 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝐒𝐭𝐚𝐭𝐞𝐦𝐞𝐧𝐭 Given an array arr[] and an integer target, determine whether there exists a triplet in the array such that: arr[i] + arr[j] + arr[k] = target Return: true → if such a triplet exists false → otherwise 💡 𝐎𝐩𝐭𝐢𝐦𝐚𝐥 𝐀𝐩𝐩𝐫𝐨𝐚𝐜𝐡 ✅ Sorting + Two Pointer Technique The idea is: Sort the array. Fix one element arr[i]. Use two pointers (left and right) on the remaining subarray. Compare the current sum with the target: If sum matches → triplet found. If sum is smaller → move left pointer. If sum is larger → move right pointer. This approach avoids unnecessary computations and works efficiently for large constraints. ⚡ Time Complexity Sorting: O(n log n) Two Pointer Traversal: O(n²) Overall Complexity: O(n²) 📦 Space Complexity O(1) (excluding sorting space) 📘 Example Input: arr[] = [1, 4, 45, 6, 10, 8] target = 13 Output: true Explanation: Triplet {1, 4, 8} gives the required sum 13. 🔗 Optimal Approach Code https://lnkd.in/gF3Nk6Mj ------- I post DSA problems (1x daily) Hit the 🔔 icon → Select “All” to get the link first Follow ( Krupesh Patil ) 💙 Like | ♻️ Repost | 💬 Comment ------- #CompetitiveProgramming #DSA #CPP #Coding #LeetCode #ProblemSolving #Algorithms #DataStructures #Coding #Programmer

🚀𝐂𝐨𝐦𝐩𝐞𝐭𝐢𝐭𝐢𝐯𝐞 𝐏𝐫𝐨𝐠𝐫𝐚𝐦𝐦𝐢𝐧𝐠 | 𝐇𝐚𝐬𝐡𝐢𝐧𝐠 + 𝐒𝐥𝐢𝐝𝐢𝐧𝐠 𝐖𝐢𝐧𝐝𝐨𝐰 𝐩𝐚𝐭𝐭𝐞𝐫𝐧 | 𝐌𝐚𝐱𝐢𝐦𝐮𝐦 𝐒𝐮𝐦 𝐨𝐟 𝐃𝐢𝐬𝐭𝐢𝐧𝐜𝐭 𝐒𝐮𝐛𝐚𝐫𝐫𝐚𝐲𝐬 𝐖𝐢𝐭𝐡 𝐋𝐞𝐧𝐠𝐭𝐡 𝐊 🧩 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝐒𝐭𝐚𝐭𝐞𝐦𝐞𝐧𝐭: Given an integer array nums and an integer k, find the maximum sum among all subarrays of size k such that: ✔️ All elements inside the subarray are distinct ✔️ Subarray length must be exactly k If no valid subarray exists, return 0. 💡 𝐊𝐞𝐲 𝐎𝐛𝐬𝐞𝐫𝐯𝐚𝐭𝐢𝐨𝐧 Instead of checking every subarray repeatedly, we can: 🔹 Maintain a sliding window of size k 🔹 Track frequencies using a hash map 🔹 Keep updating the current window sum 🔹 If hash map size becomes k, it means all elements are unique 🎯 This avoids recalculating sums and duplicate checks again and again. ⚡ 𝐎𝐩𝐭𝐢𝐦𝐚𝐥 𝐀𝐩𝐩𝐫𝐨𝐚𝐜𝐡 🔹 Techniques Used: Sliding Window Hashing (unordered_map) Frequency Counting 🔹 Time Complexity: O(N) 🔹 Space Complexity: O(K) 🧠 What I Learned This problem teaches an important CP concept: “Whenever you need continuous subarray processing with uniqueness checks, think of Sliding Window + Hashing.” This pattern appears frequently in: Distinct subarray problems Longest substring questions Frequency-based window problems Interview coding rounds 🔗 Optimal C++ Code 💻 CODE LINK: https://lnkd.in/gzN86-wC ------- I post DSA problems (1x daily) Hit the 🔔 icon → Select “𝐀𝐥𝐥” to get the link first Follow ( Krupesh Patil ) 💙 Like | ♻️ Repost | 💬 Comment ------- #CompetitiveProgramming #DSA #Cpp #Hashing #SlidingWindow #Coding #Algorithms #DataStructures #Programmer #Coding #ProblemSolving #CP #Tech

🚀 𝐂𝐨𝐦𝐩𝐞𝐭𝐢𝐭𝐢𝐯𝐞 𝐏𝐫𝐨𝐠𝐫𝐚𝐦𝐦𝐢𝐧𝐠 | 𝐒𝐭𝐫𝐢𝐧𝐠 + 𝐇𝐚𝐬𝐡𝐢𝐧𝐠 | 𝐍𝐮𝐦𝐛𝐞𝐫 𝐨𝐟 𝐏𝐚𝐢𝐫𝐬 𝐨𝐟 𝐒𝐭𝐫𝐢𝐧𝐠𝐬 𝐖𝐢𝐭𝐡 𝐂𝐨𝐧𝐜𝐚𝐭𝐞𝐧𝐚𝐭𝐢𝐨𝐧 𝐄𝐪𝐮𝐚𝐥 𝐭𝐨 𝐓𝐚𝐫𝐠𝐞𝐭 🔍 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝐒𝐭𝐚𝐭𝐞𝐦𝐞𝐧𝐭: Given an array of digit strings nums and a target string target, we need to find the number of pairs (i, j) such that: i != j nums[i] + nums[j] == target 𝐁𝐫𝐮𝐭𝐞 𝐅𝐨𝐫𝐜𝐞 𝐀𝐩𝐩𝐫𝐨𝐚𝐜𝐡: This solution would check every pair (i, j) and concatenate strings. Time Complexity: O(N² × K) Where: N = number of strings K = string concatenation/comparison cost This becomes inefficient for larger inputs. ⚡ 𝐎𝐩𝐭𝐢𝐦𝐚𝐥 𝐇𝐚𝐬𝐡𝐢𝐧𝐠 𝐀𝐩𝐩𝐫𝐨𝐚𝐜𝐡 ✅ Idea Use a frequency map (unordered_map) to store how many times each string appears. For every string s in nums: Check if target starts with s Find the remaining suffix needed Search that suffix directly in the hash map Add its frequency to the answer Avoid pairing the same index with itself ⏱️ Complexity Analysis Time Complexity: O(N × K) Space Complexity: O(N) 📌 Concepts Used Hashing / unordered_map String prefix checking String manipulation Frequency counting Competitive Programming Optimization 💻 Optimal C++ Code CODE LINK: https://lnkd.in/gdfqzscA ------- I post DSA problems (1x daily) Hit the 🔔 icon → Select “All” to get the link first Follow ( Krupesh Patil ) 💙 Like | ♻️ Repost | 💬 Comment ------- #CompetitiveProgramming #DSA #Cpp #Hashing #LeetCode #Coding #ProblemSolving #Algorithms #DataStructures #Programming #SoftwareEngineering