Sorting

5 posts with the tag “Sorting”

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 88: Merge Sorted Array

May 14, 2025

DevGod

Elf Vtuber

Question

In this Leetcode Problem, we are given two already sorted arrays, as well as their expected sizes in the m and n variables. The Nums1 array is also filled with zeros at the end to ensure the Nums2 array can fit inside of Nums1.

Our task is to merge both of these presorted arrays together Inplace inside of Nums1, while maintaining a sorted ordering. Inplace is different from most Leetcode problems, as we are only required to edit the given nums1 array. Instead of checking a specific function return value, the Leetcode Judge instead checks what we have done with the given nums1.

Additional, the Follow Up challenge specifies we want to solve this problem in O(m+n) time. The easy (m+n) log(n) solution would be to concatenate the given arrays together, then sort them using a built-in sort function. However, because most built-in sorting methods are log(n) time complexity, this would break our follow up challenge. Instead, we can use a more optimal two pointer approach.

Solving

To solve this problem, we use an I variable to iterate from right to left on the nums1 array. We then use two pointers named a,b as a way to check values from the two given arrays. The pointer a is used to look up values in nums1, and the pointer b is used for numbers in nums2. So where the I variable is just for iterating through nums1, a and b are actually used for performing our comparisons.

If nums1[a] is greater then nums2[b], then we can keep that value at nums1 the same. Note that we only check this if our a pointer is still at a valid slot in nums1. Otherwise, we can safely assume that the current I th position in nums1 needs to be replaced with nums2[b]. Since nums2 is guaranteed to be the smaller length of the two given arrays, we can exit out of our while loop.

Instead of returning an array, we can just let the code end at the while loop, as the Leetcode Judge is only concerned with what nums1 is equal to.

TLDR:

We must merge two given sorted arrays together inplace. To solve the follow up challenge of O(m+n) time complexity, we can easily do this using a two pointer solutions instead of relying on built in sorting methods.

Leetcode 2780: Minimum Index of a Valids Split

Mar 25, 2025

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

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 3011: Find if Array Can Be Sorted

Nov 4, 2024

DevGod

Elf Vtuber

About

There are two main parts to this problem. First, we need to be able to preform a sort on the array of values. Second, we must evaluate whether two elements in the array need to be swapped, and whether they are swappable given their count of on (1) in their binary representation of themselves. If the given array is already sorted, we can return true. If the given array is unsorted, then we must return whether it can become sorted by swapping elements when their bit counts are equal to each other. Returning false means that we have reached a point where the array is unsorted, and elements are different bit counts from each other, meaning it’s impossible to complete the swap operation.

For example:

[1,5,2] = false, 5 and 2 can’t be swapped, even though they need to be swapped
[1,2,3,4,5] = true, sure some numbers can’t be swapped, but since its already sorted we don’t need to worry

Thoughts

Since this is a bitwise problem, a while loop can find the number of on (1) bits a number has. Also, an ideal sorting algorithm to use would be bubble sort, since the problem specifies you are preforming swaps between elements. Since the main idea is to test for bit counts and whether elements in the array are less than each other, bubble sort is the first thing that popped into my head. With bubble sort, I could check how elements values differ from each other, as well as how their bit counts differ from each other.

Implementation

For my solution I went with a bubble sort approach, since bubble sort is well known for being a sort algorithm that preforms a bunch of swaps between a left and right pointer. By using a bubble sort to implement a solution, I could also include a check during swaps to check if the two elements I’m swapping at the time are different bit counts. If at any point they are different bit counts and need to be swapped, I can simply exit early and return false. Otherwise, I continue on with my business until the array is fully sorted and return true.

For finding the bit count of on (1) bits of a number, I simply use a while loop that counts the & of each first bit. Then to iterate down, I just do an arithmetic shift right, >> 1, to effectively half and floor the number each iteration until the number I am checking reaches zero.

Closing Thoughts

After rereading the question, I noticed that leetcode did specify that only two ADJACENT elements can be swapped in one operation. While my solution passes all test cases, my solution does technically break the only ADJACENT elements rule. https://www.geeksforgeeks.org/bubble-sort-algorithms-by-using-javascript/ The bubble sort algorithm template on geeksforgeeks actually follows this rule a bit better, but at the end of the day still gets the job done :p