May LeetCoding Challenge - Week 1

As a complement to my education, I've been participating in the May Leetcoding Challenge over at leetcode to improve on my problem solving skills as well as understanding of data structures and algorithms. I've decided to write this article on each problem, a high level method of how my initial solution was and how my solution differed from the optimal solution.

In writing this, I'm hoping to both reinforce my own learning and inspire others who might be like me, feeling the need to improve and increase my "toolbox" of solutions, especially when seeing how hard technical interviews can get in some of the best companies in the world. Feel free to correct me if I've gotten any points wrong, I'd love to learn how I can do better! The solutions use the C++ STL.

May 1st

First Bad Version

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

My initial kneejerk solution to this was a brute force algorithm, starting from 1 all the way to n. However, given the question condition here "You should minimize the number of calls to the API", I knew there had to be a better way than an O(n) time complexity solution.

The solution I decided on was a binary search algorithm. The problem here is that the binary search algorithm that I had always implemented searched for a single unique number in a list. If I were to implement the binary search that I knew of, this meant a wrong answer as I would return once isBadVersion was true. Therefore, I would need to modify the binary search algorithm to search for the point at which isBadVersion(i) is true and isBadVersion(i-1) is false.

After some time of building a solution using trace tables and test cases, I came up with the following pseudocode.

declare low = 1
declare high = N

while low < high
    mid = (low + high) / 2
    if isBadVersion(mid)
        high = mid
  else
    low = mid + 1
return low

However, it was still failing certain test cases. Thankfully, the error given by leetcode was enough to point out the problem with the code: Integer overflow.

With a bit of revision of the above code. I was able to pass with a O(log N) time complexity with O(1) space complexity and complete Day 1. This solution was consistent with most of the fastest running solutions.

May 2nd

Jewels and Stones

You're given strings J representing the types of stones that are jewels, and S representing the stones you have. Each character in S is a type of stone you have. You want to know how many of the stones you have are also jewels.

The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so "a" is considered a different type of stone from "A".

Note:

• S and J will consist of letters and have length at most 50.
• The characters in J are distinct.

The initial thought here was that for each stone in S, I could search J for jewel and increment a counter if it is a jewel. This would end up being a O(S*J) time complexity solution with O(1) space complexity. However given a bit of further thinking I ended up using a solution with unordered_set, in which most operations are O(1), making a O(S + J) time complexity with O(J) space complexity.

At a high level, I ended up with this pseudocode.

declare unordered_set jewels
declare int count = 0
LOOP J
    insert J in jewels

LOOP S
    if s in J
        add 1 to count

return count

Using this, it was enough to pass the submission! However, I learned the solution could still have been found with the same time complexity without the use of unordered_set. Given all characters in J and S are letters, this means all I need is an array of size 57 ('z' - 'A').

May 3rd

Ransom Note

Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.

Each letter in the magazine string can only be used once in your ransom note.

Constraints:

• You may assume that both strings contain only lowercase letters.

Given May 2nd's question and the constraints, the immediate thought was to use an array of size 26 to store the count of all characters in magazine M, then decrement for each character in the ransom note N. If the count goes below 0 then canConstruct would be false.

declare int[26] chars;

loop m in M
    increment chars[m - 'a']

loop n in N
    decrement chars[n - 'a']
    if chars[n - 'a'] < 0
        return false

return true

This solution passed, but it wasn't the most optimal solution because there are two checks that could be done without ever having to go into the loops. If there was no ransom note, then it would definitely be true. If there was more characters in the ransom note than in the magazine, then it would definitely be false.

Therefore, there may be cases where loops wouldn't be needed.

May 4th

Number Complement

Given a positive integer num, output its complement number. The complement strategy is to flip the bits of its binary representation.

Constraints:

• The given integer num is guaranteed to fit within the range of a 32-bit signed integer.
• num >= 1
• You could assume no leading zero bit in the integer’s binary representation.

First thought, given they want a binary representation, this attempt should use bitwise operators. Given the way a complement is found e.g. the binary complement of 1001 is 0110, then every bit after the first bit corresponds to a power of 2. Therefore my solution after many, many attempts, I ended up with something like this.

declare sum = 0
declare pow = 1

LOOP num > 0
    if bitwise and of num and 1 == 0
        add pow to sum
  right shift num by 1
  multiply pow by 2

return sum

I found this question pretty hard because I was unfamiliar with bitwise operators and don't use them very often, so I had heavy usage of trace tables to understand how each operator might occur in order to build this solution, so it was satisfying to have a solution that eventually passed. However, the smart solutions also showed that I had a lot to learn here with how to utilize the full range of bitwise operators. My solution ended up with a time complexity of O(n) where n is the number of bits in that number and O(1) space complexity.

Without spoiling, I did end up finding out that the solution could be found with a loop and a single bitwise XOR which only served to motivate me to learn more to close that gulf.

May 5th

First Unique Character in a String

Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.

Note: You may assume the string contain only lowercase letters.

This question was a variation of the questions from May 2nd and May 3rd, so I won't go into too much detail. Given the note, I used an int array of size 26 and looped through the string twice for a solution with O(N) time complexity and O(N) space complexity.

May 6th

Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Given the question, my solution defaulted to using unordered_map (Internally a HashTable) since I found the question similar to the previous days, however there were key differences I missed out by defaulting to what I knew.

Using an unordered_map gave me a solution with O(n) space and O(n) time complexity, however there were various other solutions, with the fastest and most memory efficient being the Bayer-Moore voting algorithm which would be O(n) time and O(1) space.

May 7th

Cousins in Binary Tree

In a binary tree, the root node is at depth 0, and children of each depth k node are at depth k+1.

Two nodes of a binary tree are cousins if they have the same depth, but have different parents.

We are given the root of a binary tree with unique values, and the values x and y of two different nodes in the tree.

Return true if and only if the nodes corresponding to the values x and y are cousins.

Note:

• The number of nodes in the tree will be between 2 and 100.
• Each node has a unique integer value from 1 to 100.

Armed with my learnings from the past week, it seems as though leetcode had also wanted to test participants with a problem of Graph Theory. I had only previously implemented the Depth-First Search (DFS) algorithm before, so this was a question that I was unfamiliar with, and I found it fairly challenging. I knew of the existence of the Breadth-First Search (BFS), but had not implemented and read on it yet, so there was no better time than now to further learn about it.

In addition to this, the problem threw in the added challenging of managing depth in the BFS so I spent a significant amount of time on this.

At a high level, I ended up with this solution

FUNC foundVal
    if val equal to x or y and parent node is null
        set parent to parent of current node
    else if parent is set
        if parent of current node is equal to parent
            return false
        else
            return true

FUNC main
    declare level, levelSize, queue and parent

    if root node equal to x or y
        return false

    push root to queue

    LOOP
        set levelSize to size of queue
            LOOP levelSize greater than 0
                if left node exists
                    check if value is found
                    add left node to queue
        if right node exists
            check if value is found
            add right node to queue
        decrement levelSize
    if parent is not null
        return false
    increment level

Given the solution, it has a general time complexity of O(n) and a space complexity of O(n) where n is the number of nodes.

I found talking through the solution helped, as well as figuring out on what cases this function would terminate. By breaking down the problem into parts, it became something that was manageable instead of a mountain to climb.

Overall Learning Points

• Consider the general cases, then consider the edge cases.
• The most familiar solution might not necessarily be the best solution.
• Break the problem down into parts and it'll be more manageable.
• Especially for the question on May 6, can't use a solution that I don't know exists.