Skip to content
DevGod Repo
Blog

Hash_Table

7 posts with the tag “Hash_Table”

Leetcode 169: Majority Element

DevGod
DevGod
Elf Vtuber

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 1: Two Sum

DevGod
DevGod
Elf Vtuber

About

Two Sum is the first ever Leetcode problem published. In this problem, we are given an array of numbers, and a target integer. We must find two points in the given array who’s values added together are equal to the given target value. At the end, we return the indexes of where these two points exist in the given array.

To solve this problem, we can use a data structure known as a Hash Table. Basically, Hash Tables are used for optimally searching, setting, and getting key value pairs. In this problem, using a Hash Table is important for storing past results that we can use later in our for loop. By sacrificing this extra little bit of memory, we can write an O(N) time complexity solution for the problem.

Specifically, we want to find the difference between the target and the current value we’re evaluating in the given array. This difference value is a number we need to find in the future to form a pair that equals the given target. Our Hash Table’s keys will be set to this difference, while our values will be set to our current index for use later. For example, if our first element in the array is 1, and our target is 5, then we would store {4:1}.

We continue scanning through the given array, whilst recording our difference key and our index values along the way. If we ever come across a value in the given array that happens to equal a key stored inside of our hash table, we then know we have found a matching pair that equals target. We can then return the current index we are checking, alongside our previous index already stored inside of our Hash Table. Back to our above example, if we have {4:1} in our Hash Table, and we found a 4 further in the array, we can return our current index along with the past index we’ve stored in the Hash Table.

TLDR:

Using a Hash Table to store the needed future value along with the past Index. Then if we hit the required future value further in the array, we can return our past Index, along with the current index.

Leetcode 3375: Minimum Operations to Make Array Values Equal to K

DevGod
DevGod
Elf Vtuber

For today’s LeetCode problem, I honestly had to reread the prompt several times to really grasp what it was asking. It’s an easy problem conceptually, but the wording makes it a bit tricky to follow at first.

The main idea is this: we’re given an array and we’re allowed to perform a specific operation multiple times. We can choose a number from the array — but only if there’s exactly one unique number in the array that’s greater than it. For example, in the array [1, 2, 2, 2, 2, 2], the number 1 is valid because the only number greater than it is 2. But in [1, 2, 3], the number 1 is not valid because both 2 and 3 are greater than it — meaning there’s more than one unique number greater than 1.

Once we’ve identified valid numbers, we can use them to perform the operation: turning all instances of a greater number into that number itself. So in [1, 2, 2, 2, 2], we can transform all the 2s into 1s in a single operation — because we’re allowed to perform this operation any number of times, but it can only decrease values, never increase them.

A key detail is that we can only convert numbers downward. So if we’re given a target value K, we must ensure it’s possible to reduce all the values in the array to K using this method. If K is greater than any number in the array, it’s impossible — since we can’t increase values. For example, if K = 3 and the array is [1, 2, 2, 2, 2], we can’t reach 3 because we can’t increase any of the values.

Our goal is to return the minimum number of operations required to make every value in the array equal to K. To solve this, I used a Set in JavaScript to track all the unique values greater than K since each unique value greater than K will need its own operation to be reduced to K. If at any point we encounter a value less than K, we know the task is impossible and should return -1.

TLDR

Count how many unique values in the array are greater than K — that’s the minimum number of operations needed. If the array contains any value less than K, it’s impossible to solve, so return -1.

Leetcode 763: Partition Labels

DevGod
DevGod
Elf Vtuber

For today’s daily leetcode problem, we are given a string and need to split it into as many partitions as possible, ensuring that each letter appears in at most one partition. Additionally, the partitions must preserve the order of letters as they appear in the original string. However, we don’t need to store the actual substrings—our task is simply to return the lengths of these partitions.

Example Walkthrough Consider the string “pizzatime”. The optimal partitions would be [1,6,1,1]. Here’s why:

  • The letters p, m, and e each form their own single-letter partitions since they don’t share any letter with another partition.

  • The substring “izzati” forms a partition because it contains multiple occurrences of i and z, and we need to ensure that all instances of a letter belong to a single partition.

  • Since the letters must remain in order and cannot belong to multiple partitions, “zzati” is grouped together with i to form a partition of length 6.

Another example is “partitionlabels”, which results in [1,13,1]:

  • The letters p and s form their own separate partitions.

  • The middle partition, “artitionlabel”, must include all occurrences of a and l.

  • Since l appears late in the string, we must extend the partition to ensure all ls are included, resulting in a large middle partition.

Implementation Approach Since I was in a hurry and the constraints were small, I used JavaScript’s built-in .lastIndexOf() method to determine the last occurrence of each letter in real time. The key insight is that a letter’s last occurrence dictates where a partition must end. While this approach runs in 𝑂(n^2) time due to repeated .lastIndexOf() calls, an optimized solution could use a hashmap for 𝑂(1) lookups.

To efficiently track when to end a partition, I maintain a max variable, representing the farthest last occurrence seen so far. As I iterate through the string, I update max using:

max = Math.max(max, s.lastIndexOf(s[L]));

This ensures that if a previous letter has a later last occurrence, we extend the current partition accordingly. This is crucial for cases like “partitionlabels”, where encountering l extends the partition beyond a’s last occurrence.

I iterate through the string using a loop and keep track of partitionSize. Whenever I reach max, I add partitionSize to the result array, reset it, and continue. Instead of constructing substrings, I only track partition lengths, as that’s all the problem requires.

This greedy approach ensures an optimal partitioning of the string while keeping the implementation simple and efficient.

Leetcode 2780: Minimum Index of a Valids Split

DevGod
DevGod
Vtuber

I started today’s daily LeetCode problem by using LeetCode’s provided Lodash _.countBy function to quickly create a frequency map of all elements in the array. Since the dominant element is the one that appears more than half the time, it must have the highest frequency among all elements. The dominant element is the one with the highest frequency in the array, while my suffix sum will represent the total count of the dominant element within the given array. The problem also guarantees that the input will always contain a dominant element before any array splits occur.

Once I identified the dominant element, I used its frequency to compute a suffix sum of the array. To determine the earliest possible valid split, I maintained both a suffix sum tracking the remaining occurrences of the dominant element and a prefix sum counting the ones I had already seen. Iterating from left to right, I subtracted elements from the suffix sum while adding them to the prefix sum. Using the index i and the array length, I determined the sizes of both the left and right partitions.

Essentially, I maintained a prefix sum (counting occurrences in the left partition), the left partition’s size, a suffix sum (tracking the remaining dominant elements in the right partition), and the right partition’s size. With these variables, I could efficiently check whether a valid split was possible at a given index. This approach is more optimal than a brute-force solution since I never actually split the array; instead, I keep it intact while using only four variables to determine whether a given index is a valid split point. For example, initially, the suffix sum contains all instances of the dominant element. If i moves to the first element and that element is the dominant one, I increase the prefix sum while simultaneously decreasing the suffix sum.

Finally, since it is possible for the array to have no valid split, we need to return -1 if no valid location is found. To handle this, I simply iterate through the array, returning early if I find a valid split point. Otherwise, if no valid index is found, I return -1 at the end.

Leetcode 2516: Take K of Each Character From Left and Right

DevGod
DevGod
Elf Vtuber

About

This leetcode problem asks use to find the minimal number of operations needed to get AT LEAST k amounts of a, b and c characters. For each operation, you are able to either remove a letter from the beginning or end of the given string.

Example

“aabaaaacaabc” k=2

The minimal number of operations needed would be 8. From the left of the given string we can remove letters “aab”. From the right of the given string we can remove letters “caabc”. With these 8 removal operations, we can get 4 a’s, 2 b’s and 2 c’s, which meet our “AT LEAST” k of each letter requirement.

Thoughts

At first, I was thinking it was some kind of greedy deque problem. At first glances, It felt like the problem was asking to choose optimally between either the left side vs the right side of the char array.

However, I then realized that it sounded more like finding an optimal prefix and suffix of the string such that you had all the letter you needed. Seeing I was finding a string prefix and suffix, I knew that I would need some kind of Two Pointer approach for this problem.

After getting a little frustrated, I peaked at the topic tags and saw “Sliding Window”. Then it clicked, a lot of Leetcode sliding window problems are phrased like, for this continuous sub array in your array of data, find X criteria or frequencies. This problem sounded similar, but the main difference was we are concerned about what is on the outside of the sliding window, versus what’s on the inside of the sliding window.

Implementation

In Javascript, I first find the frequencies of a,b and c present in my given string. If the amount of letters in the whole string are less than K for any of the letters, I then just return a -1. If the amount of letters in the whole string are greater than K, a while loop is used to start building my sliding window.

During each iteration, sliding window’s R pointer slides to the right, and for each letter it comes across it subtracts from my frequency map of letters. If at any point a letter’s frequency becomes less than K, I start moving the left pointer to the right. For each letter my left pointer hits, I increase the frequency of that letter in the frequency map.

This ensures that my sliding window never takes more letters than it can from the string prefix or suffix. In other words, this makes sure that my sliding window is the largest window of characters that can take up the space between the smallest need prefix and suffix of the string.

Lastly, for each iteration we keep track of the maxRange of our sliding window. We then return the given string length - maximum range of the sliding window. We return this because the minimal of letter removal operations is equal the amount of character not present inside our sliding window. The answer therefor is basically the smallest possible string prefix and string suffix.

TLDR

  1. Find the minimal number of letters from beginning or end of string to remove for “at least” K letters.

  2. At first thought it was a greedy problem, but it’s actually a slightly unusual sliding window / two pointers problem.

  3. Use Sliding window to find the largest range between the smallest needed prefix and suffix of string.

  4. The sliding window is valid if your remaining letter frequencies do not go below K elements.

Closing Thoughts

This is a very interesting sliding window problem. Instead of following the usual pattern of focusing on the internal state of the Sliding window element frequencies, it focuses on how your sliding window impacts the external state of you total frequencies of each letter in the given string.

Leetcode 2275: Largest Combination With Bitwise AND Greater Than Zero

DevGod
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. 1 = 01, 2 = 10, 01 & 10 = 00
  2. 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. [1,3,5] = 3
  2. [2,3] = 2
  3. [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.