Algorithms to Identify Majority Candidates in Arrays

You might not know this randomized probabilistic method to find the Majority element! The majority element of a sequence is an element that appears more than half the number of times in that sequence. Many interesting competitive programming problems are based on this property. Most of you might already be familiar with the Boyer-Moore Majority Voting Algorithm, which finds the majority element in an array in O(n) time. Boyer-Moore Algorithm Steps: Initialize an element m and a counter c with c = 0. For each element x in the input sequence: If c == 0, assign m = x and c = 1. Else if m == x, increment c by 1. Else decrement c by 1. Return m. In the second pass, we can iterate over the array to validate if freq(m) > n/2. However, in competitive programming problems, you may not be required to find the majority element of the entire array but of multiple subarrays of an array. Using the above algorithm for each query would make your solution quadratic in time, i.e., O(n²) or O(n × q), which is inefficient. So, how can we optimize this? Let’s consider a different and interesting approach: Assumption: There exists a majority element in the array, say x. This means x appears more than n/2 times in the array. Key Observation (Probability): If we pick a random element from the array, the probability that it's not x is at most 1/2. Now, if we repeat this process twice, the probability that x is not picked either time becomes: (1/2) × (1/2) = 1/4 If we repeat this k times, the probability of not picking x at all becomes: (1/2)^k For k = 30, this probability becomes extremely small. So, with high probability, at least one of those 30 random picks will be x. Efficient Algorithm: Pick 30 random elements from the array. For each picked element, count its frequency in the current subarray. If its frequency > n / 2, then it's the majority element of that subarray. If none of the picked elements satisfy this condition, then you can confidently say there is no majority element in that array. Frequency Optimization: The only heavy operation left is counting the frequency of a candidate element in a subarray. This can be optimized using: A 2D prefix frequency array, if max(a[i]) × n is manageable. A 2d array of positions for each unique value, and using binary search to count occurrences in a range (more scalable for larger values). This makes the frequency counting operation O(1) or O(log n) per candidate check. Final Time Complexity: Since you do at most 30 random picks per query, and frequency checking is fast, the final complexity becomes: O(30 × q) or O(30 × log(n) × q) Which is efficient enough to pass time limits. Extra Tip: Instead of using rand() for random picks (which can be weak and predictable), it’s better to use C++'s mt19937 random number generator (often called rng) for better randomness and performance. Practice Problem: Try this problem to apply this technique: 👉 Codeforces 1514D - https://lnkd.in/dNf-W8W2

🚀 Contest Winning Strategies 101 - From Moore’s Voting to Majority-in-Range Queries 🚀 Most FAANG interviews will test you on the classic Majority Element problem—find the element that appears > n/2 times in a static array. Moore’s Voting Algorithm nails it in O(n) time and O(1) space: 1. Candidate selection (one pass) 2. Verification (second pass) Every standard sheet in the market handles that - so let me ask you the next question "What’s the majority in A[L…R]?”—and you have up to 10⁵ queries on an array of size 10⁵? A brute force ≃ O(n) per query is a non-starter. Here’s how to level up: ⚙️ 1. Store a “voting‐pair” per segment Build a Segment Tree where each node over a subarray [l..r] keeps: cand = the Moore candidate for that subarray cnt = its “net vote” (votes for minus votes against) Merging two children is just another round of voting: if left.cand == right.cand: merged.cand = left.cand merged.cnt = left.cnt + right.cnt else if left.cnt > right.cnt: merged.cand = left.cand merged.cnt = left.cnt - right.cnt else: merged.cand = right.cand merged.cnt = right.cnt - left.cnt That gives you O(log N) per query to retrieve a single candidate for [L..R]. 🔍 2. Verify with prefix‐lists Moore’s trick only selects a candidate; you still need to confirm it really occurs > ⌊(R–L+1)/2⌋ times. Precompute pos[val] = sorted list of all indices where A[i]==val. Then in O(log N) you can count occurrences in [L..R] by two binary searches. 📈 3. Complexity Build: O(N log N) (segment tree + map positions) Each query: O(log N) to get cand + O(log N) to verify → O(log N) total This scales to 10⁵ queries in under a second, turning a one-pass offline trick into a real-time range service. 💡 Key takeaway: Many “linear-time” interview algorithms can be lifted to range-query or dynamic settings by augmenting data structures (segment trees, BITs, etc.) with just a bit of extra info. Taking the understanding of standard problems to the next level, is how you level your DSA game up. Stay tuned for more such content!! ✌🏻🚀

🚀 Asked in Accenture | Majority Element Problem In one of the Accenture interviews, I was asked a simple looking question: 👉 “Given an array, find the element that appears more than n/2 times.” At first glance, it feels like a counting problem. My first instinct was to use a HashMap and track frequencies. But then came the follow-up: “Can you solve it in O(n) time and O(1) space?” That’s when the real interview started. Instead of storing counts, the key idea was elimination. 💡 If an element appears more than n/2 times, it can never be completely canceled out by other elements. Using the Boyer–Moore Voting Algorithm: Maintain a candidate Increase count when the same number appears Decrease count when a different number appears Reset candidate when count becomes zero In the end, the surviving candidate is the majority element. No extra space. Single pass. Clean logic. Sometimes interviews are not about writing more code - they’re about thinking smarter. Keep practicing patterns. The difference between average and strong solutions often lies in understanding these classic optimizations. https://lnkd.in/gC6QGR8V #Accenture #DSA #CodingInterview #Java #InterviewPreparation #Algorithms #ProblemSolving #SoftwareEngineer

#𝟭𝟬𝟬𝗗𝗮𝘆𝘀𝗢𝗳𝗟𝗲𝗲𝘁𝗖𝗼𝗱𝗲 - 𝗤𝘂𝗲𝘀𝘁𝗶𝗼𝗻 𝟮: 𝗠𝗮𝗷𝗼𝗿𝗶𝘁𝘆 𝗲𝗹𝗲𝗺𝗲𝗻𝘁 𝗣𝗿𝗼𝗯𝗹𝗲𝗺: Given an array nums of size n, return the majority element. The majority element is the element that appears more than [n / 2] times. You may assume that the majority element always exists in the array. 𝗘𝘅𝗮𝗺𝗽𝗹𝗲: nums = [3,4,4,5,4,9,4,4,1]. The majority element is 4 (there are 9 elements, and '4' occurs 5 times (> n / 2). 𝗔𝗽𝗽𝗿𝗼𝗮𝗰𝗵 𝟭: 𝗕𝗿𝘂𝘁𝗲 𝗙𝗼𝗿𝗰𝗲  For each element, traverse the array to find its frequency and check if it appears more than n/2 times. 𝚃̲𝚒̲𝚖̲𝚎̲ 𝚌̲𝚘̲𝚖̲𝚙̲𝚕̲𝚎̲𝚡̲𝚒̲𝚝̲𝚢̲: O(n^2) (nested loops) 𝚂̲𝚙̲𝚊̲𝚌̲𝚎̲ 𝚌̲𝚘̲𝚖̲𝚙̲𝚕̲𝚎̲𝚡̲𝚒̲𝚝̲𝚢̲: O(1) 𝗔𝗽𝗽𝗿𝗼𝗮𝗰𝗵 𝟮: 𝗛𝗮𝘀𝗵𝗺𝗮𝗽 𝘁𝗼 𝘀𝘁𝗼𝗿𝗲 𝗳𝗿𝗲𝗾𝘂𝗲𝗻𝗰𝗶𝗲𝘀 We can optimize the brute force approach by using a hashmap to count the frequencies in linear time. The majority element is the element with the highest value in the hashmap. 𝚃̲𝚒̲𝚖̲𝚎̲ 𝚌̲𝚘̲𝚖̲𝚙̲𝚕̲𝚎̲𝚡̲𝚒̲𝚝̲𝚢̲: O(n) (single parse of the array) 𝚂̲𝚙̲𝚊̲𝚌̲𝚎̲ 𝚌̲𝚘̲𝚖̲𝚙̲𝚕̲𝚎̲𝚡̲𝚒̲𝚝̲𝚢̲: O(n) (for the hash map) 𝗔𝗽𝗽𝗿𝗼𝗮𝗰𝗵 𝟯: 𝗦𝗼𝗿𝘁𝗶𝗻𝗴 Upon sorting the array, the middle index will always hold the majority element (as more than half of the values in the array are the majority element). Remember to only use this method if the question allows you to modify the array.  𝚃̲𝚒̲𝚖̲𝚎̲ 𝚌̲𝚘̲𝚖̲𝚙̲𝚕̲𝚎̲𝚡̲𝚒̲𝚝̲𝚢̲: O(n log n) (for sorting) 𝚂̲𝚙̲𝚊̲𝚌̲𝚎̲ 𝚌̲𝚘̲𝚖̲𝚙̲𝚕̲𝚎̲𝚡̲𝚒̲𝚝̲𝚢̲: O(1) 𝗔𝗽𝗽𝗿𝗼𝗮𝗰𝗵 𝟰: 𝗕𝗼𝘆𝗲𝗿-𝗠𝗼𝗼𝗿𝗲 𝘃𝗼𝘁𝗶𝗻𝗴 𝗮𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺 This is the most optimal solution for this question, albeit a tough concept to grasp for the first time. Let's try to understand it this way:    • Maintain a 'count' variable.    • Start by assuming the first value to be the majority element.    • Every time we see the same number, we vote for it (increment count).    • Every time we see a different number, we cancel the vote (decrement count).    • If the count reaches zero, we pick a new candidate.    • Since the majority element appears more than n/2 times, it will always remain at the end. 𝚃̲𝚒̲𝚖̲𝚎̲ 𝚌̲𝚘̲𝚖̲𝚙̲𝚕̲𝚎̲𝚡̲𝚒̲𝚝̲𝚢̲: O(n) (single parse of the array) 𝚂̲𝚙̲𝚊̲𝚌̲𝚎̲ 𝚌̲𝚘̲𝚖̲𝚙̲𝚕̲𝚎̲𝚡̲𝚒̲𝚝̲𝚢̲: O(1) (constant space) Try it out: https://lnkd.in/dZ7p3Mxa Follow for more! - Sheel Sanghvi #LeetCode #ProblemSolving #CodingChallenge #TechLeadership #SoftwareEngineering #100DaysOfCode #Hiring #TechCommunity #MajorityElement #InterviewPrep

#Day 10 DSA Milestone: Optimal Solution for Majority Element #LeetCode 169 Excited to share a significant milestone on Day 10 of my focused DSA training! I successfully implemented the Moore Voting Algorithm to solve the Majority Element problem (LeetCode 169). This approach is considered the gold standard for this problem because it achieves the absolute best performance metrics. ✨ The Code: Boyer-Moore Voting Algorithm This algorithm efficiently finds the element that appears more than n/2 times in an array of size n, using a brilliant strategy of vote cancellation. Java class Solution { public int majorityElement(int[] nums) { int n = nums.length;//find length of array int count = 0; int el = 0; // The candidate for the majority element for(int i=0;i<n;i++){ if(count == 0){ // New election: set the current element as the candidate count = 1; el = nums[i]; } else if(nums[i] == el){ // The current element matches the candidate, increment vote count++; } else{ // The current element is different, cancel one vote count--; } } return el; } } 📊 Performance Analysis This solution demonstrates professional-level efficiency, which is crucial for real-world software engineering: Time Complexity: O(N) (Linear Time) We make a single, fast pass through the array. Space Complexity: O(1)(Constant Space) We only use a few fixed variables (count, el), regardless of the input size N. This technique is a perfect example of how a clever algorithm can dramatically reduce resource usage! 🔑 Key Takeaway The Boyer-Moore Voting Algorithm works because the majority element's abundance ensures that its vote count will never drop to zero permanently. Even after being paired and cancelled by every other element, it will always be the last candidate standing. A mandatory pattern for mastering DSA! #DSA #LeetCode #CodingChallenge #BoyerMooreVoting #Java #O1Space #Algorithms #SoftwareDevelopment