Skip to content
DevGod Repo
Blog

Blog

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 3169: Count Days Without Meetings

DevGod
DevGod
Vtuber

For today’s daily problem, I created a line sweep-themed solution using LeetCode’s provided JavaScript Min Priority Queue, also known as a Min Heap, data structure. Meetings are given in an array in the form [start time, end time], making this problem a perfect fit for the line sweep technique.

I used a for loop to store both the start and end times of meeting ranges. A brute-force approach would be to iterate over each day, counting whether or not a meeting is taking place at that point. However, since days can range from 0 to 1,000,000, this would be highly inefficient. Instead, by storing only the exact days when meetings start and end, we can efficiently determine the number of meeting-free days.

Our MinPriorityQueue PQ data structure will store pairs of two numbers.

  • The first number represents the day on which a meeting either starts or ends.

  • The second number represents the event type:

    • 1 indicates the start of a meeting range.

    • -1 indicates the end of a meeting range.

The priority queue automatically sorts these pairs by day number, in increasing order, ensuring that earlier events are processed first. For example, the pair [20, 1] (a meeting starting on day 20) will appear before [100, 1] (a meeting starting on day 100).

Sorting by day number allows us to process events in chronological order, creating a structured timeline of meeting activity for us to sweep through—hence the name line sweep.

Once we have these meeting times stored in a MinPriorityQueue (also known as a min heap), we can begin popping the sorted meeting times and calculating the meeting-free days until our data structure is empty. The key observation is to determine the first day of a meeting-free period and the last day of that period. We can track this by maintaining a prefix sum of active meetings.

  • If our prefix sum reaches zero, it means the worker has entered a meeting-free period.

  • If the prefix sum is already zero, it means the worker is currently in a meeting-free period but is about to leave it due to an assigned meeting.

The total number of meeting-free days for a given period is calculated as:

score += currDay - lastLuckyDay

I considered lucky days as the critical points where the prefix sum of currently assigned meetings transitions from zero to one or from one to zero. These points mark the start and end of meeting-free periods for the worker. So by keeping track of the ‘lastLuckyDay’ / the previous start of the meeting free period, we can subtract from our current day number to add the number of meeting free days to our score varible.

A few other details to consider:

  1. Meeting Ranges are Inclusive – If we are given the range [1, 3], this means days 1, 2, and 3 all have scheduled meetings.

  2. Days Beyond the Last Meeting – The worker may have more total workdays than the last scheduled meeting. For example, if meetings only occur on days 1, 2, and 3, but the worker is assigned 10 days of work, we must also count the meeting-free days 4 through 10.

To account for this final case, we perform one last update before we can return the answer:

score += (total workdays - lastLuckyDay);

This approach allows us to efficiently determine the total number of meeting-free days while keeping our solution optimal.

The k-th Lexicographical String of All Happy Strings of Length n

DevGod
DevGod
Elf Vtuber

Another backtracking problem where you are given some letter options to choice from to arrange permutations to explore. This one is a bit different cause you are tasked with finding all permutations containing just ‘a’, ‘b’ or ‘c’ letters, with no duplicates. For example a happy permutation is “abc”, and a non happy one would be ‘aab’.

You are given N for the amount of letters that should be in your generated sequence, and K for finding the Kth seqence if you were to sort all the seqences you found in a list. I like how leetcode’s hints tonight casually tried to get you to use more memory then you would need to.

Instead of generating an array of all my possible seqences, I just greedily backtrack using the already lexigraphically sorted string “abc”. I then just use a score varible to keep track of which Kth seqence I am currently at. If I have reached the Kth seqence, I just return out of my backtrack function and then return the answer.

Lastly, I know for sure there has to be some really cool math combinatrics trick for this problem, but I just couldn’t think of it, EI the backtracking for it just being seqences of 10 letters or less worked pretty well, but im sure if it were harder constraints I would be forced to somehow optimally use math to spit out a seqence.

Leetcode 1352: Product of the Last K Numbers

DevGod
DevGod
Elf Vtuber

Cool so looks like we get another System Design problem today. As usual, Leetcode just casually gives us the defualt JS prototyping functions together like a madlad template. This time we accepting numbers in a sort of data stream in one method. The other method being for taking the previous K values recieved, and returning the product of all of them multiplied together.

At first I didnt even care about the follow up, I just wanted to do it fast and pass it so I didnt have to worry about ruining my daily streak. So I just did an array push for my add() method, and then for my getProduct() method I just took a slice of my array at the ending depending on the k size given and then reduced using multiplacation to return the answer. This worked out good, but was pretty gross with a 1000ms being used. Definately not the O(1) goal that follow up sets us up for.

After that, and after some messing around with the testcase that a zero happens, I ended up instead keeping an array of multiplied prefix sums of my values, and a current prefix sum varible to just quickly take the current prefix sum value dividied by the past prefix sum value based on K offset to quickly get the answer.

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.