DEV Community: vickdayaram

LeetCode 10. Regular Expression Matching, Dynamic Programming Edition

vickdayaram — Sun, 01 May 2022 00:00:00 +0000

Solving LeetCode 10, Regular Expression Matching with Dynamic Programming. Click here and try it out your self!

To get the most out of this post I recommend you read my original post that covers the analysis and the recursive solution. We will use that analysis and focus on how we can implement a solution using Dynamic Programming.

LeetCode Problem Statement

Given an input string s and a pattern p, implement regular expression matching with support for ’.’ and ’*’ where:

’.’ Matches any single character. ’*’ Matches zero or more of the preceding element. The matching should cover the entire input string (not partial).

Examples:

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Input: s = "aa", p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

Breaking it down

Lets understand how we can apply Dynamic Programming to solve this problem. If you are not familiar with Dynamic Programming at all, I’d recommend that you learn the basics first before diving into this post.

Analysis Recap

When we have an exact match, move on to the next character. An exact match can happen in two ways:

Characters match exactly
Pattern contains a ”.”

If the next character ahead is a ”*” we have to asses the remainder of the string in one of two ways:

Match zero characters of the preceding character in the pattern
Match one or more characters of the preceding character in the pattern

Applying Dynamic Programming

Dynamic Programming is described as solving a problem bottom up. The core strategy is as follows:

Identify your base cases (Solutions for small sub problems that you already know)
Build solutions for small sub problems from base cases
Use the previous solutions to build solutions for more complex cases, and so on

This will become more clear as we get into the implementation of the algorithm.

To keep track of all of these sub problems we will use a matrix. We’ll refer to this as our DP table. Using a matrix is fairly common in Dynamic Programming although other data structures could be used as well.

Example one

Structuring our DP Table

To structure our table we need to answer the following:

What are our base cases? They will be the following:

Empty Pattern, Empty String
Empty Pattern
Empty String

What kind of values will our table store? We can build a table of boolean values. If the sub string and sub pattern match, we can tag it with True, otherwise False

As we iterate through we will be referencing our table for solutions to previous sub problems. We will use those solutions to solve our current problems, and use solutions to current problems to solve the next problems, and so on. Working in a bottom up fashion!

With that in mind, this is what our table would look like:

Important Note: I chose to place the pattern on the X axis and the string in the Y axis. You can orient the table however you want, but be mindful of how you orient your inputs since it will affect how you search your table.

Populating our base cases

Before iterating through and solving for sub problems we need to initialize our table with the solutions to our base cases. These cases represent the small sub problems that we already know the answer to. Just like in a recursive algorithm, dynamic programming will build our solution based on these sub problems.

Base Case 1: Empty String, Empty Pattern

If we have an empty string and an empty pattern, that should evaluate to true. Which would look like this:

Base Case 2: Empty Pattern

If we have an empty pattern, and a non empty string, that would look like this:

Base Case 3: Empty String

If we have an empty string, and a non empty pattern, that would look like this:

Iterating through

Once our table is set up, we can start to iterate through and populate the rest of our table. Once we are done, our answer should exist in dp[s.length][p.length].

For Dynamic Programming problems, I find it incredibly helpful to have your core logic written out ahead of time. This way as you are manually stepping through you can validate it, and make adjustments if necessary.

With that said, our core logic should look like this:

DP solutions can be very unreadable sometimes when everything is being read directly from the table. I’ve added variables here to help with that. This makes things a bit more verbose but I hope that it makes it clearer.

You should be able to come up with the core logic from the initial analysis of the problem. The challenging part will be figuring out where to look in the table. If you are still getting used to Dynamic Programming like I am, the best way to understand where to look is to work out a few problems. In this case I have done that ahead of time.

Lets start looping through:

i = 1
j = 1

sChar = s[i - 1] // a
pchar = p[j - 1] // a

Notice how we are looking at the previous character. This makes things a bit more convenient to populate our table. This is because our table is taking into account the base cases which adds a character to the string and the pattern respectively.

Ok, so we have a match! Lets check our DPTable to check the solution to the previous sub problem.

As we can see in this case, we have hit our base case, Empty String, Empty Pattern. So we can tag this cell with True.

After the update our table would look like this:

Nice!

Moving on to the next iteration

Since we don’t have any more characters in the pattern, we would move on to

i = 2
p = 1

This is what it would look like from the table perspective:

s[i - 1] === p[j - 1] ? 
"a" === "a" ?

We have a match! Lets check our DPTable to check the solution to the previous sub problem.

Our DPTable indicates that our previous sub problem was not solved successfully. We hit our base case 2(Empty Pattern). So we would tag this cell with False.

At this point we would break out from our loops, since i == 3. Our answer will exist in dp[s.length][p.length] and as we can see it’s False as we expected.

Nice!

Example Two

Ok, working through example two, we should learn how to handle the ”*” character. Lets get started by building our table with our base cases:

Populating our base cases

Base Case 1: Empty Pattern, and Empty String

Base Case 2: Empty String

How does an empty string match with a single ”*” pattern?

Remembering the definition of ”*”, we can match zero or more of the preceding character. Since our base case is an empty string it eliminates the option of matching one or more of the preceding character. That leaves us with matching zero characters. To do that we would look at the value in dp[i][j - 2] which is our base case (Empty String, Empty Pattern). So we would tag this cell with True.

We will have to remember to add this logic when building our base cases

It’s easy to get tripped up on this piece, I sure did! Let’s dive a little deeper to make sure that this makes sense by looking at an example.

The pattern “a*” is looking to match strings that:

Have one or more “a”s
Have zero “a”s

Empty strings, have zero “a”s. So this checks out.

Tip: Dive deeper when you get tripped up. Understanding the details will set you up for success. Brushing over them could leave you blind sided in the next steps!

Base Case 3: Empty Pattern

Nice, table is ready!

Iteration One

Starting point will be:

i = 1
j = 1 

s[i - 1] === p[j - 1] ? 
"a" === "a"

We have a match. Lets check our DPTable to check the solution to the previous sub problem.

As we can see we hit our base case 1 (Empty String, Empty Pattern). We can tag this cell with True.

Iteration Two

i = 1
j = 2

s[i - 1] === p[j - 1] ? 
"a" === "*"

Our first star case! Lets check our DPTable to check the solution to the previous sub problem.

In this case we can see that matchZero hits our base case 2 (Empty Pattern), which is not a successful solution.

Since previousCharMatch is true, we can explore matchingOneOrMore which was solved successfully. So we can tag with cell with True.

Iteration Three

i = 2
j = 1

s[i - 1] === p[j - 1] ? 
"a" === "a"

We have a match. Lets check our DPTable to check the solution to the previous sub problem.

We would tag this cell with False since we hit base case 3 (Empty Pattern).

Iteration Four

i = 2
j = 2

s[i - 1] === p[j - 1] ? 
"a" === "*"

”*” Pattern again! Lets check our DPTable to check the solution to the previous sub problem.

Just like Iteration Two:

We can see that matchZero hits our base case 2 (Empty Pattern), which is not a successful solution.

Since previousCharMatch is true, we can explore matchingOneOrMore which was solved successfully. So we can tag with cell with True.

Final Table

Our final table will look like:

Our answer will be in dp[s.length][p.length], and as we can see it’s True as expected.

Nice!

Example 3

I’ll leave it to you to work out example three. You should follow the same pattern we did in the previous two examples. The new character you will have to account for is ”.” which matches any single character once.

The best way to do this is to have the core logic available, and step through populating the table cell by cell. This is precisely what our algorithm will do. A solid understanding of this process will make implementing the algorithm a breeze!

The Algorithm Plan

Solve with Dynamic Programming

Create DP table. Matrix of s.length + 1 by p.length + 1. Initialize with false values.
Populate base cases
- Empty String, Empty Pattern
- Empty String
- Empty Pattern
Write nested for loop
- Outer loop starting from 1 <= s.length
- Inner loop starting from 1 <= p.length
- In each iteration
  - If we have match
  - Check the previous string so far at dp[i - 1][j - 1]
  - If the previous is True, tag this cell as True
  - If we have a ”*”
  - MatchZero: dp[i][j - 2]
  - If PreviousMatchChar
    - MatchZero or MatchOneOrMore: dp[i - 1][j]
  - If either of these is True tag the cell as True. Otherwise False
Once you break from the loop return dp[s.length][p.length] for the solution

Code


const array = (n) => { return Array(n).fill(false); }

const isMatch = (s, p) => {

    // Adding one to account for base cases
    const dp = array(s.length + 1).map(() => array(p.length + 1));

    // Base cases
    // Empty String Empty Pattern
    dp[0][0] = true;

    // Empty String
    for(let i = 1; i <= p.length; i++) {
        let pChar = p[i - 1];
        if (pChar === "*") {
            dp[0][i] = dp[0][i - 2];
        }
    }

    // Empty Pattern
    // We handle this by pre populating our matrix with false values

    // Iteration
    for(let i = 1; i <= s.length; i++) {
        for(let j = 1; j <= p.length; j++) {
            let sChar = s[i - 1];
            let pChar = p[j - 1];
            let stringMatchSoFar = dp[i - 1][j - 1];
            let currentMatch = sChar === pChar || pChar === ".";
            if (currentMatch) {
                dp[i][j] = stringMatchSoFar;
            }

            if (pChar === '*') {
                let matchZero = dp[i][j - 2];
                let previousMatch = sChar === p[j - 2] || p[j - 2] === ".";
                let matchOneOrMore = dp[i - 1][j];
                dp[i][j] = matchZero || (previousMatch && matchOneOrMore);
            }
        }
    }

    return dp[s.length][p.length];
}

Summary

The time complexity of this algorithm is O(S * P) where S is the length of the string and P is the length of the pattern. The space complexity will be O(S * P) since we are storing solutions to sub problems in a matrix. Although Dynamic Programming solutions can be hard to think about the time complexity analysis is quite simple as you can see.

Key takeaways:

Lay out your core logic ahead of time
Build your DP table manually by stepping through the problem and test your core logic
Make adjustments to your core logic as needed as you step through

Once your core logic is solid, the rest of the implementation is fairly trivial as you can see.

Hope you found this helpful!

LeetCode 10. Regular Expression Matching

vickdayaram — Sun, 03 Apr 2022 00:00:00 +0000

Solving LeetCode 10, Regular Expression Matching. Click here and try it out your self!

LeetCode Problem Statement

Given an input string s and a pattern p, implement regular expression matching with support for ’.’ and ’*’ where:

’.’ Matches any single character. ’*’ Matches zero or more of the preceding element. The matching should cover the entire input string (not partial).

Examples:

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Input: s = "aa", p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

Initial Thoughts

Hard problem… What pattern can we apply to solve this?

Breaking it down

Lets start breaking this down piece by piece, and looking at the examples.

Example 1:

How can we approach this? We can iterate through and compare the characters. If they are equal, we can compare the next set of characters and so on.

In this example, we run out of characters for the pattern but still have characters in the string. This scenario indicates we don’t have a match. This is the case because we are looking for a full match, not partial.

Takeaway

Once we reach the end of the pattern, we can check the length of the remaining string. If it equals zero, we have a match. Otherwise, we do not.

Example 2:

Handling ”*”

After walking through this example we should understand how to handle the case with ”*” in the pattern.

Definition of ”*”: Matches zero or more of the preceding character in the pattern.

Reading the definition tells us we can match in two ways.

We can have zero occurrences of the preceding character in the pattern
We can have one or more occurrences of the preceding character in the pattern

The solution could exist in option one, or option two. We would have to explore both to know for sure.

Note: Whenever we run into problems where we need to explore multiple paths, recursion can be an effective tool. Uncovering this indicates that we could use recursion to solve this, and that’s what we will be doing. If you are not familiar with recursion, I’d recommend to learn the pattern first and then come back to this post.

Stepping through the example

With recursion in mind, lets work through the example:

We can compare the first characters and see that they are equal.

To identify if we have the ”*” we have to look ahead to the next character in “p”. If it’s a ”*” we need to handle both our options.

Handling The First Case (Level 1)

Case one : Zero occurrences

Action : Ignore the characters in “p” and skip ahead

Since we have reached the end of the pattern, but not the string, we would return false

Handling The Second Case (Level 1)

Case two : One or more occurrences of the preceding character

Action : Move on to check the next character in “s”

Once we get here, we would compare the characters again. Since they match, and the next character in p is ”*”, we would explore our two cases again.

Handling The First Case (Level 2)

Case one : Zero occurrences

Action : Ignore the characters in “p” and skip ahead

We would jump ahead in “p”, but we would still have characters left in “s”. So this would evaluate to false.

Handling The Second Case (Level 2)

Case two : One or more occurrences of the preceding character

Action : Move on to check the next character in “s”

We would jump ahead in “s” and reach the end of “s”. We would still have characters in “p” however. So, once again, we would check the next character in “p”, identify the ”*” case, and explore the two cases. Deeper in the stack we go!

Handling The First Case (Level 3)

Case one : Zero occurrences

Action : Ignore the characters in “p” and skip ahead

This time, we have reached the end of both strings, which means that we have a match, and would evaluate to true.

Handling The Second Case (Level 3)

Case two : One or more occurrences of the preceding character

Action : Move on to check the next character in “s”

Here we would move ahead in s, and be out of bounds. Since there is no character to compare here we would return false.

Note: We are exploring this case for completeness, but depending on how we implement our algorithm we could just stop exploring once we find a true case.

Takeaway

Recursion will be a good approach to solve this since we have to explore two possible paths.

Example 3

For this example we have ”.” This character indicates that we can match any character. In this case it’s followed by the ”*” so we would apply the cases we learned in the last example as well.

Handling The First Case (Level 1)

Case one : Zero occurrences

Action : Ignore the characters in “p” and skip ahead

In this case we would run out of characters in “p”, but we would still have characters in “s”. So this case would evaluate to false

Handling The Second Case (Level 1)

Case two : One or more occurrences of the preceding character

Action : Move on to check the next character in “s”

Since ”.” can equal any character, we would move ahead to the next character in “s”. From there we would evaluate our two cases again.

Handling The First Case (Level 2)

Case one : Zero occurrences

Action : Ignore the characters in “p” and skip ahead

Like before, this would evaluate to false since we have ran out of characters in “p”.

Handling The Second Case (Level 2)

Case two : One or more occurrences of the preceding character

Action : Move on to check the next character in “s”

This case looks familiar from the previous example. We would move one character ahead in “s” since ”.” matches any character. Once we get here, we can see that we will eventually evaluate to true, by exploring case number one: zero occurrences of the preceding character in the next level of the stack.

Nice! Stepping through these examples have helped us understand the cases we will have to handle. Now that we have a good understanding of the problem, lets lay our thoughts out so we can code it up.

The Algorithm Plan

Like we uncovered we will be using a recursive approach to solve the problem. With that in mind, lets identify our base cases

Bases Cases:

If we reach the end of “p” and the end of “s” we have a match
Evaluate firstMatch: Check if the first characters in “s” and “p” equal
Check if the next character in “p” is a ”*”, if so:
- Return
- Case one: call the function by moving “p” ahead by two characters
- OR
- Case two: firstMatch AND call the function by moving “s” ahead by one character
Return
- firstMatch
- AND
- call the function by moving “s” up on character and “p” up one character

Code


const isMatch = (s, p, sIdx = 0, pIdx = 0) => {
    if (p.length === pIdx) {
        return s.length === sIdx;
    }

    const firstMatch = sIdx < s.length && (s[sIdx] === p[pIdx] || p[pIdx] === ".");

    if ((pIdx + 1) < p.length && p[pIdx + 1] === "*") {
        return (
            isMatch(s, p, sIdx, pIdx + 2) // Case One
            || firstMatch && isMatch(s, p, sIdx + 1, pIdx) // Case Two
        )
    }

    return firstMatch && isMatch(s, p, sIdx + 1, pIdx + 1);
}

Summary

In the worst case, this algorithm runs in O((S + P) * 2^S + P/2), where S and P are the lengths of “s” and “p” respectively. This time complexity is very challenging to pin down. I’d recommend this blog post for a deep dive.

Working through this problem recursively is helpful to understand what is involved in figuring out the solution. However, the optimal solution to this problem can be achieved with Dynamic Programming. The Dynamic Programming solution to this problem will run in O(S * P), which is much faster.

If you are not familiar with Dynamic Programming it can be hard to wrap your head around at first. However, once you understand how to apply the pattern, it can help you come up with performant solutions with minimal code. It’s a very powerful pattern.

I’d challenge you to take what we have learned and try to solve this problem with Dynamic Programming. I’ll challenge my self with that too!

Hope this was helpful!

LeetCode 102. Binary Tree Level Order Traversal

vickdayaram — Sun, 20 Mar 2022 00:00:00 +0000

Solving LeetCode 102. Binary Tree Level Order Traversal. Click here and try it out your self!

LeetCode Problem Statement

Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).

Example:

Example 1 Image:

Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Example 2:
Input: root = [1]
Output: [[1]]

Example 3: 
Input: root = []
Output: []

Initial Thoughts

Breadth First Search!

Breaking it down

We can use BFS to traverse the tree and collect all the nodes for a given level in a currentLevel array. We can store each of our currentLevel arrays in an results array. Once we finish our traversal our solution should be contained in results.

If your not familiar with how to implement BFS, continue to read on here. We’ll describe BFS implementation as it relates to this problem. If you are familiar feel free to skip.

Implementing BFS

We can use a queue, while loop, and for loop to implement BFS. Typically a queue and a while loop are required, however the for loop is optional depending on the problem. Also, remember this is just one way to do this.

To kick things off we will initialize a queue with the root node. We will continue to iterate through the queue while it’s not empty.

As we iterate in our while loop we will capture the current length of the queue. This length represents the number of nodes at the current level. Looking at our example, for the first iteration currentLength will equal one. The next time it will equal two, and the last iteration it will equal two again. This will become more clear as we continue to work through the problem.

Storing currentLength is critical here. That’s the information that lets us know the bounds of each level so we can operate on nodes on a level by level fashion.

Important Note. Make sure to save currentLevel as a variable, and don’t use queue.length. As you will see we are always adding child nodes to the queue so the length will change.

Every node we grab in the for loop will belong to the currentLevel. For this problem we are asked to collect each level and return it in an array. So every time we shift() from our queue, we can push the value to the currentLevel.

To collect the next level, we will check if the current node has children. If it does, we will push them to the queue.

Once the iteration finishes, our queue should have the next level and our result should have the first level.

Following these steps, we will collect all the levels! Nice.

The Algorithm Plan

Approach Overview

If there is no root, return []
Initialize a queue with the root node
Initialize a results array
While the queue is not empty
- Initialize a currentLevel array
- Capture the currentLength of the queue
- Declare a for loop, and iterate through the queue from 0 to the currentLength
- Shift() from the queue
- If node.left, push node.left to the queue
- If node.right, push node.right to the queue
- push node.val to the currentLevel
- push currentLevel to results
Return results

Code


const levelOrder = (root) => {

    if (!root) return []

    const results = [];
    const queue = [root];

    while (queue.length > 0) {
        const currentLength = queue.length;
        const currentLevel = [];

        for(let i = 0; i < currentLength; i++) {
            const node = queue.shift();
            if (node.left) {
                queue.push(node.left);
            }
            if (node.right) {
                queue.push(node.right);
            }
            currentLevel.push(node.val);
        }

        results.push(currentLevel);
    }

    return results;
}

Summary

The time complexity of this Algorithm is O(N) since we are visiting every node in the tree. The space complexity will be O(N) + O(K), where K is the level with the most nodes. This represents the biggest size that our queue could be.

Another interesting piece here is the queue that we are using. In my solution I am just using a normal JS array. This works like a queue in terms of the operations, but does not give us the performance we could get from a true queue implementation. Analyzing this piece is beyond the scope of this blog post, but it’s important to call it out.

Hope you found this helpful!

LeetCode 25. Reverse Nodes in k-Group

vickdayaram — Sun, 27 Feb 2022 00:00:00 +0000

Solving LeetCode 25. Reverse Nodes in k-Group. Click here and try it out your self!

LeetCode Problem Statement

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list’s nodes, only nodes themselves may be changed.

Examples:

Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]

Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]

Initial Thoughts

Linked Lists… For me, these problems are fairly easy to understand conceptually. The challenging part here is figuring out the implementation. With Linked Lists problems, keeping track of pointers is key.

Breaking it down

Lets look at an example and start working through it to understand what the implementation will look like.

Overview

From looking at this we can see that we will need a way to count the nodes as we iterate through them. Once we get to k nodes, we will have to run some operations to reverse that sub list, and re-connect it. Once we do that, we can move on to the next k nodes.

What to do once you get to k nodes

Once we get to the kth node we will need to reverse the list from 1 to 2. In order to reverse a list, we will need the startingNode. We will need a pointer to keep track of that.

Then we can disconnect the list, and keep track of the rightHalf to re-connect.

Reversing the sub-list

Now we can actually reverse the list. We won’t be doing a deep dive on linkedList reversal here. If you aren’t familiar with how to reverse a linkedList, I highly recommend you learn that first before diving into this problem.

Once we reverse the list we should have:

Important observation here. Notice how starting node is now the tail of our subList, and currentNode is the head.

Re-connecting the reversed sub-list to the main list and re-setting for the next iteration

To re-connect and reset we would run the following operations on our pointers:

startingNode.next = rightPart
startingNode = rightPart
currentNode = rightPart
counter = 1

Resulting in:

Hmm ok, we have made some progress. There are two things that we are missing here though…

What about the leftPart?!

We haven’t seen the leftPart come into action yet, but as you probably guessed we will have to handle this. To handle this we will use a leftPart pointer.

What are we going to return once we are done?

We will have to return the newHead of the first subList. To handle this, we can… you guessed it, use a newHead pointer.

Re-connecting the reversed sub-list to the main list and re-setting for the next iteration with the leftPart and newHead

Then, we’ll run the following operations…

startingNode.next = rightPart // connect the list
newHead = currentNode // set the newHead, we will only do this once
leftPart = startingNode // save the leftPart for the next iteration
startingNode = rightPart // save the next startingNode
currentNode = rightPart // set up the next currentNode
counter = 1 // reset the counter

Then we’ll be left with…

Re-connecting the reversed sub-list to the main list and re-setting for the next iteration in the middle of the list

Disconnect the subList, and reverse it by running:

rightPart = currentNode.next // save the rightPart
currentNode.next = null, disconnect from the main list
reverse(startingNode) // reverse the subList

Resulting in…

Re-connect the subList to the mainList, and reset for the next iteration.

leftPart.next = currentNode // connect the leftPart
startingNode.next = rightPart // connect the rightPart
leftPart = startingNode // set the next leftPart
startingNode = rightPart // set the next startingNode
currentNode = rightPart // set the next currentNode
counter = 1 // reset the counter

Resulting in…

Nice, our process should handle all the intermediate subLists.

Handling the end of the list

Here our counter equals 2 which equals k. With our current flow this would trigger our a subList reversal, however it shouldn’t since this is not a true subList with length 2. To handle this case, we will only trigger our process if:

if (currentNode !== null && counter === k)

Adding this will ensure that we get the desired behavior. Nice!

The Algorithm Plan

Edge case handling

If k === 1, return head. (Nothing needs to be processed in this case, return the list as is)

Global variables

Declare leftPart initialize to null
Declare newHead initialize to null
Declare currentNode initialize to head
Declare startingNode initialize to head
Declare counter initialize to 1

Main loop

Iterate through the list while currentNode !== null
Increment the counter in each iteration
If the counter === k and currentNode !== null
- Declare rightPart, and initialize it to currentNode.next for next iteration
- Disconnect and reverse
- Set currentNode.next to null to disconnect the list
- Reverse the list from the startingNode
- If there is no head, set it to currentNode
- Re connect
- Connect to left: If there is a leftPart, connect it to currentNode
- Connect to right: Set startingNode.next to rightPart
- Re set for next iteration
- Set leftPart to startingNode
- Set startingNode to rightPart
- Set currentNode to rightPart
- Set counter to 1
Return newHead

Lets code it up!

Code


const reverseKGroup = (head, k) => {

    // Handle edge case
    if (k === 1) {
        return head;
    }

    let leftPart = null;
    let newHead = null;
    let currentNode = head;
    let startingNode = head;
    let counter = 1;

    while (currentNode) {
        currentNode = currentNode.next;
        counter++;
        if (currentNode && counter === k) {

            // Save right part for next iteration    
            let rightPart = currentNode.next;

            // Disconnect and reverse
            currentNode.next = null;
            reverse(startingNode);

            // Set newHead if needed
            if (newHead === null) {
                newHead = currentNode;
            }

            // Connect the list back
            if (leftPart !== null) {
                leftPart.next = currentNode;
            } 
            startingNode.next = rightPart;

            // Reset for the next iteration
            leftPart = startingNode;
            startingNode = rightPart;
            currentNode = rightPart;
            counter = 1;
        }
    }

    return newHead;
}

const reverse = (node) => {
    let prev = null;
    let currentNode = node;
    while (currentNode) {
        let nextNode = currentNode.next;
        currentNode.next = prev;
        prev = currentNode;
        currentNode = nextNode;
    }
    return prev; // returning for as a good practice, not needed in this problem
}

Summary

This algorithm runs in O(n) time where n is the number of nodes in the list, and O(1) space.

As you can see the code is fairly trivial. It’s very easy to get tripped up with all the different pointers that you have to keep track of. I sure did!

Having a good mental model is key, and drawing things out really helps especially if your more visually inclined. In fact, I’d say that’s probably true for most problems.

Hope this was helpful!

LeetCode 57. Insert Interval

vickdayaram — Sun, 20 Feb 2022 00:00:00 +0000

Solving LeetCode 57, Insert Interval. Click here and try it out your self!

LeetCode Problem Statement

You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

Examples:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

Initial Thoughts

Brute force: push the new interval, then sort by start time and merge all the remaining intervals. The data is already sorted though… can we use that to make this more efficient?

Draw a timeline diagram for sure. Doing that is one of the most helpful things when solving these interval problems.

Breaking it down

Lets look at the example:

From looking at this, we can figure out that the right spot to insert the interval is between the first and second interval in the list.

So to find the insertion point, we have to find the first interval that overlaps with the new interval

Lets look at the second example:

So we can find our insertion point by iterating through the intervals and checking if the new interval overlaps with the current one we are iterating through.

Notice how the intervals before the insertion will stay as is. They will not be subject to merge. However, all the intervals after insertion may be subject to merge.

With this in mind, we could iterate through the intervals while there is no overlap with the new interval, and push intervals into a results array. Then we can iterate through the remaining values, merge if necessary, and push into the results array.

Let’s step through it:

Once the loop breaks we can push the new interval into the results.

From here this will resemble a merge interval problem. We can iterate through the remaining intervals, and merge when we have to. If you are not familiar with this problem, I highly recommend that you work on that first.

Stepping through the second half:

Lastly, return our results:

Nice

The Algorithm Plan

The algorithm will be broken into three parts:

Part 1

Iterate through intervals while current interval does not overlap with new interval
Push interval into results array

Part 2

We have found the insertion point, push new interval into results array

Part 3

Iterate through the remaining intervals
If currentInterval and lastInterval overlap
- Merge intervals
- Pop from results
- Push merged into results
If they do not overlap
- Push into results
Increment the currentIdx

Finally, return results

Ok, lets code it up!

Code


const insert = (intervals, newInterval) => {

    let results = [];
    let currentIdx = 0;

    // Part 1
    while (intervals[currentIdx] && intervals[currentIdx][1] < newInterval[0]) {
        results.push(intervals[currentIdx]);
        currentIdx++;
    }

    // Part 2
    results.push(newInterval);

    // Part 3
    while(currentIdx < intervals.length) {
        let lastInterval = results[results.length - 1];
        let currentInterval = intervals[currentIdx];
        if (lastInterval[1] < currentInterval[0]) {
            results.push(currentInterval);
        } else {
            let merged = [
                Math.min(currentInterval[0], lastInterval[0]),
                Math.max(currentInterval[1], lastInterval[1])
            ]
            results.pop();
            results.push(merged);
        }
        currentIdx++;
    }

    return results;
}

Summary

The time complexity of this algorithm is O(N), where N is the number of intervals in the list. The space complexity is O(N) since we are creating a new list.

I remember when first attempting this, it was really hard to wrap my head around. The biggest thing that has helped me with interval problems in general is remembering the following:

Non overlapping cases are easier to identify than overlapping cases

This is key from an implementation stand point. It’s must easier to write code to determine if intervals don’t overlap, versus the cases that they do. Good way to see this for your self is to draw some diagrams, and identify all the ways that two intervals can overlap, and all the ways that they won’t. Highly recommend that you explore this.

Thanks for reading. Hope this was helpful!

LeetCode 143. Reorder List

vickdayaram — Sat, 12 Feb 2022 00:00:00 +0000

Solving LeetCode 143. Reorder List. Click here and try it out your self!

LeetCode Problem Statement

You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln

Reorder the list to be on the following form:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

You may not modify the values in the list’s nodes. Only nodes themselves may be changed.

Examples:

Input: head = [1,2,3,4]
Output: [1,4,2,3]

Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]

Initial Thoughts

Hmmm… After some thought, it became clear that I’d have to solve a couple of sub problems. The way I realized this was by looking at the input and output, and walking through some examples by hand. Drawing things out by hand is recommended by mostly everyone, and with great reason. A tool that I have been using lately to do this is excalidraw. It’s been super helpful.

So, Draw things!

Breaking it down

Let’s take an example:

It looks like we would like to re order the list in a way where we are interleaving the numbers from the end of the list into the beginning.

The pattern would be to start with the last node, 5 in this case, and place it between the 1 and the 2. Then take the next last node, 4, and place it between the 2 and the 3.

We have two sets of numbers. Set A, the set we will insert nodes into, and Set B, the nodes that we will insert into Set A. Since we are only given one list however, we have to determine where one set of number ends and the other begins. From the example above, we can see that the middle of the list is this spot.

We can find the middle of the list, and then have two lists that we can work with. To find the middle of a linked list we can use the fast and slow pointer approach. With this approach we would end up with something like:

This looks like something we can work with. Although it will be hard to work with the second list since we want to start backward. This is a singly linked list so we don’t have a reference to the previous node.

What if it was reversed? Then our lists would look something like:

Instead of having two separate lists, we could have two lists that end on the same node. Something like this:

Our algorithm implementation will be written expecting to operate on this data structure (two lists that end on a shared node). Keep this in mind. Disconnecting the two lists would work as well, but the implementation would be different.

So we will find the middle of the linked list, and reverse the second half. Once we get here we have to figure out how to interleave the nodes of the two lists. This is the tricky part.

We can iterate through both the lists, and update the pointers as we go. Let’s look at an overview of the process:

During iteration

Looks like things would work. Lets take a look at how our loop would break in this case:

As you can see, we end up in a situation where

firstHalf = 3 -> null
secondHalf = 3 -> null

Following our algorithm

let nextFirstHalf = firstHalf.next // null
firstHalf.next = secondHalf // 3, circular reference
firstHalf = nextFirstHalf // null

let nextSecondHalf = secondHalf.next // 3, circular reference
secondHalf.next = firstHalf // break circular reference, now 3 -> null
secondHalf = nextSecondHalf // 3, with no circular reference

In this case, things would just work once the loop breaks. Nice!

But… How would the loop break with an even number of nodes?

I’ve added a node to our example, lets pick it up and go through it to find out.

In this case, secondHalf would be null, and firstHalf.next would be pointing to itself. As you can see we end up with a cycle.

To ensure we return a proper list without a cycle, we have to check to make sure that firstHalf.next equals null after the loop breaks. If it doesn’t, set it to null to remove the cycle

The last iteration is key here! This tripped me up for sure!

The Algorithm Plan

Steps we need to solve this problem from our breakdown analysis:

Overview

Find middle of list
Reverse second half
Use to pointers to iterate through both lists, and interleave the nodes

Finding the middle of the linked list

Use a two pointer approach
- Previous pointer, Slow pointer, and Fast pointer
- Once Fast reaches the end, Slow will be the middle node of the list

Reverse the second half of the list

Write a helper function to reverse the list starting from the slow node
The function should return the new head of this list, this value will be our secondHalf

Interleave the nodes

Create a pointer for the firstHalf
Iterate through while firstHalf and secondHalf are not null
Update pointers for the firstHalf
- Store the nextFirstHalf
- Set firstHalf.next to secondHalf
- Set firstHalf to nextFirstHalf
Update pointers for the secondHalf
- Store the nextSecondHalf
- Set secondHalf.next to firstHalf
- Set secondHalf to nextSecondHalf
Return head (Since we are just changing pointers, we can return the original head of the list we were given)

Alright, lets code it up!

Code


const reorderList = (head) => {

    // Find the middle
    let slow = head;
    let fast = head;

    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }

    // reverse second half
    let secondHalf = reverseList(slow);

    // interleave nodes
    let firstHalf = head;

    while (firstHalf && secondHalf) {
        // Update firstHalf pointers
        let nextFirstHalf = firstHalf.next;
        firstHalf.next = secondHalf;
        firstHalf = nextFirstHalf

        // Update secondHalf pointers
        let nextSecondHalf = secondHalf.next;
        secondHalf.next = firstHalf;
        secondHalf = nextSecondHalf;
    }

    // remove circular dependency if it exists
    if (firstHalf && firstHalf.next !== null) {
        firstHalf.next = null;
    }
    // return original head since we were just changing pointers
    return head;
}

const reverseList = (node) => {
    let prev = null;
    while (node) {
        let nextNode = node.next;
        node.next = prev;
        prev = node;
        node = nextNode;
    }
    return prev;
}

Summary

This was an interesting problem. The solution I am using here is from educative.io. Using two linked lists that point to the same node wasn’t something that came to my mind. This data structure makes the algorithm slightly nicer though.

Without knowing that solution, disconnecting the lists is a more natural solution. The crux with that approach also reveals it self in the last iteration. You have to add some additional logic in the loop to handle some cases.

I challenge you to give that a shot. Draw out a diagram and work through it slowly, iteration by iteration.

Sometimes, you have to go slow to go fast!

Hope this was helpful!

LeetCode 581. Shortest Unsorted Continuous Subarray

vickdayaram — Sun, 23 Jan 2022 00:00:00 +0000

Solving LeetCode 581, Shortest Unsorted Continuous Subarray. Click here and try it out your self!

LeetCode Problem Statement

Given an integer array nums, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order.

Return the shortest such subarray and output its length.

Examples:

Input: nums = [2,6,4,8,10,9,15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

Input: nums = [1,2,3,4]
Output: 0

Input: nums = [1]
Output: 0

Initial Thoughts

This problem tripped me up. Grasping what you need to do is straight forward, but I had to spend some time coming up with a way to do this. What helped me get un-stuck is looking at examples and looking for a pattern. Doing this helps me understand more deeply what I am trying to find.

Once you know what you need to find, it’s easier to formulate a plan to get to a solution. So ask yourself often, “What I’m I looking for?”

What we are looking for

The minimum number out of order
The maximum number out of order
The index to insert the minimum number for it to be in order
The index to insert the maximum number for it to be in order

Break down the problem and make it easy

The Algorithm Plan

Keeping in mind the problems we need to solve, lets look at our Algorithm Plan.

Iterate from left to right and look for the first number out of order
- Number out of order will be arr[i] > arr[i + 1]
- If no number is found, return, array is sorted
- Call this the lowIdx
Iterate from right to left and look for the first number out of order
- Number out of order will be arr[i] < arr[i - 1]
- Call this the highIdx
Look for the minimum number in the subarray from the above indexes
Look for the maximum number in the subarray from the above indexes
Expand the subarray if needed
- Decrement the lowIdx while the current value at low index is greater than the minNumber you found.
- Increment the highIdx while the current value at the high index is less than the maxNumber you found.
Return maxIdx - minIdx + 1. This is the length of the min subArray the needs to be sorted

That’s our plan! As you can tell by looking at it, we are just solving our sub problems, one sub problem at a time.

Lets code it up!

Code


const findUnSortedSubArray = (array) => {

    let low = 0;
    let high = array.length - 1;

    while (low < array.length - 1 && array[low] <= array[low + 1]) {
        low++;
    }

    // Array is sorted
    if (low === array.length - 1) {
        return 0;
    }

    while(high >= 0 && array[high] >= array[high - 1]) {
        high--;
    }

    let arrayMin = Infinity;
    let arrayMax = -Infinity;
    for(let i = low; i <= high; i++) {
        arrayMin = Math.min(arrayMin, array[i]);
        arrayMax = Math.max(arrayMax, array[i]);
    }

    while (low > 0 && array[low - 1] > arrayMin) {
        low--;
    }

    while (high < array.length - 1 && array[high + 1] < arrayMax) {
        high++;
    }

    return high - low + 1;    
}

Summary

This Algorithm runs in O(N) time and O(1) space. Credit to Educative.io for this solution. It’s very elegant, and it’s a great example of breaking down a problem into sub problems.

The key takeaway from this problem is to break it down and keep it simple. The first part of solving these questions is teasing out that ambiguity.

Hope that you enjoyed this walk through.

So, break it on down, and keep it simple

LeetCode 202. Happy Number

vickdayaram — Sun, 23 Jan 2022 00:00:00 +0000

Solving LeetCode 202, Happy Number. Click here and try it out your self!

LeetCode Problem Statement

Write an algorithm to determine if a number n is happy.

A happy number is a number defined by the following process:

Starting with any positive integer, replace the number by the sum of the squares of its digits. Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy. Return true if n is a happy number, and false if not.

Examples:

Input: n = 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

Input: n = 2
Output: false

Initial Thoughts

Happy Number. I didn’t realize numbers could feel emotions…

HA!

I thought I would have to keep track of my solutions. If a solution was equal to 1, then it would be a happy number. If I saw it before, then it would be a sad number.

This solution would require extra space though… can we do better?

Could we solve with with O(1) space?

Indeed we can by using slow and fast pointers. Lets see how!

The Algorithm Plan

The key insight here is that we are searching for a cycle. Either a cycle that gets stuck in a number 1, or a cycle that doesn’t. Lets keep that in mind as we go through this Algorithm plan.

Approach Overview

Set up two pointers, a slow one and a fast one
- Slow = number
- Fast = getNextSum(number)
While fast != 1 && slow != fast
Slow pointer will solve the problem for the current number
Fast pointer will solve the problem for two steps ahead
When the loops break
- return fast === 1
- If this is true, the number is happy, else it’s sad

getNextSum implementation

Accepts number
Declare sum variable and set to zero
While number > 0
- Get the leading digit with modulo operator number % 10
- Update the sum with the square value sum = digit * digit
- Remove the leading digit from the number number = Math.floor(number/10)
Return the sum

That’s our plan. Overall this algorithm is fairly easy to implement. Nothing fancy here.

Once you realize that you are searching for cycles, this solution follows nicely. That’s the key insight we need to uncover.

Lets code it up!

Code


const isHappy = (number) => {
    let slow = number;
    let fast = getNextSum(number);
    while(fast !== 1 && slow !== fast) {
        slow = getNextSum(slow);
        fast = getNextSum(getNextSum(fast));
    }
    return fast === 1;
}

const getNextSum = (number) => {
    let sum = 0;
    while(number > 0) {
        let digit = number % 10;
        sum += digit * digit;
        number = Math.floor(number / 10);
    }
    return sum;
}

Summary

This Algorithm runs in O(logN) time and O(1) space. The time complexity here is hard to determine. It requires some real insight into the numbers.

For a detailed time complexity analysis I’d highly recommend the solution section on leetCode here.

Hope the walk through was helpful!

LeetCode 844. Backspace String Compare

vickdayaram — Sat, 22 Jan 2022 00:00:00 +0000

Solving LeetCode 844, Backspace String Compare. Click here and try it out your self!

LeetCode Problem Statement

Given two strings s and t, return true if they are equal when both are typed into empty text editors. ’#’ means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

Examples:

Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: Both s and t become "ac".

Input: s = "ab##", t = "c#d#"
Output: true
Explanation: Both s and t become "".

Input: s = "a#c", t = "b"
Output: false
Explanation: s becomes "c" while t becomes "b".

Initial Thoughts

Ok, I can use a stack, array, or maybe even build a new string with backspaces applied?!!

But…

Can you solve it in O(n) time and O(1) space?

Hmmm…

Well… I mean… I guess… Yea… Hmm…

Spoiler, Yes we can. Lets take a look and see how

The Algorithm Plan

How can this work? O(n) and O(1) space…

We can use a two pointer approach to achieve this

Overall Execution

Set up two pointers
- One for the first string, set to the last character
- One for the second string, set to the last character
We will iterate through each character until we reach the first character of each string. Iterate while sIdx >= 0 || tIdx >= 0. This will ensure that we can get to the end of the strings if they are different lengths
- For each iteration we will look for the next valid character idx
- Valid character idx will be a an idx that will be part of the final string after backspaces are applied.
- We will write a helper function for this functionality since we will need it for both strings.
- Once we have a valid idx for both strings we will compare them.
- If they are the same
  - Decrement the pointers
  - Continue to check the next character
- Else, return false and break. Strings are not equivalent
If the loop breaks check if sIdx === tIdx.
- If they do, the strings are equivalent.
- This is a case we will run into if the backspaces wind up creating an empty string for both strings and return -1s.
- If one string becomes empty, and not the other, then they are not equivalent.

Valid Character Helper Function

Args: currentIdx, string
Set up a backspace count variable equal to 0
If the current character is not a ”#”
- If backspace count is 0
- return currentIdx
- If backspace count is > 0
- decrement backspace count
If the current character is a ”#”
- Increment backspace count
Decrement currentIdx for each iteration
Return -1 if there are no more characters

The helper function is what’s doing most of the work here. Notice how we are finding the right indexes to compare here in O(1) space.

That’s our plan. Lets code it up!

Code


const backspaceCompare = (s, t) => {
    let sIdx = s.length - 1;
    let tIdx = t.length - 1;

    while (sIdx >= 0 || tIdx >= 0) {
        sIdx = getValidIdx(s, sIdx);
        tIdx = getValidIdx(t, tIdx);
        if (s[sIdx] !== t[tIdx]) {
            return false;
        }
        sIdx--;
        tIdx--;
    }

    return sIdx === tIdx;
}

const getValidIdx = (string, idx) => {
    let backspaceCount = 0;
    while(idx >= 0) {
        let char = string[idx];
        if (char !== "#" && backspaceCount === 0) {
            return idx;
        }
        if (char !== "#" && backspaceCount > 0) {
            backspaceCount--;
        }
        if (char === "#") {
            backspaceCount++;
        }
        idx--;
    }
    // At this point we would return -1 if there are no more valid chars
    return idx;
}

Summary

This Algorithm runs in O(n) time and O(1) space. We completed our challenge! The crux here is figuring out how to apply the backspaces without using extra space. When I took on the challenge that’s the part that I struggled with the most. The pointer approach works quite beautifully.

The aha moment for me was that I don’t need to compare the entire strings in one go, I can do it character by character. That insight really helps open up the door to this approach.

Hope you found this walk through helpful!

LeetCode 75. Sort Colors

vickdayaram — Sun, 16 Jan 2022 00:00:00 +0000

Solving LeetCode 75. Sort Colors with a two pointer approach. Click here and try it out your self!

This problem is also known ad the Dutch National Flag problem because the flag has three colors.

LeetCode Problem Statement

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library’s sort function.

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Input: nums = [2,0,1]
Output: [0,1,2]

This problem is simple enough. But can we solve it in O(n) time without any extra space?!

Take a breath to think about it…

AAAAHHHH… Yes! But how? Two pointer approach to the rescue

The Algorithm Plan

The intentions of the machine we will create…

Execution

Create three global variables for positions
- idx, iterator, current value
- low, last lowest index, for 0s
- high, last highest index, for 2s
Iterate number by number until we reach the current high value
- Implement this with a while loop, while idx <= high
- It’s important to use high here because the value will change. We need the loop to terminate early for things to work as expected.
Run checks
- If the num === 0
- swap values with left pointer
- increment the left pointer
- increment idx
- If the num === 2
- swap values with the right pointer
- decrement the right pointer
- If the num === 1
- increment the idx, this value is in the right place
return the array

Planning is a crucial part of solving problems. Take the time to plan and set your self up for a easy execution.

Lets code it up!

Code


const swap = (values, iOne, iTwo) => {
    const temp = values[iOne];
    values[iOne] = values[iTwo];
    values[iTwo] = temp;
}

const sortColors = (nums) => {

    let idx = 0;
    let low = 0;
    let high = nums.length - 1;

    while (idx <= high) {
        let val = nums[idx];
        if (val === 0) {
            swap(nums, low, idx);
            low++;
            idx++;
        } else if (val === 2) {
            swap(nums, high, idx);
            high--;
        } else {
            idx++;
        }
    }
    return nums;
};

Summary

This algorithm runs in O(n) time with O(1) space. Very nice. Satisfying these constraints is the hardest part of this problem. Using the two pointer approach works quite nicely. I have used two pointers before but using them in this fashion is new to me. This is a great one to visualize in your mind a bit as far as how it’s actually working.

When writing the plan section I didn’t think about the helper function for the swapping. The helper function dawned on me as I was coding up the solution. I think shaping your algorithm a bit as you go is ok. Figuring out how to structure it while you are coding up though… I’m sure it can be done, but it’s not the best approach.

Take the time to plan. A Wizard in the future will thank you. That Wizard will be you, if you hone in your planning game.

Hope you found this walk through helpful!

LeetCode 16. 3Sum Closest

vickdayaram — Sat, 15 Jan 2022 00:00:00 +0000

Solving LeetCode 16. 3Sum Closest, with a two pointer approach. Click here and try it out your self!

LeetCode Problem Statement

Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.

Return the sum of the three integers.

You may assume that each input would have exactly one solution.

Examples:

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Input: nums = [0,0,0], target = 1
Output: 0

This problem is interesting. What you are asked to is simple, and is easy to understand. Today we will work on building out a solution that runs in O(n^2) by using a two pointer approach.

The Algorithm Plan

The intentions of the machine, and how it will run…

Execution

Sort the array of numbers up front. Two pointer approach only works with a sorted set of numbers.
Iterate through each value in the array until array.length - 2. This ensures we always have triplets and don’t have to deal with out of bound errors.
For each iteration
- Set up a left var equal to i + 1
- Set up a right var equal to array.length - 1
- Set up a while loop, while left < right
- Calculate current sum
- Run checks
  - If we found a better answer, update ClosestSum
  - Use Math.abs, remember there could be negative numbers
  - If sum is greater than target, decrement right to find a better answer
  - If sum is less than target, increment left to find a better answer

Variables

ClosestSum: Global Variable to keep track of the best answer. We will return this at the end. Initialize to Infinity
Left Pointer, Right Pointer, CurrentSum, for each iteration of the loop.

These are the steps that we need to execute for the algorithm.

Special Note on Planning: Planning is an important step when writing code. The better you plan, the easier it will be to code the solution. So take extra time here, its a wise investment. It may seem slower at first, but it’s how you will become a wizard.

Lets code it up!

Code


const threeSumClosest = (nums, target) => {

    // Sort the array for two pointer approach
    nums.sort((a, b) => a - b);

    let closestSum = Infinity;

    for(let i = 0; i < nums.length - 2; i++) {

        let val = nums[i];
        let left = i + 1;
        let right = nums.length - 1;

        while (left < right) {
            const currentSum = val + nums[left] + nums[right];
            const currentDiff = Math.abs(target - currentSum);
            const closestDiff = Math.abs(target - closestSum);

            if (currentDiff < closestDiff) {
                closestSum = currentSum;
            }

            if (target < currentSum) {
                right--;
            } else {
                left++;
            }
        }
    }

    return closestSum;
}

Summary

This Algorithm runs in O(n^2) time. O(n * log(n)) for the sort plus O(n^2) for the iteration, O(n * log(n) + n^2), which is asymptotically equivalent to O(n^2). Space complexity will be O(n) which is required for sorting.

The two pointer approach pattern we used here can be used for a variety of other problems similar to this one. It’s a great one to have in your tool belt.

Hope you found this walk through helpful. If you take one thing away from this I hope it’s the planning piece. Take the time to plan. It’s a habit that will help you as an engineer, and life in general.

LeetCode 424. Longest Repeating Character Replacement

vickdayaram — Sat, 08 Jan 2022 00:00:00 +0000

Solving LeetCode 424. Longest Repeating Character Replacement, with a Sliding Window approach. Click here to try it out your self!

LeetCode Problem Statement

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations

Examples:

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.

This was a tough problem for me to wrap my head around. The key for me was getting a better insight into what I was looking for…

Working backwards, what does our solution look like?

We are looking for the longest substring that contains the same characters after substituting up to K times.

In other words we are looking for a substring that contains the max alike letters plus K substitutions. So in any given window our answer should work out to be:

const solution = maxLetterCountInWindow + k

Where solution must be less than the length of the string.

Example 1:

Input: s = "ABAB", k = 2
Output: 4

window = {A: 2, B: 2} from index 0 to 3;
maxLetterCount = 2;
k = 2;

solution = maxLetterCount + k
solution = 4

In the above example we can either have a window where the maxLetter is A, or B. In either case we can delete the other letter up to K times, which in this case is 2.

Example 2:

Input: s = "AABABBA", k = 1
Output: 4

Solution 1
window = {A: 3, B: 1} from index 0 to 3
maxLetterCount = 3
k = 1

solution = maxLetterCount + k
solution = 4

Solution 2
window = {A: 1, B: 3} fro index 2 to 5
maxLetterCount = 3
k = 1

solution = maxLetterCount + k
solution = 4

Understanding this insight turned this hard problem into a manageable one. Let’s look at the code and see how we can apply this.

Code

const findLengthOfLongestSubStringWithMaxDeletes = (str, k) => {

    let maxLength = -Infinity;
    let maxLetterCount = 0; 
    let frequencyMap = {}; // for the given window
    let windowStart = 0;

    for(let windowEnd = 0; windowEnd < s.length; windowEnd++) {
        let rightChar = s[windowEnd];
        if (!frequencyMap[rightChar]) {
            frequencyMap[rightChar] = 0;
        }

        // Keep track of the char frequency in the currentWindow
        frequencyMap[rightChar] += 1;

        // Update the maxLetterCount for the window
        maxLetterCount = Math.max(maxLetterCount, frequencyMap[rightChar]); 

        // Validate the current window to make sure we satisfy the constraints 
        // If the currentLength - maxLetterCount > k 
        // shrink the window since we don't have substitutions left. 
        const currentLength = windowEnd - windowStart + 1;
        if ((currentLength - maxLetterCount) > k) {
            let leftChar = s[windowStart];
            // Remember to decrement the frequencyMap with the character 
            // that is going out of the window
            frequencyMap[leftChar] -= 1;
            windowStart++;
        }

        // Now we have a valid window, so check if we have 
        // found a better answer
        const validLength = windowEnd - windowStart + 1;
        maxLength = Math.max(validLength, maxLength);
    }

    return maxLength;
}

Summary

This algorithm runs in O(n) time and O(1) space. Given that we only have 26 letters in the english language, that’s a fixed space we would keep in the hashmap which is equivalent to O(1).

I struggled when solving this problem. Understanding that the length of the substring would equal the maxNumberOfCharacters + k, was the key insight I needed to make a break through.

Hope you found this helpful!