Skip to content
DevGod Repo
Blog

Blog

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.

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 70: Climbing Stairs

DevGod
DevGod
Elf Vtuber

About

This leetcode problem is about a fictional set of stairs, and finding the total amount of ways you could climb to the Nth step. Whilst climbing the stairs, you can choose to climb at most 1 or 2 steps at a time. Additionally, the problems lets us know that stairs 1,2,3 are equal to 1,2,3 ways respectively. I ended up using Top Down Dynamic Programming alongside Recursion plus Memoization for time optimization.

One way to think about this problem, is to imagine what leads up to your target Nth stair. For example, if you wanted to reach the 100th stair, you have to either climb one step from the 99th stair, or climb two steps from the 98th stair. Since the Nth stair is reachable from the previous two stairs, we can calculate the number of ways to reach the Nth stair by adding together the previous two stairs amount of climbing combinations. This forms a pattern similar to a Fibonacci number problems, where we want to find the answer based on the sum of previous answers we’ve found for the problem.

The sub problem of “Climbing Stairs” is that for each Nth stair, we must find the number of ways the previous two stairs had before adding them together. The base cases of this problem is that for any Nth stair less than or equal to three, the number of ways will be the same value as Nth. It is when stair’s N is greater than three that we must use our DP solution to find the total number of ways to climb up to that stair.

Additionally, since N can get large, I use a hash map named MEMO to store past results to reduce unnecessary recursive function calls, optimizing my solution by relying on cached past results for better speed. If my MEMO has a result for a given step I am looking for, then I just use that. However, if MEMO doesn’t contain the number of ways for the Nth stair I am looking for, then I proceed forward with running my recursive solution.

TLDR

Used Dynamic Programming, Recursion and Memoization to find the each Stairs number of ways to climb. Each Nth stair number of total ways relies on the previous two stairs total ways added together. Stairs 1,2,3 have one way, two ways, and three ways to climb to them respectively.

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.