Counting

Leetcode 169: Majority Element

Jun 14, 2025

Shout out Solaris428 for help

Question

This Leetcode problem asks us to find the “Majority Element” from a given array of numbers. The majority element is the element of the array that appears > N/2 times. Basically, the majority element is the only absolute mode in this given array. Leetcode will only give you input arrays guaranteed to have one majority element. We must find and return the majority element to solve this problem.

Follow up

We must solve this question using linear O(n) time complexity and O(1) constant space complexity. In other words, any solutions that use sorting algorithms would break this follow up’s time complexity rule. This is because sorting algorithms, Wether implemented or using language’s built in sorting methods, will result in at best nlogn time complexity. Secondly, we can not use data structures such as frequency Arrays or Hash tables, as these would be n space complexity at best.

Solving

Since there is only at most one majority element present in our given array, we can use a running frequency of elements. This is because the majority element appears more often then all other values of the array. In other words, if we were to take the frequency of the majority element, subtracted by the sum of all the other frequencies of the non majority elements, the total would be more than zero. This only occurs for the majority element, as that is going to be the only element in the array that appears more often then all of the other elements.

We start by initializing a score variable used for tracking the current frequency, as well as the current “potential answer” we are investigating. We use a for loop to iterate through all of the numbers of the given array. If the num of the for loop is equal to the potential answer we are currently investigating, then we increment the current frequency score, else we decrease the score. If our frequency score ever reaches zero, then we change our current ans we are investigating to the current num of the for loop. This is because if our frequency is zero, at that point in time our current potential answer is <= the frequency of other values.

In other words, whenever our currently investigated potential ans running frequency is equal to zero, we must start investigating a new value at that time. Continuing with this pattern of investigating potential majority elements as they become suspects, and then once they get cleared we investigate the next value.

Lastly, once we have reached the end of our for loop, then our answer that is left should be the majority element we are looking for, so we return the ans. This solution fits our follow up, as we use constant space, and we use liner time complexity.

TLDR:

We use an approach similar to a running prefix sum, where we keep track of the majority element by returning the element who’s frequency at the end of array traversal is greater then zero.

Leetcode 2275: Largest Combination With Bitwise AND Greater Than Zero

Nov 5, 2024

DevGod

Elf Vtuber

About

This problem focuses on finding combinations of numbers from the given array such that the bitwise & AND of all numbers are greater than or equal to 1. Out of all combinations of elements, we return the size of the largest possible combination length.

For example, [1,2,3,4,5] = 3, since the greatest combination length possible would be 1,3,5. This is because 1&3&5 is equal to 1.

Thoughts

An important thing to note about using the bitwise AND & operator is that between two numbers, only the ON (1) bits locations can stay one when performing the AND & bitwise operation. For example, 1 AND 2 would equal zero since they do not share any ON (1) bit locations, but 1 AND 3 would equal 1 since both 1 and 3 have the 1 bit turned on.

1 = 01, 2 = 10, 01 & 10 = 00
1 = 01, 3 = 11, 01 & 11 = 01

With this property noted, we can say that for a combination of numbers bitwise AND together have to share ON (1) bit locations among all of them to be greater than zero. In other words, as soon as we reach a number with a bit location that is off, said bit location in the ending result is also turned off.

Seeing this, I decided an optimal way to organize these array elements into valid combinations would be using a hashmap data structure. A hashmap can assign elements into groups based on what bit locations they have flipped on. All elements in a group are in common, as they would all share a specific ON (1) bit location.

Implementation

To solve this problem, I used the built-in Javascript Map() object to record the frequencies of elements in the array that share a specific bit location. To update both myMap and the answer variable, I created a function named “nya” on each candidate in the candidates’ array. The function nya can check each ON(1) bit location a candidate has and update the frequency of that bitmask location if it is on. Lastly, nya can update my ans variable with the maximal length of a valid combination.

For example, for test case [1,2,3,4,5], these are all my valid combinations. To save on memory space, I can update the frequency at a given bit location key instead of maintaining an array of elements at that key. In other words, sorting into buckets, but instead, I keep track of the buckets’ lengths.

[1,3,5] = 3
[2,3] = 2
[4,5] = 2

ans = 3

Closing Thoughts

This is a pretty fun bitwise & hashmap combo problem. While coding this solution, I almost did not go with a frequency map, but instead went with keeping track of all elements in an array inside of the hashmap. Switching to keeping track of the frequency of all elements that shared an ON bit location instead of all the elements in that combo saved my bacon for sure time complexity and memory space-wise.