Latest Event Updates
leetcode 1470. Shuffle the Array
This problem cant be looked at as such
- The array nums is made of two arrays joined together
- nums is [1,2,3,4]
- separate the two array
- array x is [1,2]
- array y is [3,4]
- recombine the arrays such that the new array is made in the following manner
- x[0],y[0],x[1],y[1]
- the result will be [1,3,2,4]
var shuffle = function(nums, n) {
// the array nums can be divided into two subarrays
// the value n is the length of each subarray
//
// To make this a one pass solution create two pointers
// one to the start of the first subarray
// the other to the start of the second subarray
let p1 = 0
let p2 = n //conveniently n is the index pointer2 should be at
const result = []
while(p1<n){
result.push(nums[p1])
result.push(nums[p2])
p1++
p2++
}
return result
};
leetcode 1512. Number of Good Pairs faster than 92.15% of JavaScript online submissions
The way I approached the problem was that we are only looking for equivalent pairs. Meaning if our current value is a 1, the only other values we are concerned with is other 1 values. in [ 1,2,3,4,1,2,3,4,1] when looking at value of once, we only care about index 0 and index 4
Rather then loop through the array every time we need a change values, lets loop through the array one time, and put all the equivalent values together. example. lets get [1,1,1] [2,2] [3,3] [4,4]
To get them all together in one pass, use a dictionary to hold values that are the same. I pushed the index values into the array, but that’s actually not needed. Next step will tell us why
Once we have all equivalent values together, such as [1,1,1] we could loop trough the sub array and make combinations. But using math we actually shorten this, not needed to manually make combinations. I figured there must be a mathematical way to do this. This stackoverflow link gave me the correct mathematical formula to proceed.
var numIdenticalPairs = function(nums) {
let d = {} //create dictionary
nums.forEach( (e,index)=> { //iterate over array
//if key does not exist, add it
if(d[e] === undefined){ d[e] = [index]}
//else push value to key's array
else { d[e].push(index) }
})
let pairs = 0
Object.keys(d).forEach(key=>{ //get count of pairs
let n = d[key].length
pairs += (n * (n-1))/2
})
return pairs
};leetcode 202. Happy Number memory usage better than 100% JavaScript
What the problem is asking for is
- look at each digit separately
- square the digit
- sum all the squares
- if the sum of the squares will eventually equal 1, its a happy number
To solve this problem you have to know a mathematical trick, else the loop will go on forever. Once n < 10, if n is 1 or 7 the number will be happy. Any other number will cause an infinite loop.
var isHappy = function(n) {
if(n<10){
if(n===1 || n===7){return true}
return false
}
let sum = 0
while(n>0){
let value = n % 10
sum += value**2
n -= value
n /= 10
}
if(sum ===1){return true} //I could leave this out...
return isHappy(sum)
};leetcode 118. Pascal’s Triangle memory usage beats 92.69 % of JavaScript submissions.
While doing this leetcode problem I ended up with a nice position in memory usage for this problem
var generate = function(numRows) {
//base cases
if(numRows === 0){return []}
if(numRows === 1){return [[1]]}
if(numRows === 2){return [[1],[1,1]]}
const arr = [[1],[1,1]]
//we start with counter of 2 because we are now on the subarray in postion 2
// remember arrays are 0 based
let counter = 2
while(counter<numRows){
let row = [1] //fill out the outter left of the triangle
let innerCounter = 1 //counter for inner loop
while(innerCounter <= counter-1){
//push the sum of the values of left and right parent nodes
// they are not really nodes, but when you look at the provided image
// they can be seen as a kind of node
row.push(arr[counter-1][innerCounter-1] + arr[counter-1][innerCounter])
innerCounter++
}
row.push(1) //fill out the outer right of the triangle
arr.push(row) //push the subarray onto the main array
counter++
}
return arr
};leetcode : 190. Reverse Bits JavaScript solution
Here is a simple way to reverse bits in JavaScript. This method uses string manipulation rather than bit manipulation, but it works and may be easier to grasp for someone who does not have a Computer Science background.
toString(2)
This is one of the keys to making the solution work. The input is a base 10 number. When calling toString() on the number we can also apply an optional parameter radix, which is a fancy way of saying “base”, and in this case base 2 aka binary.
var reverseBits = function(n) {
//convert the number to base2 then stringify, split, and reverse
let reversedArray = n.toString(2).split("").reverse()
//the converted number may not be 32 digits so pad the end
while(reversedArray.length <32){ reversedArray.push('0')}
//join the string, then convert to Integer from base 2
return parseInt(reversedArray.join(""),2)
};leetcode : 326. Power of Three
A small and simple recursive solution to the power of 3 problem.
What the problem is asking for is if the value given is a power of 3. So 9 or 27 would be true because 3*3=9, and 3*3*3=27.
A number who has 3 has one of it’s factors would be false. Example 18, which is 3*3*2 is not a power of three
var isPowerOfThree = function(n) {
//base case : 3 to the power of 0 is 1
if(n === 1){return true}
//Since JS uses floating numbers, eventually when you keep dividing by 3
//the value of n will either be 3,1, or some floating number less than 3
if(n < 3){return false}
//either we end up with n as 3, or we call our function again
return ( n / 3 === 1 || isPowerOfThree(n/3))
};leetcode : 198. House Robber
This is another dynamic programming problem. The way to solve this is to focus only which is greater A) sum of houses robbed until element i or B) the sum of houses robbed up to i-1
The reason we have to make the this decision comes down to the fact that we cannot rob adjacent houses so we have to calculate weather its more profitable to rob the current house or the adjacent houses.
The defaults are the following
- If there are no houses, return 0
- If there is only 1 house return the value of house 1
- If there are 2 houses, return the grater value of house 1 or house 2
after being aware of the above, lets create an array to hold the return value if n were to have equaled i. To rephrase, break the problem size down. Instead of worrying about what happens when the array size is n, lets worry about what would we return if we stopped the array right now.
var rob = function(nums) {
if(!nums || nums.length === 0){return 0}
if(nums.length === 1){return nums[0]}
if(nums.length === 2){return Math.max(nums[0],nums[1])}
const arr = new Array(nums.length).fill(0)
arr[0]=nums[0]
arr[1]=Math.max(nums[0],nums[1])
for(i=2;i<nums.length;i++){
arr[i] = Math.max(nums[i] + arr[i-2], arr[i-1])
})
return Math.max(arr[arr.length-1],arr[arr.length-2])
};If you are having a problem understanding, just walk through the first few steps
If nums is 4,2,8,9,0 this is what we would fill our new array with
- [0] -> nums[0] -> 4
- [1] -> the greater of nums[0] or nums[1] -> 4
- [2] -> the greater of nums[2] + array[0] = 12 or array[1] = 2 -> 12
- [3] -> the greater of nums[3] + array[1] = 13 or array[2] = 12 -> 13
- [4] -> the greater of nums[4] + array[2] = 12 or array[3] = 13 -> 13
We return 13
leetcode : 70. Climbing Stairs a bottom up approach using Dynamic Programming
Dynamic Programming – boils down to solve smaller problems to solve bigger ones. How can I eat a loaf of bread? One slice at a time.
We can solve this with O(n) time and O(1) memory
- O(n) time because we will calculate each step to n
- O(1) time because we are using a limited set of variables. We only care about i-1 and i-2 which will help us get each iteration of i
var climbStairs = function(n) {
let nMinus2=1
let nMinus1=1
for(i=2;i<=n;i++){
let current = nMinus1 + nMinus2
nMinus2 = nMinus1
nMinus1 = current
}
return nMinus1 //we return nMinus1 because it holds the value of i === n
};leetcode : Binary Tree Level Order Traversal
Solution with comments to describe the process of solving this problem
var levelOrder = function(root) {
//result will be an array of arrays
// each subarray will include all the values of that depth
//example subarry in position 1, is the 2nd element
// it will contain all values of the depth level of 2
//another example is subarray in position 0, which is the 1st element
// it contains all values of depth 1, in this case the root's value
const result = []
// base case in case we get an empty tree
if(!root){return result}
//just an array we will use as a queue
// we will work with elements in a FIFO (first-in-first-out) manner
// some places this listed as stack, but thats the wrong term
// as a stack is LIFO (last-in-first-out)
const queue = []
//we push our root onto our queue to get started
queue.push(root)
//as long as the queue exists we will go through the loop
while(queue.length > 0){
//row will be an array of all values of current depth
const row = []
//keeps treack of queue size for this depth
// this way we know how many elements to shift out of the queue
// and push the values onto row
let queueSize = queue.length
//in the loop we take a node, push its child nodes to queue
// then we push the value of node onto the row
while(queueSize > 0){
const node = queue.shift()
if(node.left){queue.push(node.left)}
if(node.right){queue.push(node.right)}
row.push(node.val)
queueSize--
}
//once all nodes of a certain depth have been evaluated
// we push the array row into result
// with its position in result being the depth
result.push(row)
}
return result
};leetcode : Maximum Depth of Binary Tree : Iterative solution
Here is a iterative solution on the Max Depth of a tree problem. I solved it using recursion, but then tried to solve it using an iterative process. I added comments and some extra variables for readability to make them easier to follow along
var maxDepth = function(root, depth=0) {
//base case: if we are given an empty or null LinkedList return 0
if(!root){return 0}
//construct the array which will hold nodes
let a = []
//currently max is 0. As we traverse tree, it will grow
let max = 0
//initialize the array by adding a node, and node depth
//in this case root and 1
a.push([root,1])
//loop through while array has elements
while(a.length > 0){
//I added the following variables for readability so
//if you are learning its easier to follow along
let node = a[0][0]
let depth = a[0][1]
//if the node has a left node or right node
//add the left and right to the array
//while incrementing the depth, because
//left or right is 1 deeper then current depth
if(node.left){a.push([node.left,depth+1])}
if(node.right){a.push([node.right,depth+1])}
//here we update the max if the depth found is greater
if(a[0][1] > max){max = a[0][1]}
//we remove the node because we no longer need it
a.shift()
}
return max
};
vSPARROW 