Month: July 2020

leetcode 1470. Shuffle the Array

Posted on

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

Posted on

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

Posted on

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.

Posted on

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

Posted on

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