Month: June 2020

leetcode : 326. Power of Three

Posted on

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

Posted on

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

Posted on

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

Posted on

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

Posted on

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
};

leetcode : 234. Palindrome Linked List : memory usage beats 98.70 % of javascript submissions

Posted on

Another memory success for one of my leetcode solutions

When reading the variables sonic and tails, remember the game, Sonic is always faster than Tails, which is why hes one step ahead.

//isPalindrome      - base function 
//getLength         - helper function
//reverseFromMiddle - helper function

//get Length of Linked List
const getLength = head => {
    let counter = 0
    while(head){
        head = head.next
        counter++
    }
    return counter
}

const reverseFromMiddle = (head,middleIndex)=>{
    let middleHead=null
    for(i=1;i<=middleIndex;i++){ //1 because head is already the first node
        head = head.next
    }
    // console.log(`reverseFromMiddle head is ${head.val}`)
    let sonic = head.next
    let tails = head
    tails.next = null
    while(sonic){
        let temp =tails
        tails=sonic
        sonic=sonic.next
        tails.next =temp
    }
    // console.log(`sonic is ${sonic}`)
    // console.log("tails is", tails)
    return tails
}

var isPalindrome = function(head) {
    //if we get an empty node counts as valid palindrome
    if(!head){return true} 
    //get the length of the Linked List
    let length = getLength(head);
    //calculate 1/2 point of node
    let middleIndex = ~~(length/2)
    //from 1/2 point of Linked List 
    // start reversing into a reversed Link List
    let middleHead = reverseFromMiddle(head,middleIndex)
    //compare 2 havles
    while(head && middleHead){
        if(head.val != middleHead.val){return false}
        head = head.next
        middleHead=middleHead.next
    }
    return true
};

runtime beats 55.40 % of javascript submissions

Microsoft Office Click-to-Run service keeps re-enabling itself

Posted on Updated on

Microsoft Office Click-to-Run service keeps re-enabling itself even after being set to disabled. Every time I hear my CPU fans running, I’m thinking, why MS why.. I end the task and then go back to services to see that again, the service has been set to automatic.

Following “yonkers12″‘s advice on windows forums, after stopping and disabling the service, I changed the logon from ” Local System Account” to “This Account” using username “.\Guest” and a blank password

leetcode : Longest Common Prefix : simple JavaScript solution

Posted on

This is not the fastest solution’s by far, but I think that it is one of the more simple ones to understand.

var longestCommonPrefix = function(strs) {
    if(!strs[0]){return ""} //empty array case
    let lcp = "" //base case 
    //lcp can never be greater then first string 
    //so we can use it as the max length of our loop
    for(i=0;i<strs[0].length;i++){   
        let c=strs
            .map(s=>s[i])  //get all the i'th index letters 
            //get all the unique letters gathered in map
            .reduce((arr,char)=> arr.includes(char) ? arr : [...arr,char], [])
         if(c.length === 1){lcp += c[0]} //if unique letters == 1, keep looping
        else{break} //else loop is over
    }
    return lcp
};

leetcode : 344. Reverse String : memory usage beats 99.55 % of javascript submissions

Posted on Updated on

Nice, another leetcode challenge where I beat most of the submissions in memory.

This is most likely because people did not pay attention to the spec which says: “Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.” I took that to mean as you can only have one extra variable so that’s what I used

var reverseString = function(s) {
    for(i=0;i<~~(s.length/2);i++){
        let temp = s[i]
        s[i]=s[s.length-1-i]
        s[s.length-1-i] = temp
    }
};

Runtime could have been better. My runtime beats 15.26 % of javascript submissions.

leetcode : 867. Transpose Matrix

Posted on

This one took a while to get. Originally I was trying to transpose in place, but you cannot guarantee the input is a square, so in place won’t work.Not sure if even in C you can transpose in place for a rectangular input. There maybe some memory tricks there, but they definitely are not available for JavaScript

Code is commented to guide

var transpose = function(A) {
    //this problem we actually cant transpose in place
    //since we cannot guarantee that the input is a square
    
    const result = []
    const rowsLength = A[0].length
    const columnsLength = A.length
    
    for(i=0;i<rowsLength;i++){
        let column = []
        for(j=0;j<columnsLength;j++){
            //here we get all elements in a column from input array A
            //and add it to new array named column
            column.push(A[j][i])
        }
        //we take the variable column we generated above
        //and turn it into a row for output Array result
        result.push(column)
    }
    return result
};