Skip to content
DevGod Repo
Blog

Array

11 posts with the tag “Array”

Leetcode 55: Jump Game

DevGod
DevGod
Elf Vtuber

Question

In this Leetcode question, we are given an array of numbers. We start at the first index of the array, and our goal is to reach the end of the array. Each value of the array represents the maximum jump distance to the right. For example, if the first index’s value is 5, you could jump anywhere between 1 to 5 indexs ahead. If the index’s value is 0, then we are NOT allowed to jump anywhere beyond that spot, effectively trapping us. It is important to note that we are never given negative values in the given array. This means that leftward jumps are never allowed, given this constraint of the array Numbers.

Our goal is to determine if we can reach the end using any series of jumps. We return true or false depending on the reachability of the array’s end.

Solving

To solve this Leetcode problem, I used a greedy approach. I used a for loop to iterate left to right through the array. Whilst I traverse the array, the variable named maxJump records the furthest reachable index. In-between iterations, I check whether my current position is ‘impossible’ to reach. If an impossible index is detected, we return false and terminate early. If we go throughout the entire array, from left to right, without hitting an impossible to reach spot, we return true.

TLDR:

Used a Greedy approach to traverse the array, determining if the array’s end is reachable using any series of jumps. I solved this problem by iterating throughout the array, searching for impossible to reach spots.

Leetcode 121: Best Time to Buy and Sell Stock

DevGod
DevGod
Elf Vtuber

Question

For this Leetcode problem, we are given an array of numbers representing the fluctuating values of an imaginary stock. Each index of the given array represents a new day. Using this array, we must determine the maximum possible profit that can be achieved. The profit is determined by choosing ONE day to buy the stock, and one future day to sell the stock. In other words, a key constraint of this specific ‘buying stocks’ problem is the fact we are limited to only one sell and one buy operation.

Solving

To solve this problem, we can use Kadane’s algorithm as a template to find the maximum possible profit. This algorithm is used for many problems involving finding the max subarray sum. In our case, we can use it to find the highest profit peak for buying and selling the stock.

We use a for loop to keep track of our stock’s profits for each given day. To keep track of our current possible profit, each iteration we add the difference between the current Ith day’s value minus the previous day’s price. We use a Math.max(0,curProfit) to greedily ensure our current potential profit never dips below zero. Lastly, we use a variable maxProfit to keep track of the largest potential profit we have seen throughout the array.

TLDR:

I used Kadane’s algorithm as a template to create a maxProfit function, for finding the maximum possible profit achieved by buying and selling a stock.

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 26: Remove Duplicates from Sorted Array

DevGod
DevGod
Elf Vtuber

Question

In this Leetcode problem, we are given a pre-sorted, strictly increasing array of numbers and must remove adjacent duplicate values in-place. However, Leetcode includes a custom judge for this problem that verifies whether the array is modified in-place. For example, we do NOT want to initialize a new array to solve this problem, we want to solve this problem in-place using the original array. Another requirement of the custom judge for this question is to return K. The value K represents the amount of unique values we have after removing adjacent duplicates from the given array.

Solving

To solve this problem, I used a two pointer approach to modify the array in-place and keep track of unique values, K. I implement a for-loop that moves my right pointer R across the array. Every time nums[R] and nums[R+1] don’t equal each other, I have found a new unique value. Anytime my left pointer array element updates, I move the L one space. The right pointer, R and R+1 continue to move forwards until they reach the end of the given array.

In other words, my right pointer R is used in a sliding window style traversal to check all adjacent duplicate values in the array. Meanwhile, my left pointer L is strictly used to update positions in the left of the array, as I find unique values. Additionally, my left pointer L also keeps track of the amount of unique values that I have encountered in the given array. This is because every time I modify the position of left pointer L, it increments by one, which effectively keeps a running score of every time I updated the left section of the array.

Lastly, although the two-pointer solution does not remove the remaining “junk” values in the right section of the array, the custom judge only checks the first K elements for correctness.

TLDR

I used a two pointer approach to modify the given array in-place to hold the unique values in the left section of the array, satisfying the custom Leetcode judge requirements.

Leetcode 27: Remove Element

DevGod
DevGod
Elf Vtuber

Question

In this Leetcode problem, we are given an array named nums and a number named val. The number val represents the value we want to remove from the given nums array. For example, if we have an array nums = [1,2,3,4,5], and a val = 2, then we want nums to be [1,3,4,5] with the element 2 removed. Only the first K elements of the nums array is checked to ensure all elements equal to val have been removed.

K is used to represent the amount of elements from the beginning of the array that are checked by the Custom Leetcode Judge for this problem. This means values in nums beyond index k are ignored by the Leetcode Judge. Only the section of nums, 0 to K, need to be edited in-place by our algorithm solution.

The first K elements of nums are checked to ensure you removed the val from the starting prefix of the array. Secondly, the Leetcode Judge checks that your solution returned the amount of elements not equal to val. This means that we want to edit the nums array in-place, as well as return the amount of elements not equal to val.

Lastly, it is important to note that technically, you do not need to worry about the order of your nums array, just that the first K elements don’t include the value of val. This is because the custom judge actually sorts your nums array behind the scenes when evaluating your solution.

Solving

To solve this problem, I implemented a two pointer solution to edit elements of nums in-place, as well as keep track of the amount of elements not equal to val. I use an index variable named J to check indexs of nums, alongside the count of elements that aren’t equal to val. For each number of nums that is not equal to val, I edit the element at index J to that value, while also incrementing J to move to the next slot. Index J is used for editing specific elements of the nums array, as well as keeping track of how many elements I have found that are not equal to val. By the end, the nums array is successfully modified in-place. My solution finishes executing by returning the value of J, which represents the number of elements in nums not equal to val.

TLDR

I used a two pointer solution to edit in-place the values of nums to avoid including the value of val. At the end, I return the index J to represent the amount of elements I found from the array nums that don’t equal val. This solution satisfies the custom leetcode judge conditions of editing the nums array in-place and returning the amount of elements from nums not equal to val.

Leetcode 88: Merge Sorted Array

DevGod
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 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 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.

Leetcode 962: Maximum Width Ramp

DevGod
DevGod
Elf 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.