Boyer-Moore Voting Algorithm for Majority Element

🔥 Day 346 – Daily DSA Challenge! 🔥 Problem: ⚡ Total Hamming Distance The Hamming distance between two integers is the number of bit positions where they differ. Given an integer array nums, return the sum of Hamming distances between all pairs. 💡 Key Insight — Count Bits Column-wise Instead of comparing every pair (O(n²)), analyze each bit position independently. For a given bit: Let ones = number of elements with that bit = 1 Let zeros = n - ones Each pair of (1,0) contributes 1 to Hamming distance. Total contribution for that bit: Sum this for all 32 bits. For each bit column we count ones × zeros and add them. ⚡ Algorithm ✅ Iterate through 32 bit positions ✅ Count how many numbers have that bit set ✅ Compute contribution ones × (n − ones) ✅ Add to result ⚙️ Complexity ✅ Time Complexity: O(32 × n) ≈ O(n) ✅ Space Complexity: O(1) 💬 Challenge for you 1️⃣ Why does this approach avoid pairwise comparison? 2️⃣ How would this change for 64-bit numbers? 3️⃣ Can this be extended to compute XOR sum of all pairs? #DSA #Day346 #LeetCode #BitManipulation #HammingDistance #Math #Java #ProblemSolving #KeepCoding

Day 21/100 of DSA , (Arrays) 🚀Today I tackled the “Set Matrix Zeroes” problem At first, the brute force approach is tempting: traverse the matrix and use extra space to track zeros. Instead, I focused on the logic behind minimizing space: 🔹 Using the first row and first column as markers 🔹 Traversing carefully to avoid overwriting important values 🔹 Setting zeros in-place without extra arrays This problem is a reminder that optimization is not just about speed, but also about smart memory usage. 💡 Key takeaways: Think about what can be reused instead of creating new structures Always consider edge cases in 2D arrays Small logical adjustments make a big difference in performance Another step forward in mastering DSA fundamentals and improving problem-solving efficiency. 🚀 #DSA #Java #ProblemSolving #MatrixProblems #CodingJourney #InterviewPreparation #OptimizedCode

🔥 Day 353 – Daily DSA Challenge! 🔥 Problem: 🔍 Single Element in a Sorted Array Given a sorted array where every element appears twice except one, find that single element in O(log n) time. 💡 Key Insight — Binary Search on Pairs In a perfect paired array: Pairs start at even indices Pattern breaks at the single element We use binary search to detect where this pattern breaks. 🧠 Core Observation Before the single element: pairs → (even, odd) After the single element: pairs shift → (odd, even) So we normalize mid: if mid is odd → make it even ⚡ Algorithm Logic ✅ Find mid ✅ Make mid even ✅ Compare: If nums[mid] == nums[mid+1] → move right Else → move left This narrows down to the single element. ⚙️ Complexity ✅ Time Complexity: O(log n) ✅ Space Complexity: O(1) 💬 Challenge for you 1️⃣ Why do we force mid to be even? 2️⃣ How would you solve this using XOR in O(n)? 3️⃣ What if elements appear thrice except one? #DSA #Day353 #LeetCode #BinarySearch #Arrays #Optimization #Java #ProblemSolving #KeepCoding

Imagine finding the longest number streak in an unsorted array. For example: [100, 4, 200, 1, 3, 2] Can you spot the longest consecutive sequence? 🚀 Day 67/365 — DSA Challenge Solved: Longest Consecutive Sequence The goal: Find the length of the longest sequence of consecutive numbers. Example: Input [100,4,200,1,3,2] Consecutive sequence: [1,2,3,4] Output: 4 💡 My Approach I solved it in two main steps. Step 1 — Sort the array Since the numbers are unsorted, I first sorted the array using bubble sort. Example after sorting: [1,2,3,4,100,200] Step 2 — Count consecutive numbers Then I looped through the array: • If current number = previous + 1 → increase count • If numbers are equal → skip duplicates • Otherwise → reset count While traversing, I kept track of the longest sequence length. This problem reminded me: Sometimes sorting first makes pattern detection much easier. Day 67/365 complete. Code 👇 https://lnkd.in/dad5sZfu #DSA #Java #LeetCode #LearningInPublic #ProblemSolving #Consistency

Day 53 of My DSA Journey Today I solved a problem on searching an element in a rotated sorted array with duplicates. The array is originally sorted but rotated at some pivot. The task is to determine whether a given target value exists in the array. 🔎 My Approach Instead of directly jumping to complex techniques, I used a simple linear search approach: Traverse through the array from start to end. Compare each element with the target value. If a match is found, return true. If the loop finishes without finding the target, return false. 💡 Key Takeaway Sometimes starting with a simple and correct solution is important before optimizing. While more efficient approaches like modified binary search can reduce time complexity, this straightforward method helps clearly understand the problem first. ⏱ Time Complexity: O(n) Every day I’m improving my problem-solving skills in Java and Data Structures & Algorithms step by step. #Day53 #DSA #Java #ProblemSolving #CodingJourney #LeetCode #100DaysOfCode

DSA Challenge – Day 21 🚀 Continuing my Data Structures & Algorithms journey, today I solved the problem “Check if Binary String Has at Most One Segment of Ones.” 🔎 Problem Summary: Given a binary string s without leading zeros, determine whether it contains at most one contiguous segment of '1's. 💡 Approach: The key observation is that if multiple segments of '1' exist, the string will contain the pattern "01". So, by checking whether the string contains "01", we can easily determine if there is more than one segment of '1'. If "01" is present → multiple segments → return false If "01" is absent → only one segment → return true ⚡ Time Complexity: O(n) 📦 Space Complexity: O(1) 📈 Key Takeaway: Sometimes the most efficient solutions come from identifying simple patterns within the data rather than overcomplicating the logic. Looking forward to solving more problems and strengthening my problem-solving skills every day. #DSA #ProblemSolving #Java #CodingChallenge #SoftwareDevelopment #LearningInPublic

Day 12 #SDE Problems combining Binary Search on answer space and advanced counting techniques. Solved: • Nth Magical Number • Count of Smaller Numbers After Self Key Learning: Revisited how Binary Search + LCM/GCD concepts help in solving number-based problems efficiently. Also explored how modifying Merge Sort / using data structures can help count smaller elements after each index — a very important interview pattern. #LeetCode #DSA #BinarySearch #Algorithms #Java #SoftwareEngineering

Day 48 of my 365-Day DSA Challenge ✅ Problem: Subarray Sum Equals K (Medium) today. The naive approach? O(n²) brute force — check every subarray. Works, but dies on large inputs. The insight that changes everything 👇 Prefix Sum + HashMap Instead of checking every pair, ask a smarter question: "Have I seen a prefix sum of (currentSum - k) before?" If yes → there's a subarray ending right here that sums to k. map.put(0, 1); // empty subarray base case for each element: sum += nums[i] count += map.getOrDefault(sum - k, 0) map.merge(sum, 1, Integer::sum) The map.put(0, 1) seed is the key move handles subarrays starting from index 0. Result: O(n) time, O(n) space from brute force to optimal in one mental shift. The pattern: stop thinking about subarrays, start thinking about prefix differences. That one reframe unlocks a whole class of problems. 365 days. One problem at a time. 🚀 #DSA #Java #LeetCode #365DayChallenge #CodingJourney #SoftwareEngineering #ProblemSolving

🧠 Day 176 — Serialize & Deserialize Binary Tree 🌳 Today I revised one of the most interesting tree design problems in DSA: Serialize and Deserialize Binary Tree. The goal is simple but powerful: ✔ Convert a Binary Tree → String ✔ Reconstruct the exact same Tree → from that String This concept is used in many systems like data storage, network transmission, and distributed systems where tree structures must be preserved. Every node is processed exactly once. 💡 Key Takeaway This problem is a great example of combining: • Tree Traversal • Recursion • Data Structure Design Understanding how to encode and decode structures is a powerful concept used in real-world systems. 🚀 DSA Journey Update Slowly building strong foundations in Dynamic Programming and Trees. Consistency is the real game. #DSA #BinaryTree #Java #CodingJourney #LeetCode #SoftwareEngineering #Recursion #ConsistencyWins

Day 61 of My DSA Journey Today I solved the Subsets problem using the Backtracking technique. 🔹 Problem: Given an integer array nums, return all possible subsets (the power set). 🔹 Key Idea: Instead of trying to generate subsets directly, I used backtracking to explore every possible combination. 💡 Approach: Start with an empty subset. At each step, add the current subset to the result. Try including each element one by one. Recursively explore further subsets. Backtrack by removing the last element to explore other possibilities. 🔁 This approach systematically explores every possible subset using a decision tree. 📊 Time Complexity: O(n × 2ⁿ) — because each element can either be included or excluded. ✨ What I Learned: Backtracking is powerful for solving combinatorial problems. The pattern of choose → explore → unchoose is very important. 💻 Practicing problems like this helps strengthen recursion and problem-solving skills. #Day61 #DSA #Backtracking #Java #CodingJourney #LeetCode #ProblemSolving