DEV Community: Andrew Hsu

Leetcode Daily - Sum of Left Leaves

Andrew Hsu — Mon, 24 Aug 2020 17:57:29 +0000

Leetcode Daily - August 24, 2020

Sum of Left Leaves

Lately I've been grinding Leetcode and decided to record some of my thoughts on this blog. This is both to help me look back on what I've worked on as well as help others see how one might think about the problems.

However, since many people post their own solutions in the discussions section of Leetcode, I won't necessarily be posting the optimal solution.

Question

(Copy Pasted From Leetcode)

Find the sum of all left leaves in a given binary tree.

Example:

    3
   / \
  9  20
    /  \
   15   7

There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.

My Approach(es)

I won't go over all the code for all attempts but I will explain my approach(es) qualitatively.

Attempt 1 - DFS

(Submission - Accepted)

When I see a tree problem like this, my go-to is DFS or BFS (I usually start with DFS by default), and I tend to use a stack (you can use recursion as well).

The principle is to simply check each node to find nodes that:

Are leaves
Were the left of their parent

Once a node is found that meets these conditions, I can simply add their value to a sum that is initialized to zero at the start of the program.

The only additional thing I really need is a data structure that tells the current node if it was the left or right of its parent (or root if it is root).

I implemented this with a dictionary (in Python) that stores the node, and 'nType', or node type. The node type is currently either 'root', 'right' or 'left'. I left the type as a string for the purposes of quickly submitting code, but an enum can be used since the data can only be one of a possible set.

Submitted Code (Python):

class Solution(object):
    def sumOfLeftLeaves(self, root):

        if root == None:
            return 0
        result = 0 
        stack = [{'node': root, 'nType': 'root'}]

        # dfs using a stack 
        # add to result if left and a leaf 
        # should add an additional data, whether it was left or right or root
        while len(stack) > 0:
            curr = stack.pop() 
            currNode = curr['node']
            currType = curr['nType']

            # check if leaf 
            if currNode.left == None and currNode.right == None and currType == 'left':
                result += currNode.val

            # add children to tree 
            if currNode.left != None:
                stack.append({'node': currNode.left, 'nType': 'left'})

            if currNode.right != None:
                stack.append({'node': currNode.right, 'nType': 'right'})

        # end of while loop
        return result

Discussion and Conclusions

As mentioned in the approach section, a better data structure such as an enum could be used for storing the status of the current node. But my main concern for optimizing performance is whether I can consistently search less than O(n) (where n is the number of nodes in the tree) nodes.

I've been thinking about how to potentially rule out certain portions of the tree, but based on the node data structure I'm not sure that's feasible. Basically, since any node can have a left child, and each node points to its children but not its parents, we would have to check every node to make sure that it's not both left and a leaf node.

Leetcode Daily - Longest Palindrome

Andrew Hsu — Fri, 14 Aug 2020 15:45:28 +0000

Leetcode Daily - August 14, 2020

Longest Palindrome

Link to Leetcode Question

However, since many people post their own solutions in the discussions section of Leetcode, I won't necessarily be posting the optimal solution.

Question

(Copy Pasted From Leetcode)

Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.

This is case sensitive, for example "Aa" is not considered a palindrome here.

Note:
Assume the length of given string will not exceed 1,010.

Example:

Input:
"abccccdd"

Output:
7

Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.

My Approach(es)

I won't go over all the code for all attempts but I will explain my approach(es) qualitatively.

Attempt 1 - Determine Logical Conditions For Longest Palindrome Length

(Submission - Accepted)

I ended up approaching this as a logic problem instead of as a computer science problem. The first thing I noticed is that, except for a middle character, palindromes have matching pairs of the same character symmetric with the middle. So if we were to count how many of each unique character we have, all even sets would be able to go on a palindrome, but there is only space for only one odd "spare" letter.

I decided to pseudocode first and then write my code following this blueprint:

Count each of the letters and store the counts
Go through each of the counts and start adding them to a sum
- The sum is the length of the longest palindrome length
- If a count is even, we add it
- If the count is odd, and we haven't seen an odd, we add it
- If the count is odd, and we already added an odd, we add that count minus one (the largest even value we can add)

Submitted Code (Javascript):

var longestPalindrome = function(s) {
    // palindrome can only contain up to one odd set of letters 
    // all even sets of letters work 
    // go through the string and store all the unique letter counts 
    const dict = {}

    for (let i = 0; i < s.length; i++) {
        if (dict[s[i]]) {
            dict[s[i]] += 1
        } else {
            dict[s[i]] = 1
        }
    }

    // make an array of our letter counts to iterate on 
    let letterCount = [] 
    Object.keys(dict).forEach(key => {
        letterCount.push(dict[key])
    })

    // create variables to remember how long our longest palindrome is 
    // as well as whether we have our one odd letter set 
    let sum = 0
    let seenEven = false 
    // start adding up letter sets

    for (let count of letterCount) {
        if (count % 2 === 0) {
            sum += count 
        } else {
            if (!seenEven) {
                // add odd set if haven't seen one yet
                sum += count 
                seenEven = true 
            } else {
                // turn into even set and add 
                sum += count - 1
            }
        }
    }
    return sum
};

Discussion and Conclusions

I think the solution based on logic is very straightforward, and has time and space complexity of O(n) where n is the length of s. There are probably programming and computer science tricks that can optimize this code even further.

For example, I thought about it afterwards and instead of storing whether we have seen an odd or not, we could always add the "evenized" value, for example count - (count%2). Then add the end, if the longest palindrome length sum were less than s.length, we could simply add 1 (there are spare letters left).

Resubmitted Code:

var longestPalindrome = function(s) {
    // palindrome can only contain up to one odd set of letters 
    // all even sets of letters work 
    // go through the string and store all the unique letter counts 
    const dict = {}

    for (let i = 0; i < s.length; i++) {
        if (dict[s[i]]) {
            dict[s[i]] += 1
        } else {
            dict[s[i]] = 1
        }
    }

    // make an array of our letter counts to iterate on 
    let letterCount = [] 
    Object.keys(dict).forEach(key => {
        letterCount.push(dict[key])
    })

    // create variables to remember how long our longest palindrome is 
    // as well as whether we have our one odd letter set 
    let sum = 0

    // start adding up letter sets    
    for (let count of letterCount) {
        sum += count - (count%2)
    }
    if (sum < s.length) sum ++
    return sum
};

Leetcode Daily - Iterator for Combinator

Andrew Hsu — Thu, 13 Aug 2020 21:38:01 +0000

Leetcode Daily - August 13, 2020

Iterator for Combinator

Link to Leetcode Question

However, since many people post their own solutions in the discussions section of Leetcode, I won't necessarily be posting the optimal solution.

Question

(Copy Pasted From Leetcode)

Design an Iterator class, which has:

A constructor that takes a string characters of sorted distinct lowercase English letters and a number combinationLength as arguments.
A function next() that returns the next combination of length combinationLength in lexicographical order.
A function hasNext() that returns True if and only if there exists a next combination.

Example:

CombinationIterator iterator = new CombinationIterator("abc", 2); // creates the iterator.

iterator.next(); // returns "ab"
iterator.hasNext(); // returns true
iterator.next(); // returns "ac"
iterator.hasNext(); // returns true
iterator.next(); // returns "bc"
iterator.hasNext(); // returns false

Constraints:

1 <= combinationLength <= characters.length <= 15
There will be at most 10^4 function calls per test.
It's guaranteed that all calls of the function next are valid.

My Approach(es)

I won't go over all the code for all attempts but I will explain my approach(es) qualitatively.

Attempt 1 - DFS or BFS

(Submission - Accepted)

I decided to use the following data structures for my class:

Store the characters as a string and combinationLength as a number
Use the idea of a mask consisting of 0's and 1's. This is to determine which characters from the character string will be used to form the output string of .next()
Also generate and store all possible masks when the constructor is run. The main reason for this is that I am familiar with using search/backtracking to create all the permutations of ones and zeros, but if I'm not sure how best to iterate from one given permutation to the next.

Once the array of all possible masks is calculated, .next() and .hasNext() become pretty easy if we are storing the mask index.

.next() iterates the mask index and then uses the mask to return a string.
.hasNext() just check to see if the mask index is not the last index of the array.

Submitted Code in Javascript:

var CombinationIterator = function(characters, combinationLength) {
    this.characters = characters
    this.combinationLength = combinationLength 
    // should we generate all combinations now? or when the methods are called? 
    // for testing purposes let's generate them now 
    // string mask of characters 

    this.mask = []

    // to keep lexographical order we need bfs 
    let stack = ['']
    const charLength = characters.length 
    while (stack.length > 0) {
        // if length is 6, add it to this.mask 
        // else, add the possible combinations to the stack 
        // prefer adding 1's first up to combinationLength 
        const currCombo = stack.shift()
        if (currCombo.length === charLength) {
            this.mask.push(currCombo)
        } else if (currCombo.length < charLength) {
            // regex match /<char>/g returns array, so length of that 
            if ((currCombo.match(/1/g) || []).length < combinationLength) {
                stack.push(currCombo+"1")
            }
            if ((currCombo.match(/0/g) || []).length < charLength - combinationLength) {
                stack.push(currCombo+"0")
            }
        }
    }

    this.maskInd = -1
    console.log('initial masks: ', this.mask)

};

/**
 * @return {string}
 */
CombinationIterator.prototype.next = function() {
    this.maskInd ++ 
    const currMask = this.mask[this.maskInd]
    let result = ''
    for (let i = 0; i < currMask.length; i++) {
        if (currMask[i] === "1") {
            result += this.characters[i]
        }
    }
    return result 
};

/**
 * @return {boolean}
 */
CombinationIterator.prototype.hasNext = function() {
    // mask cannot iterate if there are no more combinations 
    return this.maskInd < this.mask.length-1
};

Discussion and Conclusions

I want to explore the approach of iterating the next combination based on the previous combination mask. This is because when the constructor is run, it is doing all the computational work up front, and finding all the permutations.

There are C(n, k) (n choose k) combinations, where n is the length of characters and k is combinationLength. And the height of the tree formed by my search is k (because there are k characters in a valid string) so the breadth-first-search scales at O( k*C(n,k) ).

If we use the formula for calculating combinations, we get:

 k * C(n,k) = k *  n!/(k! * (n-k)!) 
            = n!/((k-1)! * (n-k)!)

We can reduce the time complexity of the constructor if we just generate the initial mask, and developed a formula to determine the next mask based on the previous.

I wrote the following pseudocode in my comments but did not settle on a way to consistently determine the next mask value. I realized that at some point, the ones that have been moved from the left all the way to the right would have to be reset back to a position on the left. However, the next 1 on the left would've been shifted once to the right.

Example for characters.length = 6 and combinationLength = 3:

    111000 110100 110010 110001 
    reset to 101100 ... 101001
    reset to 100110 ... 100101
    reset to 100011 ... 100011
    reset to 011100 ... 011001

For my next steps I will explore writing an algorithm that can determine the next mask value from the previous. Since it follows a logical progression it should be possible, but I need to come up with some valid conditional statements for determining when to "reset" some of the 1's from the right back to the left.

Leetcode Daily - H-Index

Andrew Hsu — Tue, 11 Aug 2020 17:04:59 +0000

Leetcode Daily - August 11, 2020

H-index

Link to Leetcode Question

However, since many people post their own solutions in the discussions section of Leetcode, I won't necessarily be posting the optimal solution.

Question

(Copy Pasted From Leetcode)

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.

According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each."

Example:

Input: citations = [3,0,6,1,5]
Output: 3 
Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had 
             received 3, 0, 6, 1, 5 citations respectively. 
             Since the researcher has 3 papers with at least 3 citations each and the remaining 
             two with no more than 3 citations each, her h-index is 3.

Note: If there are several possible values for h, the maximum one is taken as the h-index.

My Approach(es)

I won't go over all the code for all attempts but I will explain my approach(es) qualitatively.

Attempt 1 - Check Possible H-Index Values

(Submission - Accepted)

To start out this question, I decided to think about how I would solve this for simple arrays as a human. I took a minute to understand and clarify the definition of h-index.

"A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each."

I made the following notes:

The h-index is a type of maximum value which satisfies the stated conditions.
The h-index depends on counting the number of papers which satisfies a condition.
The condition is simply related to the number in the array (number of citations).

I decided that for my first attempt I could complete it with an O(n²) solution. First we set the h-index to be the maximum possible value, which is the number of papers published. Then we iterate down and check if it meets the h-index conditions.

Submitted Code:

var hIndex = function(citations) {
    let tryH = citations.length;

    while (tryH > 0) {
        let counter = 0;
        for (let i = 0; i < citations.length; i++) {
            if (citations[i] >= tryH) counter ++;
        }
        if (counter >= tryH) return tryH;
        tryH --
    }
    return 0;
};

Attempt 2 - Remove one iterative loop from O(n²) solution

(Submission - Accepted)

I have to admit here that while I realized I needed to optimize on the O(n²) solution, I also realized that I had seen this problem before.

I had seen this problem in the introduction section of the book: Elements of Programming Interviews in Python, where they detail the thought process and more optimal solution to the h-index problem.

I use the same concept they explain in the book, which is to sort the array first. This is because, if you sort the array from high to low, then if citations[i] >= i+1 then all the previous values in citations are also greater than or equal to i+1, which is the number of papers (array index but counting starting from 1 instead of 0).

Assuming the sort is O(nlog(n)), now the iterative element of the algorithm is O(n) so the total time complexity is O(nlog(n)).

Submitted Code:

var hIndex = function(citations) {
    citations.sort((a,b) => b-a);

    let counter = 0;

    for (let i = 0; i < citations.length; i++) {
        if (citations[i] >= i+1) counter++;
        else return counter;
    }

    return counter;
};

Discussion and Conclusions

This is a very interesting example for me because it touches on a lot of challenges newer coders might run into on technical interview questions. The first one is to clarify and understand the question correctly. The second is to understand the approach and how to optimize it. And finally, it is personally interesting to me because I got the Elements of Programming Interviews book when I started studying coding challenges, and it took me a long time to comprehend and try programming the questions. But after almost one year of studying I feel so much more comfortable with questions like these that I want to remember what my initial feeling of being challenged was like so I won't be as intimidated by harder questions in the future.

Leetcode Daily - Excel Sheet Column Number

Andrew Hsu — Mon, 10 Aug 2020 15:17:01 +0000

Leetcode Daily - August 10, 2020

Excel Sheet Column Number

Link to Leetcode Question

However, since many people post their own solutions in the discussions section of Leetcode, I won't necessarily be posting the optimal solution.

Question

(Copy Pasted From Leetcode)

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

    A -> 1
    B -> 2
    C -> 3
    ...
    Z -> 26
    AA -> 27
    AB -> 28 
    ...

Example 1:

Input: "A"
Output: 1

Example 2:

Input: "AB"
Output: 28

Example 3:

Input: "ZY"
Output: 701

Constraints:

1 <= s.length <= 7
s consists only of uppercase English letters.
s is between "A" and "FXSHRXW".

My Approach(es)

I won't go over all the code for all attempts but I will explain my approach(es) qualitatively.

Attempt 1 - Treat the string as a base 26 number

(Submission - Accepted)

After trying out some examples by hand, I realized that this column naming system is basically a base 26 number. The notable difference is that instead of having a zero digit, we start at 1 with A and end at 26 with Z. Then, 27 resets to AA, which is:

 27 = 1*26 + 1*1 
 27 = A*(26^1) + A*(26^0)

Similarly, ZY, which is 701, can be broken down as:

 701 = 26*26 + 25*1 
 701 = Z*(26^1) + Y*(26^0)

Even without the zero digit, we can be fairly confident in our conversion system. The numbers start counting at 26 to the zeroth power, just like how other number bases start at the zeroth power.

With this we can write our Javascript code, which starts at the right side of the string and starts iterating the powers of 26. I used a dictionary to convert the individual letters to numbers.

Submitted Code:

var titleToNumber = function(s) {
    // s is a string, but basically converts to a number in base 26 
    // also instead of zero we have 26 
    const dict = {
        A: 1, B: 2, C: 3, D: 4, E: 5, F: 6, G: 7, H: 8, I: 9, J: 10, K: 11, L: 12, M: 13, N: 14,
        O: 15, P: 16, Q: 17, R: 18, S: 19, T: 20, U: 21, V: 22, W: 23, X: 24, Y: 25, Z: 26
    }
    let number = 0;
    let power = 0;
    for (let i = s.length-1; i >= 0; i--) {
        number += Math.pow(26, power)*dict[s[i]];
        power ++;
    }
    return number;
};

Attempt 1A - Still Treating the string as a base 26 number

(Submission - Accepted)

I just wanted to try writing this but reading the string's digits from left to right instead of right to left. Instead of adding the correct power of 26, this iterative method takes the previous number and multiplies all of it by 26 (because it's all numbers from left to right so far), and then adds the specific digit.

Submitted Code:

var titleToNumber = function(s) {
    // s is a string, but basically converts to a number in base 26 
    // also instead of zero we have 26 
    const dict = {
        A: 1, B: 2, C: 3, D: 4, E: 5, F: 6, G: 7, H: 8, I: 9, J: 10, K: 11, L: 12, M: 13, N: 14,
        O: 15, P: 16, Q: 17, R: 18, S: 19, T: 20, U: 21, V: 22, W: 23, X: 24, Y: 25, Z: 26
    }
    let number = 0;

    for (let i = 0; i < s.length; i++) {
        number = number*26 + dict[s[i]];
    }
    return number;
};

Discussion and Conclusions

There is not much I want to say about this question. Once the naming/numbering system is understood, the conversion can be done as a numerical base 26 conversion, with the added step of parsing the string. Even though I'm sure there are ways to optimize the code, I believe this is sufficient understanding of the problem.

The time complexity is O(n) for n equal to the length of string s, but the length of s is constrained to be less than or equal to 7.

Leetcode Daily - Rotting Oranges

Andrew Hsu — Mon, 10 Aug 2020 05:41:25 +0000

Leetcode Daily - August 9, 2020

Rotting Oranges

Link to Leetcode Question

However, since many people post their own solutions in the discussions section of Leetcode, I won't necessarily be posting the optimal solution.

Question

(Copy Pasted From Leetcode)

In a given grid, each cell can have one of three values:

the value 0 representing an empty cell;
the value 1 representing a fresh orange;
the value 2 representing a rotten orange. Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1 instead.

Example 1:

Input: [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Example 2:

Input: [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation:  The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3:

Input: [[0,2]]
Output: 0
Explanation:  Since there are already no fresh oranges at minute 0, the answer is just 0.

Note:

1 <= grid.length <= 10
1 <= grid[0].length <= 10
grid[i][j] is only 0, 1, or 2.

My Approach(es)

I won't go over all the code for all attempts but I will explain my approach(es) qualitatively.

Attempt 1 - Brute Force (iterate out the grids)

(Submission - Accepted)

My basic thought process focused on whether I could determine if the rotting oranges would reach all the fresh oranges on the grid. I realized that if the board didn't change between one minute and the next, that it wouldn't change at all anymore, because rotten oranges only spread to adjacent fresh oranges.

My brute force approach simply iterates the grid minute by minute by checking all the fresh oranges for adjacency to rotten oranges and then changing them from 1 to 2. I decided to use a while loop with a counter that counts the number of minutes elapsed (number of iterations).

I used a while loop but I realized there were two ending conditions:

The counter amount should be returned if the grid has no fresh oranges left.
The value -1 should return instead if the grid does not change from iteration N to iteration N+1 (but there are still fresh oranges left).

The only other complication is making copies of the grid so that I could check if the new grid (after rotten orange spread has been calculated) is the same as the current grid (before the rotten oranges spread for that minute). In Javascript, assigning the arrays equal to each other would make them reference the same array, so they would always end up equal. I wrote some helper functions in my code but end up with a pretty cumbersome implementation.

var orangesRotting = function(grid) {
    let currGrid = copyGrid(grid);
    let minutes = 0;

    while (true) {
        // check currentGrid for fresh (1)
        if (!hasFresh2D(currGrid)) {
            return minutes
        }

        let newGrid = copyGrid(currGrid);
        // process the new Grid for rottenness 
        for (let i = 0; i < newGrid.length; i++) {
            for (let j = 0; j < newGrid[0].length; j++) {
                // check 4 directions of a 1 for 2's, if true change it to a 2 
                if (newGrid[i][j] === 1) {
                    if (i-1 >= 0 && currGrid[i-1][j] === 2) newGrid[i][j] = 2
                    if (j-1 >= 0 && currGrid[i][j-1] === 2) newGrid[i][j] = 2
                    if (i+1 < newGrid.length && currGrid[i+1][j] === 2) newGrid[i][j] = 2
                    if (j+1 < newGrid[0].length && currGrid[i][j+1] === 2) newGrid[i][j] = 2
                }
            }
        }

        // check if no fresh oranges get rotten 
        if (allEqual2D(currGrid, newGrid)) {
            // cannot get more oranges rotten 
            // because no change 
            return -1;
        }

        minutes ++ 
        currGrid = copyGrid(newGrid);
    }
};

const copyGrid = (arrs1) => {
    let result = [];
    for (let i = 0; i < arrs1.length; i++) {
        result.push(arrs1[i].slice())
    }
    return result;
}

const allEqual2D = (arrs1, arrs2) => {
    // assume the lengths are equal, just want to check values 
    for (let i = 0; i < arrs1.length; i++) {
        for (let j = 0; j < arrs1[0].length; j++) {
            if (arrs1[i][j] !== arrs2[i][j]) return false;
        }
    }
    return true;
}

const hasFresh2D = (arrs1) => {
    for (let i = 0; i < arrs1.length; i++) {
        for (let j = 0; j < arrs1[0].length; j++) {
            if (arrs1[i][j] === 1) return true;
        }
    }
    return false 
}

Discussion and Conclusions

Some of my notable thoughts about my implementation can be summarized as:

Can I use a different data structure to store the grids instead of a 2D array?
Are there better indicators or ways of calculating the ending conditions? For example, Using a search algorithm starting from every rotten orange to every fresh orange. The search algorithms would also calculate the manhattan grid distances and the maximum value would be returned unless theres are fresh oranges that cannot be reached (if at least one exists, return -1).
I believe the algorithm I used is O(n⁴), if n is the length or width of the grid. That is because I check the entire grid once per iteration (O(n²), and for a rotten orange to spread from one corner to a fresh orange in the other it whose maximum path (if zigzagging) can take around half the boxes of the grid (and the size of the grid is O(n²). But luckily, n is constrained to 10, and n⁴ is 10,000, so investigating better algorithms for dealing with grids could pay off.

Leetcode Daily - Path Sum III

Andrew Hsu — Sun, 09 Aug 2020 02:10:12 +0000

Leetcode Daily - August 8, 2020

Path Sum III

Link to Leetcode Question

However, since many people post their own solutions in the discussions section of Leetcode, I won't necessarily be posting the optimal solution.

Question

(Copy Pasted From Leetcode)

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

My Approach(es)

I won't go over all the code for all attempts but I will explain my approach(es) qualitatively.

Attempt 1 - DFS or BFS

(Submission - Accepted)

After looking at the expected answer of the example, I was a little worried. For a given long path, I thought about the complexity of finding all the combination of paths and then their sums. For example, from root to the bottom left is 10 -> 5 -> 3 -> 3. There are 4 + 3 + 2 + 1 = 10 paths, because there is one path of length 4, two of length 3, three of length 2 and four of length 1.

However, I thought about how to record these path sums and realized that recording the whole path then checking the sum of all combinations was a bit cumbersome. If a binary tree has k levels, the path would require storage of O(k), and the time complexity becomes O(k^2) combinations per check.

I decided to store the sums of all paths leading to the current node. Each node would have to do a calculation of adding its own value to this array, but also push its value to the array to represent the path starting and ending at itself. If a binary has k levels, then this array's storage and the adding operation's time complexity should both be O(k).

var pathSum = function(root, sum) {
    // dfs or bfs while storing a sums array 
    // when it reaches a certain node, add val to all in the sums array then push val 
    // finally, if any paths are equal to sum then counter ++ 
    let counter = 0;
    let stack = [{
        ...root,
        sums: []
    }]
    while (stack.length > 0) {
        const currNode = stack.pop();

        // process sums array 
        const newSums = currNode.sums.map(s => s+currNode.val);
        newSums.push(currNode.val);
        newSums.forEach(s => {
            if (s === sum) {
                counter++;
            }   
        })

        if (currNode.left) stack.push({...currNode.left, sums: newSums});
        if (currNode.right) stack.push({...currNode.right, sums: newSums});
    }

    return counter
};

Discussion and Conclusions

I've done a lot of binary tree problems on Leetcode now and was able to complete a majority of them using depth and breadth first search. In this case, I haven't thought of a good idea to map this binary tree into another data structure, but instead how to calculate instances of the path sum while traversing the existing data structure. I will try to explore and keep in mind other ways to approach this problem.

Leetcode Daily - Vertical Order Traversal Of Binary Tree

Andrew Hsu — Fri, 07 Aug 2020 21:40:47 +0000

Leetcode Daily - August 7, 2020

Vertical Order Traversal Of Binary Tree

Link to Leetcode Question

However, since many people post their own solutions in the discussions section of Leetcode, I won't necessarily be posting the optimal solution.

Question

(Copy Pasted From Leetcode)

Given a binary tree, return the vertical order traversal of its nodes values.

For each node at position (X, Y), its left and right children respectively will be at positions (X-1, Y-1) and (X+1, Y-1).

Running a vertical line from X = -infinity to X = +infinity, whenever the vertical line touches some nodes, we report the values of the nodes in order from top to bottom (decreasing Y coordinates).

If two nodes have the same position, then the value of the node that is reported first is the value that is smaller.

Return an list of non-empty reports in order of X coordinate. Every report will have a list of values of nodes.

Example 1:

Input: [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]

Explanation:
Without loss of generality, we can assume the root node is at position (0, 0):
Then, the node with value 9 occurs at position (-1, -1);
The nodes with values 3 and 15 occur at positions (0, 0) and (0, -2);

The node with value 20 occurs at position (1, -1);
The node with value 7 occurs at position (2, -2).

Example 2:

Input: [1,2,3,4,5,6,7]
Output: [[4],[2],[1,5,6],[3],[7]]

Explanation:
The node with value 5 and the node with value 6 have the same position according to the given scheme.
However, in the report "[1,5,6]", the node value of 5 comes first since 5 is smaller than 6.

Notes:

The tree will have between 1 and 1000 nodes.
Each node's value will be between 0 and 1000.

My Approach(es)

I won't go over all the code for all attempts but I will explain my approach(es) qualitatively.

Attempt 1 - DFS or BFS

(Submission - Accepted)

Based on the detailed instructions, I understand that each node will have its own X and Y coordinate (relative to the root node's). With this understanding, I used depth first search to search the binary tree and add each node to a data structure. I used a Javascript object, which has hash table characteristics, to hold data about each node.

Since we need to return a data structure which sorts the nodes by X value, I decided to sort them by the X value when I add them to the container.

I wanted my container to look something like this after it's been filled in (using Example 1's values):

 const xCoordMap = {
   "-1": [{val:9, y:-1}],
   "0": [{val:3, y:0}, {val:15, y:-2}],
   "1": [{val:20, y:1}],
   "2": [{val:7, y:2}]
 }

Originally I tried to use breadth first search because that search algorithm searches through all the nodes of the same Y level consecutively. However, when there is a tie in Y value, the question wants the lower node value to be placed first. So I ended up recording the Y values in order to detect ties, and then sorted them first by highest Y value and then by lowest value (if the Y values are tied).

Submitted Javascript code:

var verticalTraversal = function(root) {
    // dfs or bfs but calculate the coordinates while running it 
    // using bfs we won't have to use the Y values to sort (?)
    // left goes to X-1, Y-1, right goes to X+1, Y-1 
    let stack = [{...root, x: 0, y:0}];

    let xCoordMap = {}

    const addNode = (val, x, y) => {
        // if the key, 'x', already exists, push it 
        // if it doesn't, make a new array 
        if (xCoordMap[`${x}`]) {
            xCoordMap[`${x}`].push({val, y});
        } else {
            xCoordMap[`${x}`] = [{val, y}];
        }
    }


    while (stack.length > 0) {

        const currNode = stack.pop();

        addNode(currNode.val, currNode.x, currNode.y);

        if (currNode.left) {
            stack.push({...currNode.left, x: currNode.x - 1, y: currNode.y - 1});
        }

        if (currNode.right) {
            stack.push({...currNode.right, x: currNode.x + 1, y: currNode.y - 1});
        }

    }

    // we have an object with numbered keys and arrays of values 
    const sortedKeys = Object.keys(xCoordMap).sort((a,b) => Number(a) - Number(b));
    const vertArrays = sortedKeys.map(key => {
       // sort the array then return it with only vals, not x and y 
       // sort by y first, then by value if y's are the same 
       xCoordMap[key].sort((a,b) => b.y - a.y).sort((a,b) => {
           if (a.y === b.y) return a.val - b.val;
           return 0;
       })
       return xCoordMap[key].map(obj => obj.val);
    });
    return vertArrays;
};

Discussion and Conclusions

I really focused on putting node data into a data structure and sorting it by the X value right when it is added. I felt that this is faster than any method which searches first and then sorts later. Especially because I am using a hash table to store the nodes with the same X value.

However, I could've done some more thinking on sorting the arrays of my node container by the Y value and node value upon adding, instead of before returning. I believe I could've done it in O(n) if I tried to put new nodes in the right spot when adding them, instead of the O(nlog(n)) sorting that I did to return the solution.

Leetcode Daily - Find all duplicates in an array

Andrew Hsu — Thu, 06 Aug 2020 17:42:51 +0000

Leetcode Daily - August 6, 2020

Find All Duplicates In An Array

Link to Leetcode Question

However, since many people post their own solutions in the discussions section of Leetcode, I won't necessarily be posting the optimal solution.

Question

(Copy Pasted From Leetcode)

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[2,3]

My Approach(es)

I won't go over all the code for all attempts but I will explain my approach(es) qualitatively.

Attempt 1 - store seen numbers in a hash table

(Submission - Accepted)

I thought about using techniques such as sorting the array, with time complexity of O(nlog(n)), but decided to utilize hash tables which take virtually O(1) to retrieve values if given a key.

Since we are looking for duplicates, we only need to traverse the array once (in O(n) time) and check if we have seen a number before. If we haven't seen it, we add it to our hash table. If we have seen it, we add it to an array holding numbers we've identified as duplicates. Then we can return the array of duplicates to complete the function.

Javascript:

var findDuplicates = function(nums) {
    // use a hash table to store numbers we've seen 
    let hash = {}

    // now go through the array once 
    let dupes = [] 

    for (let i = 0; i < nums.length; i++) {
        if (hash[nums[i].toString()]) {
            // if it is a duplicate, add it to dupes
            dupes.push(nums[i])
        } else {
            // if it is not a duplicate, add it to hash 
            hash[nums[i].toString()] = true 
        }
    }

    return dupes
};

Attempt 2 - try and not use extra space for O(n) solution

(Submission - Accepted)

I tried to take advantage of the fact that the numbers are only integers between 1 and the length of the array, N. Therefore, it can map one to one with the indices of the array unless there are duplicates.

For example, the number 1 belongs in index 0, so the number k belongs in index k - 1.

I first create a container to hold duplicates.
I then iterate through the array.
- If the number i is in index i-1, I leave it alone
- If the number i is not in index i-1:
- I check index i-1:
  - If index i-1 holds number i: this number i is a duplicate
  - If index i-1 doesn't hold number i, I swap the numbers so that i is now in index i-1
- After the swap I check the current index again using the same criteria. I continue to swap until current index either:
  - Holds the right number
  - Is a dupe because index i-1 holds i
- Finally, continue to next index and repeat i. and ii.

var findDuplicates = function(nums) {
    // try to match the numbers to index = nums[i]-1

    // now go through the array once 
    let dupes = [] 

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] !== i+1) {
            // is the number in the right place? 
            // for example: 1 belongs in index 0
            // if so, ignore. if not, try to place all 
            // numbers in a chain correctly

            // nums[i] belongs in index nums[i]-1
            // try to put it in index nums[i]-1 
            let newIndex = nums[i]-1
            if (nums[newIndex] === nums[i]) { 
                if (!dupes.includes(nums[i])) {
                   dupes.push(nums[i]) 
                }
            } else {
                let temp = nums[i]
                nums[i] = nums[newIndex]
                nums[newIndex] = temp 
                i --
            }
        } 
    }

    return dupes
};

I may not be allowed to store the duplicates in an extra array if I wanted to meet the challenge of using no extra storage space as well as having O(n) time complexity. However, I would iterate through the array again and splice out any numbers that were not in their assigned positions (number k would be in index k-1) then return the spliced array.

Discussion and Conclusions

Using hash tables (in the case of Javascript, Objects) to quickly access data is a powerful tool that I was first introduced to in the first problem I ever tried on Leetcode, Two Sums. By using the hash table instead of a nested iterative loop, we can frequently reduce O(n²) tasks to O(n).

I still need to think about how to do this problem without using extra space. I tried to use the fact that all numbers integers from 1 to the length of the array, N. My implementation spent time during the for loop (O(n) operation) to reassign values to where they would be, and swapping places with the number in the correct position if it's not a duplicate. I think this approach is still O(n) because there aren't an infinite numbers to swap, since you would stop swapping if the number were in the right position.

Leetcode Daily - Power of Four

Andrew Hsu — Wed, 05 Aug 2020 19:59:03 +0000

Leetcode Daily - August 4, 2020

Power of Four

Link to the Leetcode Question

However, since many people post their own solutions in the discussions section of Leetcode, I won't necessarily be posting the optimal solution.

Question

(Copy Pasted from Leetcode)

Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

Example 1:

Input: 16
Output: true

Example 2:

Input: 5
Output: false

Follow up: Could you solve it without loops/recursion?

My Approach(es)

I won't go over all the code for all attempts but I will explain my approach(es) qualitatively.

Attempt 1 - while loop

(Did not submit, only pseudocoded)

I believe most people understand how to iteratively solve this problem. The two possible ways to use the iterative method are:

Via multiplication

function isPowerOfFour(num) {
 let counter = 1 
 while (counter < num) {
   counter *= 4
   if (counter === num) return true 
 }
 return false 
}

Via division

function isPowerOfFour(num) {
 let counter = num
 while (counter > 1) {
   counter /= 4
   if (counter === 1) return true 
 }
 return false 
}

These methods are O(log(n)) because the number of iterations would basically be the power of 4 that the number is closest to.

Attempt 2 - Math.log

(Submission - Accepted)

For those that are not familiar with the logarithm mathematical function, please refer to my post about it, here.

Basically, if 4^N = num, then log4(num) = N.

We can also use the mathematical theorem that converts logarithms to a common basis:

logB(A) = logx(A) / logx(B)

where x is a common basis. We will simply use base 10 since most log functions are base 10.

By understanding that powers of 4 will only have log4(num) = N where N are whole numbers, we can write a very simple function:

function isPowerOfFour(num) {
    return Math.log(num)/Math.log(4) % 1 === 0
};

After submitting this solution I noticed the run time was a bit long, 140ms. I think it might be that Math.log uses an iterative method to calculate the log accurately but that's required for this solution so the method I found (discussed in the Conclusions Section could be a more computationally efficient alternative.

Discussion and Conclusions

I felt very satisfied with solution, but looked for other interesting solutions. Here is one that uses some programming knowledge as well as mathematical knowledge.

First of all, since the question is asking about a power of 4, which is a power of 2, it has a significant property in binary, which is that it is a one with all zeros to the right of it. Not only that, it must be an even number of zeros since the odd powers of 2, such as 8 = 2³, would have an odd number of zeros (3 zeros for the number 8).

This solution also takes advantage of the fact that the programmer can know the maximum size of the number in bits, which allows them to use a bit mask and therefore not have to write iteration in a higher level language.

Leetcode Daily - Add and Search Data Structure

Andrew Hsu — Wed, 05 Aug 2020 19:28:41 +0000

Leetcode Daily - August 5, 2020

Add and Search Data Structure

Link to the Leetcode Question

However, since many people post their own solutions in the discussions section of Leetcode, I won't necessarily be posting the optimal solution.

Question

(Copy Pasted From Leetcode)

Design a data structure that supports the following two operations:

void addWord(word)
bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

Example:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

Note:
You may assume that all words are consist of lowercase letters a-z.

My Approach(es)

I won't go over all the code for all attempts but I will explain my approach(es) qualitatively.

Attempt 1 - Store words in an array

(Submission - Time Exceeded)

I added wordList Array to the WordDictionary class. Then the add method simply pushes the word to the Array. I even checked if the Array already included the word to make sure I didn't have duplicates.

This made the search method pretty challenging. If an exact word is given, I could simply use Array.includes. But for optional letters indicated by the '.', I had to first iterate through an array then iterate through the letters of the word. There is probably a smarter way to do this, for example, with regex, but I ended up getting 'time exceeded' on my submission.

Attempt 2 - Changing data structure to a Hash table

(Submission - Accepted)

Since Hash tables are virtually O(1) for data retrieval I decided I would stop using the Array and use a Hash table.

However, simply using the word as the key would not make it any easier to retrieve words that had to match optional letters, '.'. I decided to refactor my data structure to make searching easier, but adding would be slightly harder.

My data structure is a hash table that has the following key value pairs:

key - length of word (maybe prepended with 'len' or another string)
value - Array of words

My add function checks if the key named len${word.length} exists, and if it does, it pushes the word to the Array held by that key. If the key does not exist, it is created with the value [word].

My search function checks if the key named len${word.length} exists, and if it does then it iterates through the array and tries to match the letters of the searched word. This is actually very similar to the original array implementation, but the array searched is potentially much smaller, unless all or most of the words in the dictionary are the same length.

This ended up being my accepted submission.

Discussion and Conclusion

I still have to do some studying on the optimal implementation of this problem. I feel that if I designed a better data structure then perhaps there could be a more efficient search algorithm. But of course, there could potentially be added complexity to the add algorithm.

In my current solution, add should still be O(1) if you ignore any complexities of using the Array.push method. And, search should still be O(n), because even though we broke down our storage data structure by word length, the amount of words stored and therefore the iterative search time still grows proportionally to the number of words added.

Simple Introduction to Logarithms for Complexity Analysis

Andrew Hsu — Wed, 27 May 2020 18:41:24 +0000

Simple Introduction to Logarithms for Complexity Analysis

Introduction
What is it?
How it Relates to Complexity Analysis
Example: Binary Search
Conclusion

Introduction

I just wanted to write this post to help introduce (very SIMPLY) the concept of logarithms, especially because many programmers do not come from a math background. This post is not meant to get into all the possible things logarithms are good for, but just to understand what it IS and show how it is relevant in an algorithm's time (and space) complexity analysis.

What is it?

Let's start from the basics. To introduce logarithms, we need to first introduce the idea of exponents, or a number to a certain 'power'.

For example:

2⁵ = 32

The superscript (smaller, higher up number) indicates the number of times you multiply the base number (regular font and position number) with itself. Therefore, we can calculate 2 x 2 x 2 x 2 x 2 = 32.

This can be useful for many things, such as for determining how much information can be stored digitally (see bits for an introduction) or in computing compounding interest in finance.

But just as we can build up the product of 2's, we may also want to know how many times we multiplied 2 together. For example, we already know that 32 is 2 multiplied together 5 times.

We use the following notation for the logarithm:

log2(32) = 5

The subscript (smaller, lower number) is the base, which is still 2 in this example. The number we want to take the logarithm of is 32 (we want to find out how many times 2 multiplied together to get this number). The result is 5 because we started with this example, so we already know the answer.

Exponentiation and logarithms are actually inverse functions. Assuming both operations use the same base value (2, or the number being multiplied), exponentiation takes a number and multiplies the base that many number of times. Logarithms, starting with that final number, find out how many times it was multiplied (the exponent).

This means that we can feed our exponential into a logarithm and get the exponent used.

log2(2^x) = x

Basically, the logarithm should be thought of as the exponent detector or calculator. (Assuming we start with the same base; very important!)

Notes

A couple of notes about logarithms before we continue:

Most of the time, we just see 'log', such as on a calculator. This is most likely log10, which is base 10.
Logarithms have properties that allow conversion between different bases: Formula to convert logarithm bases. This is really useful if you need to calculate log in a different base but only have a log (base 10) function (in your programming language or on a calculator).
Sometimes you may see 'ln' or natural log. This is a logarithm in base e, or Euler's number. This is usually irrelevant for programmers and developers unless you are working with something related to mathematics but now you know what the ln button is on a graphing calculator.

How it Relates to Complexity Analysis

Bored yet?

Let's get to something more relevant. We know that there are many different ways algorithms can scale in time (and space) complexity, such as O(n), O(n²), O(nlog(n)), etc.

You may have seen a graph (with two curves) like the one below:

I created this graph using GeoGebra Graphing Calculator, a site where you can draw graphs using math formulae.

These curves may already be familiar with you. The higher, puke green curve that increases to infinity is 2^x. The lower, dark teal curve is log2(x). In both cases, x is simply the value on the horizontal axis of the graph.

Because exponentiation and logarithms are inverse functions, and we are using base 2 for both curves, we can observe a symmetry along the a diagonal line (whose slope is 1).

From what we know about complexity analysis and big O notation, the exponential curve is really bad (increases towards infinity very fast) while the logarithm is very good (the slope tends to descend rather than ascend like the exponential).

Now that we know what the logarithm is, and why it has that descending (but not fully reaching horizontal) slope, let's take a look at a case where we find logarithms in commonly seen algorithms.

Example: Binary Search

You may have seen binary search already but here is a summary:

Let's say you are given a sorted array of integers (ascending order). One way to find if a target value is held in the array is to look through every array index in order. But a more efficient way (especially for longer arrays) is to use binary search.
If the array is sorted, you can check if the median index holds the target value. But if the median index's value is lower than the target, you know that you only need to search the upper half of the array. Similarly, if the median index's value is higher, you only need to search the lower half.
This can be repeated until base cases are reached, such as when the sub-array being searched is only a length of 1.

I won't discuss how to solve or implement binary search in any more detail here. I want to use the binary search algorithm to show how we can determine that (spoiler alert!) the time complexity is O(log(n)) where n is the length of the array being sorted.

Let's use our trusty number 32 from the previous section. We already know that this is 2⁵. We also know that when we implement binary search, we keep finding the median index (or the midpoint) between our starting and ending indices. This is because we want to rule out half of the search area each time (if we know the target is higher or lower, we know which side NOT to search).

Since dividing by 2 is the inverse of multiplying by 2, this plays into our hands because exponentiation is simply multiplying a bunch of times. If our input array has 32 numbers to look through, we don't want to look through all 32.

Let's see what we are actually binary searching through if we have an array of length 32 (indices 0 - 31).

Iteration 1:
- We check index 15 (average of 31 and 0 is 15.5, and we take the floor).
- If our target number is found on array[15], we can return out of the function. Else, we binary search the upper or lower half of the array.
Iteration 2:
- Since the sub-array is only length 16, we can take the median of 0 and 15, which is 7 (floor of 7.5).
- If target found, return. Else, binary search an array of length 8.
Iteration 3:
- Array length 8
Iteration 4:
- Array length 4
Iteration 5:
- Array length 2
Iteration 6:
- Array length 1

"6 iterations!" you may say, thinking that I am actually not that great at math. But when you think about the powers of 2 and its correlation to the sub-array lengths, you will see that 1 is actually 2⁰. And counting 0-5 actually gives you 6 items.

Additionally, the exact amount isn't the most important thing in complexity analysis, but rather the scaling factor as the size of data increases. For example, 2¹⁰ is 1024. If you had an array of around 1000 numbers, your binary search would probably take 11 iterations in the worst case (0-10 is 11 items). But when you start comparing 11 iterations to the 1000 iterations an O(n) linear algorithm would take, the benefits start to become apparent.

Also, even though most numbers are not exactly divisible by 2, as long as you are roughly dividing the array in half all the smaller pieces are either ignored (we know the target isn't in a certain half of the array) or break down to arrays of length 2 and 1 anyway. So the performance would be comparable to the next power of 2 not lower than the array length.

Conclusion

While not every programmer needs to know a ton of math, logarithms are seen frequently enough that I feel it should be introduced. They have many mathematical properties but most are not necessary to memorize for a programmer.

The behavior of logarithms, however, is important to understand in algorithms and their complexity analysis because the potential improvements in algorithm performance are so great, and can be thought of as low hanging fruit in many cases, such as for well known divide and conquer algorithms.

DEV Community: Andrew Hsu

Leetcode Daily - Sum of Left Leaves

Leetcode Daily - August 24, 2020

Sum of Left Leaves

Question

My Approach(es)

Attempt 1 - DFS

(Submission - Accepted)

Discussion and Conclusions

Leetcode Daily - Longest Palindrome

Leetcode Daily - August 14, 2020

Longest Palindrome

Question

My Approach(es)

Attempt 1 - Determine Logical Conditions For Longest Palindrome Length

(Submission - Accepted)

Discussion and Conclusions

Leetcode Daily - Iterator for Combinator

Leetcode Daily - August 13, 2020

Iterator for Combinator

Question

My Approach(es)

Attempt 1 - DFS or BFS

(Submission - Accepted)

Discussion and Conclusions

Leetcode Daily - H-Index

Leetcode Daily - August 11, 2020

H-index

Question

My Approach(es)

Attempt 1 - Check Possible H-Index Values

(Submission - Accepted)

Attempt 2 - Remove one iterative loop from O(n2) solution

(Submission - Accepted)

Discussion and Conclusions

Leetcode Daily - Excel Sheet Column Number

Leetcode Daily - August 10, 2020

Excel Sheet Column Number

Question

My Approach(es)

Attempt 1 - Treat the string as a base 26 number

(Submission - Accepted)

Attempt 1A - Still Treating the string as a base 26 number

(Submission - Accepted)

Discussion and Conclusions

Leetcode Daily - Rotting Oranges

Leetcode Daily - August 9, 2020

Rotting Oranges

Question

My Approach(es)

Attempt 1 - Brute Force (iterate out the grids)

(Submission - Accepted)

Discussion and Conclusions

Leetcode Daily - Path Sum III

Leetcode Daily - August 8, 2020

Path Sum III

Question

My Approach(es)

Attempt 1 - DFS or BFS

(Submission - Accepted)

Discussion and Conclusions

Leetcode Daily - Vertical Order Traversal Of Binary Tree

Leetcode Daily - August 7, 2020

Vertical Order Traversal Of Binary Tree

Question

My Approach(es)

Attempt 1 - DFS or BFS

(Submission - Accepted)

Discussion and Conclusions

Leetcode Daily - Find all duplicates in an array

Leetcode Daily - August 6, 2020

Find All Duplicates In An Array

Question

My Approach(es)

Attempt 1 - store seen numbers in a hash table

(Submission - Accepted)

Attempt 2 - try and not use extra space for O(n) solution

(Submission - Accepted)

Discussion and Conclusions

Leetcode Daily - Power of Four

Attempt 2 - Remove one iterative loop from O(n²) solution