Array

3 posts with the tag “Array”

Leetcode 2780: Minimum Index of a Valids Split

Mar 25, 2025

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

Mar 22, 2025

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:

Meeting Ranges are Inclusive – If we are given the range [1, 3], this means days 1, 2, and 3 all have scheduled meetings.
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.

Leetcode 962: Maximum Width Ramp

Oct 17, 2024

DevGod

Vtuber

About

So this problem is basically asking about finding the longest distance between two indexs of an array such that the left index is lower then the right index, and that the value at the left index is smaller then the value at the right index.

Another way to look at this problem is to pick two indexs, I and J, such that the index I appears before index J, as well as the number at nums index of I being smaller then the value at nums index of J.

In other words, Number I must appear before J in the array, and number I must be smaller than number J in the array.

For example [(1),2,3,4,(5)] = Minimal distance between elements 5 and 1 is 4 [(1),0,2,(3)] = Minimal distance between elements 1 and 3 is 3 [6,3,(2),1,5,(3)] = Minimal distance between the last 3 and the middle 2 is 4

Thoughts

I immediately misread the questions and assumed it was talking about finding the largest increasing monotonic stack by traversing left to right in the test case array. However, even after realizing this wasn’t the case, I was still determined to use a monotomic stack for this problem.

Rethinking about the problem, I realized that for each right most index, the distance value that would be returned was the distance between itself and the leftmost index of any element that is smaller then the right most index’s value. For example, for a testcase like [200,5,4,3,2,1,100] at the index for element 100, you would consider only 5,4,3,2,1 since those are values that are smaller then 100. the 200 can then be ingnored.

Also I realized that the way to get a maximal distance would be using classic monostack popping until you reach a point where you can no longer pop. For example, with testcase [200,5,4,3,2,1,100], you could have a monostack like [200,5,4,3,2,1], and then pop elements 5,4,3,2,1 you are left with 200.

For testcases like [10,1,2,3,11], your monostack that you start with initally should just elements such that each element is less then its prevous elements. For example, you would only need to have [10,1] to evaluate from the 11 element. This is due to being 2 and 3 being larger then 1, but also appearing after 1 in the array. Since 1 is already smaller then the next elements, 2 and 3, and can greedily say that 2 and 3 are not good choices, since 1 is already smaller then thoose two values.

Lastly, with a problem like this I am sure that while my monoStack is going to use the values of the array for comparisons, I am storing indexs inside of the monoStack itself. This way, I am able to do a distance calculation between two different points in the array if certian conditions are meet.

Implementation

First, I use a for loop to form a decreasing monoStack in Javascript like I usually do. However, I dont preform any popping operations, only pushs when I find numbers that are smaller then the previous number on the top of the stack.

I then a second for loop, this time moving from right to left, to remove elements from my monoStack if they are smaller or equal to my current number. I also update my max varible with the max possible distance between the index. This is simply done my taking my current Rightmost index on my, and then subtracting the index on the top of the stack, which represents the rightmost index of the next element in the array that is smaller than my rightmost index’s value.

Finally, I just return max which after the second for loop runs, contains my maximal distance / maximal ramp width to leetcode.