Skip to content
DevGod Repo
Blog

Blog

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 191: Number of 1 Bits

DevGod
DevGod
Elf Vtuber

Question

In this leetcode problem, we are given a 32 bit integer which we must find the hamming weight of. The hamming weight is the amount of ones present in the binary representation of the given integer. Lastly, the binary representation of a number is basically using zeros and ones to symbolize the number. Our goal is to return this hamming weight of the given integer n.

Solved

To solve this question, we can use bitwise operators and a while loop to optimally find the amount of ones / ON bits. Our while loop continuously runs until given integer n is zero. Each iteration, add the &1 of n to our current sum. The &1 operation adds a 1 to our sum, if the least significant bit inside of n is also set. Also during each iteration, our n integer is bitwise shifted to the right by 1. This has the same affect as dividing n by two before flooring. In terms of binary representation, this shift to the right physically shifts all numbers to the right by one. The last digit after running this operation simply disappears. Once my while loop finishes executing, I use my sum variable to return the answer.

TLDR

Used bitwise operators and a while loop to efficiently iterate through each binary digit of the given n integer. While iterating through my while loop, I add to my sum variable before returning the answer.

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.