DEV Community: blakeahalt

Leetcode 435. Non-overlapping Intervals

blakeahalt — Mon, 17 Apr 2023 09:52:19 +0000

This solution works by first sorting the intervals array in ascending order based on the starti of each interval.

intervals.sort((a,b)=> a[0]-b[0])

The sorted array becomes:
intervals = [[1,2],[1,3],[2,3],[3,4]]

Here is a simple way to visualize the intervals array:

Next, we initialize a variable called prevEnd to the endi of the first interval, or intervals[0][1], and a variable called count to 0.

let prevEnd = intervals[0][1]
let count = 0

Here is what that looks like:

For loops typically begin at i=0, but notice our for loop begins at i=1.

 for (let i=1; i<intervals.length; i++) {
...
}

This is because we've already used the first element of the intervals array, which represents i=0, to set the variable prevEnd = intervals[0][1]. In our case, prevEnd is initialized at 2.

So starting at i=1, every iteration of the for loop compares the values between intervals[i][0] and prevEnd to determine which code in the if/else statement to execute. Note that the value of prevEnd will get updated each iteration.

If intervals[i][0] is greater than or equal to prevEnd, it means that the interval does not overlap with the previous interval and prevEnd is updated to the endi of the current interval, or intervals[i][1].

if (intervals[i][0] >= prevEnd) {
  prevEnd = intervals[i][1]
...

Else, if intervals[i][0] is less than prevEnd, it means that the interval overlaps with the previous interval. So, the variable count is incremented by one and prevEnd is updated to the minimum value between intervals[i][1] and prevEnd.

...
else
  count++
  prevEnd = Math.min(intervals[i][1], prevEnd)
}

Let's walk through the for loop and see how the if/else statement gets applied at each iteration.

In the first iteration, when i=1, we can see that intervals[i][0] <= prevEnd.

According to the if/else statement, we increment the count by 1 and set prevEnd to the smaller value between intervals[i][1] and prevEnd. In this case intervals[1][1]=3 and prevEnd=2, so prevEnd remains the same.

In the next iteration when i=2, prevEnd = intervals[i][0].

According to the if/else statement, we set prevEnd to intervals[i][1]. In this case intervals[2][1]=3, so prevEnd updates its value to 3.

In the last iteration when i=3, prevEnd = intervals[i][0] once again.

Since, there are no more iterations, we exit the for loop and return our count, which is 1.

A visual review of our process shows that removing the second element of the array makes the rest of the array non-overlapping.

The time complexity is O(nlog n), where n is the number of intervals in the input array. This is because the code first sorts the input array, which takes O(nlog n) time, and then iterates through the array once, performing constant-time operations on each element.

The space complexity is O(1), which means that the amount of memory used by the code is constant, regardless of the size of the input. This is because the code only uses a few constant-size variables to store information, and does not create any new arrays or objects.

Hope this was helpful.

Happy coding!

Leetcode 409: Longest Palindrome

blakeahalt — Tue, 04 Apr 2023 08:14:42 +0000

Problem 409: Longest Palindrome

Given a string 's' which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters. Letters are case sensitive.

This solution iterates through the characters of the input string s, and for each character, checks if it is already in the Set 'set'. If the character is already in the Set, it means that it can be part of a palindrome, so the count is incremented by 2 (because a palindrome has two identical halves). The character is also deleted from the Set, so that it cannot be counted again. If the character is not in the Set, it is added to the Set.

At the end of the loop, if the length of the input string s is equal to the count, it means that all characters can be used to form a palindrome, so the count is returned as is. If the length of s is not equal to the count, it means that there are some characters left in the Set that can be used to form a palindrome with the existing characters, so the count is incremented by 1 and returned.

We begin by initializing 'count' to 0 and 'set' to a new empty Set.



let count = 0
let set = new Set()

Next, we start iterating through a for loop.



for (let char of s) {
  ...
}

Each iteration checks whether each character is already in the set or not.
If the character is NOT in the set we add it to the set.



for (let char of s) {
  if {
    ...
  } else 
    set.add(char)
}

If the character IS in the set, the count is incremented by 2 and deleted from the set.



for (let char of s) {
  if (set.has(char) {
    count += 2
    set.delete(char)
  } else 
    ...
}

At the end of the loop we need to return the correct count, indicating the longest possible palindrome. Knowing that a palindrome can contain at most 1 single character, we can use a ternary operator to account for this.



return count < s.length ? count + 1 : count

If the count is less than s.length we know there's at least one single character. In our case, count = 6 and s.length = 8. The longest possible palindrome we could return would be a combination of (dcc[x]ccd), where [x] represents a single character from our set. It doesn't matter if it were (dccaccd) or (dccbccd) since the count would still be equal to 7. The [x] represents the '+ 1' in our ternary 'count + 1'.

If the count is NOT less than s.length that means our string has an even count and every character has a matching character creating a complete palindrome. Since it's impossible for the count to be greater than s.length, when the count is not less than s.length it can only mean that count = s.length. Our ternary could be written as either:



return count < s.length ? count + 1: count



return count < s.length ? count + 1: s.length

Our final code looks like this:



var longestPalindrome = function(s) {
    let count = 0
    let set = new Set()

    for (let char of s) {
        if (set.has(char)) {
            count+=2
            set.delete(char)
        } else {
            set.add(char)
        }
    }
return count !== s.length ? count + 1 : count
}

The time complexity of this code is O(n), where n is the length of the input string s. This is because the code iterates through each character in the string only once and performs constant time operations on each character.

The space complexity of this code is also O(n), where n is the length of the input string s. This is because the code creates a set to store characters that appear an odd number of times in the string, and the size of the set can be at most half the length of the input string (in the case where all characters in the string appear exactly twice). Therefore, the space required to store the set is proportional to the length of the input string. Additionally, the code uses a constant amount of additional space to store the count variable.

Hope this was helpful. Please leave a comment if anything looks incorrect or if you have any questions.

Happy coding!

LeetCode 3: Longest Substring Without Repeating Characters

blakeahalt — Fri, 17 Feb 2023 11:21:27 +0000

Problem 3. Longest Substring without Repeating Characters

Begin by defining the stack variable and max variable.

let stack = new Set()
let max = 0

Using a for loop we can begin adding each element from the input string. At the same time, we want to keep track of the longest substring in the max variable by comparing the current max size and the size of the stack up until that point.

Our full code, so far, would look like this:

var lengthOfLongestSubstring = function(s) {
  let stack = new Set()
  let max = 0

  for (let i=0; i<s.length; i++) {
    stack.add(s[i])
    max = Math.max(max, stack.size)
  }
return max
}

That's a good starting point, but now we need to account for any repeating characters.

Once we get to the third index, you can see that the stack would be:

stack = [a,b,c,c]

This is not what we want because the problem is asking for the longest substring without repeating characters.

To resolve this we need to delete all of the elements in our current stack until there are no repeated characters and then continue the logic we coded above (adding and keeping track of the max).

In order to do this we need to add another variable called left. Our variables can be updated to this:

  let stack = new Set()
  let max = 0
  let left = 0

This left variable is going to point to an element in the string that we delete in our stack. Currently:

left = 0, so s[left] = 'a'.

Using a while loop, we can add logic to delete all of the elements preceding the repeated character. In our case, since our stack = [a,b,c,c] we want to delete stack = [a,b,c] and be left with stack = [c].

The while loop looks like this:

  while (stack.has(s[i])) {
    stack.delete(s[left])
    left++
  }

This will pause at the current i-th iteration in our for loop and execute until true.

Looking at the purple section in the image we can see we're paused at i=3 because our current stack now has a repeated character 'c'. Whenever a repeated character occurs our code will enter the while loop and execute the commands (delete and left++) until false.

It's important to understand that the while loop will keep performing the (delete and left++) commands until the stack no longer has a condition where stack.has(s[i]).

We'll come back to this. Let's run it back to the beginning.

Here is our full code:

var lengthOfLongestSubstring = function(s) {
  let stack = new Set()
  let max = 0

  for (let i=0; i<s.length; i++) {
    while (stack.has(s[i])) {
      stack.delete(s[left])
      left++
    }
    stack.add(s[i])
    max = Math.max(max, stack.size)
  }
return max
}

Take note of where we've placed our while loop. The reason why we we're able to iterate from i=0 to i=3 without entering the while loop is because stack.has(s[i]) was never true.

At i=0, does stack have s[0] or ('a')? No, so we add 'a' to the stack and our for loop goes to i=1. Now our stack=[a].
At i=1, does our stack have s[1] or ('b')? No, so we add 'b' to the stack and our for loop goes to i=2. Now our stack=[a,b].
At i=2, does our stack have s[2] or ('c')? No, so we add 'c' to the stack and our for loop goes to i=3. Now our stack=[a,b,c].
At i=3, does our stack have s[3] or ('c')? YES, and this will trigger our while loop.

Once we have triggered the while loop, as we mentioned above it will start to delete elements from the stack and add 1 to the left variable.

Let's take a closer look at i=3.

Well, after i=2, our stack=[a,b,c]. Now, looking at when i=3, our while loop has checked that, yes, the stack has s[3] or 'c' and begins to delete and add one to left.

what does that look like?

stack.delete(s[left])

This will delete s[left], which currently left=0.
So, we delete s[0] or 'a'.
Then we add one to left.
left=1.

Ok, looking at the code we continue down to stack.add(s[i]) and update the max variable, right? NO!

Because we're in a while loop, we don't exit until the condition stack.has(s[i]) is false. After updating the previous sequence we see that stack=[b,c], left=1 and s[i]= 'c' since we're still paused at i=3.

The while loop continues checking if our stack has 'c'. It does, so we delete s[left], which is now s[1] from the stack and iterate left by 1.
Now our stack=[c] and left=2.

Again, the while loop checks if our stack has 'c'. It does, so we delete s[left], which is now s[2] from the stack and iterate left by 1.
Now our stack=[] and left=3.

Again, the while loop checks if our stack has 'c'. It doesn't because our current stack is empty. In the code, we exit the while loop and execute the next part of the code which is:

  stack.add(s[i])
  max = Math.max(max, stack.size)

So, we add s[i] or 'c' to our stack and calculate the max. Math.max takes the bigger value between max, currently 3 from stack=[a,b,c], and the current stack.size, which is 1.

Now, stack=[c] and max=3

This concludes i=3 and the for loop continues to i=4.

At i=0, does stack have s[4] or ('a')? No, so we add 'a' to the stack and our for loop goes to i=5. Now our stack=[c,a] and we can see that max = Math.max(3,2), 2 being the stack.size of stack=[c,a]. So, still max=3.

Now, stack=[c,a] and max=3

At this point you should be able to follow the remainder of the for loop. We add another element at i=5 and enter the while loop at i=6.

When our for loop ends we check the max value and see that it's 3, which indicates that the longest substring our code found was length 3. In this case, the strings equal to 3 were [a,b,c] and [c,a,b] but the question was not asking for which strings, only the longest length.

The time complexity of this function is O(n), where n is the length of the input string s.

The reason for this is that the function iterates through each character in the string once using a for loop. Within the loop, it performs a constant number of operations, which include set operations (adding, deleting, and checking for membership in the set) and arithmetic operations (comparing and taking the maximum).

The space complexity of this function is O(min(n,m)), where n is the length of the input string s and m is the size of the character set (i.e., the number of distinct characters in s).

The reason for this is that the function uses a set stack to store the characters in the current substring it is considering. The size of the set can be at most the size of the character set, which is O(m). In the worst case, where all characters in the input string are distinct, the size of the set would be equal to n.

In addition to the set, the function also uses a constant amount of additional space O(1) to store variables such as left and max. However, this does not affect the space complexity since it's a constant.

Therefore, the space complexity of the function is O(min(n,m)), since the overall space used by the function is dominated by the size of the set, which is the minimum of n and m.

The best case scenario for this function is when the input string s contains only one character or is empty. In this case, the for loop will execute only once, and the while loop will not execute at all, resulting in a time complexity of O(1) and a space complexity of O(1).

lengthOfLongestSubstring('a') // returns 1
lengthOfLongestSubstring('') // returns 0

The worst case scenario of the function is time complexity O(n) and space complexity O(m), where n is the length of the input string s and m is the stack size of all unique characters.

lengthOfLongestSubstring("abcdefghijklmnopqrstuvwxyz") // In this case, the input string contains all unique characters, and the `stack` set will have to accommodate all characters of the input string. Therefore, the worst case space complexity is O(n), not O(m).

Hope this was helpful. Please leave a comment if anything looks incorrect or if you have any questions.

Happy coding!