LeetCode #125: Valid Palindrome (Solution in Python & Explanation)

In this article, I will be explaining how to solve the Valid Palindrome problem on LeetCode. This is an Easy-level problem.

The Problem

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

Example 1:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.

Example 3:

Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.

Solution

Alphanumeric characters are the lowercase letters a-z, capital letters A-Z, and integers 0-9.

So, to solve this, we first want to remove all non-alphanumeric characters, including spaces, punctuation, etc., from the input string. Then, we need to check the new string to see if it’s a palindrome. We have two ways we can do this.

Solution #1

For this solution, we create a new string which contains all of the alphanumeric characters from the input string (lowercased). Then, we compare this new string to its reversed version. If they are the same, the function returns true. If not, it returns false.

In order to create the new string, we loop through the characters in the original input string and, if the character is alphanumeric, we append it to the new string.

Finally, we can check if the string (without any special characters or spaces) is a palindrome by using a boolean expression to equate it to its reverse. We can get the reverse of a string by using str[::-1]

def isPalindrome(self, s: str) -> bool:
    newStr = ""
    
    for char in s:
        if char.isalnum():
            newStr += c.lower()
    return newStr == newStr[::-1]

This solution has a time complexity of O(n) because we have to loop through the string to remove non-alphanumeric characters. It also has a space complexity of O(n) because we are creating another string, which could be at most the size of the input string.

Solution #2

For this solution, we will create pointers to the beginning and end of the array which will make sure that the two sides have the same characters in the same order.

First, create two pointers— one which points to the beginning of the string and the other which points to the end. The two pointers will move inwards, checking each character until the reach the middle or overlap with each other.

As the pointers loop through the characters, they will skip any characters that are not alphanumeric. To do this, we use while loops that will continue to run until the character at the left/right index is alphanumeric. We also add a check to make sure that the left/right index is in bounds by checking left < right / right > left

We must make sure to compare the lowercase versions of the characters to each other. If any character at the left pointer does not match the corresponding character at the right pointer, then we know that it’s not a palindrome and can return False. If the entire loop finishes then that must mean the string is a palindrome and we can return True. 

def isPalindrome(self, s: str) -> bool:
    left, right = 0, len(s) - 1 
 
    while left < right:
        while left < right and not s[left].isalnum():
            left +=1
        while right > left and not s[right].isalnum():
            right -= 1
        if s[left].lower() != s[right].lower():
            return False 
        left, right = left + 1, right - 1
    return True

The time complexity for this solution is O(n) because you are still looping through the entire string. The space complexity is O(1) because you are not making a new string.

LeetCode #242: Valid Anagrams (Solution in Python & Explanation)

The Problem

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: s = "anagram", t = "nagaram"
Output: true

Example 2:

Input: s = "rat", t = "car"
Output: false

Solution

We know that the two strings are anagrams if:

  1. They have the same length
  2. They have the same characters and the same quantity of each character

So, if we can verify that the strings pass these two criteria, we can verify that they are valid anagrams.

We can check if they are the same length by simply using len:

len(s) == len(t)   # boolean expression

But how can we check if they have the same characters and the same quantity of each character? We can use hash maps. For each string, we can create a hash map that includes every unique character in the string and its frequency in the string.

For example, this would be the hash map of the string s, which has a value of "anagram":

s = "anagram"
countS = {"a": 3, "n": 1, "g": 1, "m": 1}

Once, we have created the hash maps, we can check if they are equivalent by using a boolean expression:

countS == countT

So, let’s put it all together. These are all the steps we have to take:

  1. We check if the strings are not the same length. If they’re not, we can immediately return False without doing any other code.
  2. We create empty hash maps for the two strings s and t.
  3. We loop through each character in s and t and add them to the hash maps. If the character does not exist in the hash map, a new key for the character is added and the value is initialized to 0 (then we add 1). If a key for the character does exist in the hash map, we add 1 to the value.
  4. We check if the two hash maps are equivalent. If they are, we return True. If they are not, we return False.

This is the final code.

   def isAnagram(self, s: str, t: str) -> bool:
        # Step 1: check if same length
        if len(s) != len(t):
            return False
        
        # Step 2: create hash maps
        countS = {}
        countT = {}
        
        # Step 3: loop through characters to add to hash map
        for i in range(len(s)):
            countS[s[i]] = 1 + countS.get(s[i], 0)
            countT[t[i]] = 1 + countT.get(t[i], 0)
        
        # Step 4: check if hash maps are equivalent  
        if (countS == countT): 
            return True
        else: 
            return False

This solution has a time complexity of O(s + t) or simply O(n) because we have to iterate through each of the strings. The space complexity is also O(s + t) because we are building hash maps that are the sizes of arrays s and t.

There is another solution that is much more simple, but less efficient. We can sort both of the strings and see if the sorted versions are equivalent. This works because, if they are anagrams, then they will have the same sorted value.

def isAnagram(self, s: str, t: str) -> bool:
    return sorted(s) == sorted(t)

A good sorting algorithm can sort an array of characters in O(n * log(n)) time. The space complexity could be either O(1) or O(n)

LeetCode: Two Sum (Solution in Python & Explanation)

In this article, I will be explaining how to solve the Two Sum problem on LeetCode. This is an Easy-level question for Arrays.

The Problem

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

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

Example 3:

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

The Solution

The most straightforward way to solve this problem is to check every combination of two values in the array and see if they can sum up to the target value. To do this, we would iterate through the entire array and for each item we would iterate through the array a second time to check the sums of the current array item with every other item in the array and see if they are the target. The (worst-case) runtime for this solution method is not very efficient: O(n2).

There is a better solution that only requires us to loop through the array once. Basically, if we could loop through the array and, for each array item, check if the number that adds with that value to get the target exists in the array using an operation that doesn’t have O(n) time complexity, then we could make our program much faster. We can do this by using a hash map.

We create a hash map that will store array items as keys and their indexes in the array as values ({array_value: array_index})

We use the enumerate function to get the index of the current item as we loop through the array. For each array item, we compute the difference diff between the target value and the item’s value. Since target - n = diff, that means diff + n = target. If this difference diff is in the hash map, then that means that the value has already been seen in the array. Thus, we’ve found the . If the difference is not in the array, then we add the current array item and its index to the hash map then move to the next array item. 

def twoSum(self, nums: List[int], target: int) -> List[int]:
        hm = {} 
        for i, n in enumerate(nums): 
            diff = target - n 
            if diff in hm:
                    return [hm[diff], i]
            hm[n] = i

This solution has a time complexity of O(n) because we only have to loop through the nums array once and the lookup and insert operations into the hash map have a runtime of O(1). Although, we do have to use extra memory to create the hash map. The memory complexity is O(n) because we could potentially add every value to the hash map.

LeetCode: Contains Duplicates (Solution in Python & Explanation)

In this article, I will be explaining how to solve the Contain Duplicates problem on LeetCode. This is an Easy-level question for Arrays.

The Problem

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Example 1:

Input: nums = [1,2,3,1]
Output: true

Example 2:

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

Example 3:

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

Solution

This problem requires that we loop through the array. We may not have to loop through the entire array depending on when / if we find the first duplicate.

As we loop through the array, we check each array item to see if we’ve seen it before. How can we check if we’ve seen a value in the array before? The naive method would be to do a second loop through the array for each. The program will have a complexity of O(n2) because you are looping through each array element and then, within that loop, you are looping through each array element again.

def containsDuplicate(self, nums: List[int]) -> bool:
        dups = set()
        for n in nums:
            for s in nums:
                if n == s:
                   return True
            dups.add(n)
        return False

This solution is slow and we can solve this problem in a more efficient way.

As we loop through the array, we can keep track of the values that we’ve seen thus far. Then, as we continue looping through and checking new values, we can check if they are already in the set of values that we’ve seen before. How can we keep track of the values that we’ve seen? We can use a hash set. This solution takes O(n) time because we are only looping through the array once instead of twice.

def containsDuplicate(self, nums: List[int]) -> bool:
        dups = set()
        for n in nums:
            if n in dups:
                return True
            dups.add(n)
        return False

There is another solution that is even more simple in terms of readability. It is only one line. Basically, we convert the list of numbers into a hash set and compare the length of the set to the length of the original list. If the lengths are different then that must mean that there are duplicate items in the original list because the duplicates are taken out of the set.

This solution uses the no duplicates property of hash sets to solve the problem in an extremely simple way. The time complexity of this solution is also O(n) because that is the complexity of converting a list to a set. 

def containsDuplicate(self, nums: List[int]) -> bool:
        return len(set(nums))!=len(nums)

Data Structures: Arrays

In this article, we will be talking about the most popular data structure: arrays. You will learn what an array is, how it’s stored in your computer’s memory, the complexity of array operations. This will help you to be successful when using arrays in code interviews.

What is an array?

An array, also known as a list, is a collection of items stored in contiguous space in memory. The items of an array are organized sequentially in memory.

This image gives a visual of how arrays are stored in memory. Each array element has a value, memory address, and an index. The index is the integer (0-n) that corresponds to the element’s order position in the array. The first element has an index of 0 and the last element in the array has an of n-1 where n is the length of the array.

Array Operations

OperationComplexity
lookupO(1)
pushO(1)
insertO(n)
deleteO(n)
searchO(n)

The lookup operation takes O(1) time, or constant time because, since each array item is allocated to an equal-size memory space and each memory space is indexed by contiguous integers, your computer is able to immediately jump to the correct memory address using the array index.

The insert operation takes O(n) time, or linear time, because if the item is not at the very end of the list, the other items in the last after the index of the insertion have to be shifted down in memory to make space for the new item. This requires looping through each of the items to copy and move the contents of the memory address to a different memory address.

The push operation also has a complexity of O(1) because since you are adding the item at the last array index, you don’t have to loop through each array element to shift them. This operation has different names in different languages. For example, in Python it’s called append. There is also the pop operation in which the last array item is removed from the array. This also takes constant time.

The delete operation takes O(n) time for the same reason as the insertion operation. When an item is deleted from the array, all of the items after that time must be shifted forward.

The search operation takes O(n) time because you must look at each item in the array in order to see if it is the item you are looking for. This can be quick if it’s one of the first items in the array, but if it’s at the end of the array it will take longer.

Pros & Cons of Arrays

Pros of arrays:

  • Fast lookups
  • Fast push/pop
  • Ordered (sorting)

Cons of arrays:

  • Slow inserts
  • Slow deletes
  • Fixed size (if using static arrays)

Static vs Dynamic Array

Static arrays are a fixed in size. You specify the number of items your array will hold ahead of time.

Dynamic arrays allow us to copy and rebuild an array at a new location with more space in memory.

How to Divide an Array in Half in JavaScript

In this tutorial, I will show you how to divide a JavaScript array into two equal parts (or almost equal if the array has an odd length).

Use the Array instance slice() method:

const test_array = ["a", "b", "c", "d", "e", "f"];

const half = Math.ceil(list.length / 2); 

const firstHalf = list.slice(0, half)
const secondHalf = list.slice(-half)

If the list contains an even number of items, the result is split with exactly half the items:

>>> firstHalf
["a", "b", "c"]
>>> secondHalf
["d", "e", "f"]

The Math.ceil() function always rounds a number up to the next largest integer. We add this in case the array length is odd and list.length / 2 is not a whole number.

If the array contains an odd number of elements, the result is split as close to half as possible.

const odd_array = [1, 2, 3, 4, 5]
const half = Math.ceil(list.length / 2); 
const firstHalf = list.slice(0, half)
const secondHalf = list.slice(-half)

Since there are 5 elements, the half variable will be Math.ceil(5 / 2) = 3. So, the array will split on the third element.

>>> firstHalf
[1, 2, 3]
>>> secondHalf
[4, 5]

Make a Face with D3.js and SVG

This tutorial is a good introduction to using D3.js with SVG. It will cover selecting DOM elements with D3, creating DOM elements with D3, customizing them, and more.

At the end of the tutorial, you will have created a smiley face that looks like this:

Loading D3.js

Load D3.js from CDN by adding the following script tag to the header of your index.html file: 

https://d3js.org/d3.v5.min.js

Now, you can check to make sure that D3 was successfully added to your project by simply typing “d3” in the console while running your html file. It should output the d3 object, which looks like this:

Now, we can use D3 to manipulate the DOM by using the d3 object in our JavaScript code. Here’s an example:

d3.select('div');

Creating a face using SVG and D3

Make an SVG in your index.html file:

<svg width="500" height="250"></svg>

In your app.js file, get access to the SVG element you just created using d3:

const svg = d3.select('svg');

Creating the Head

Now, add a circle to the SVG:

const circle = svg.append('circle');

Now, we will give the circle a radius and (x, y) position for its center. We will use D3 method chaining:

circle 
    .attr('r', 250 / 2)   // radius
    .attr('cx', 500 / 2)  // center x
    .attr('cy', 250 / 2); // center y

I set the radius and center-y values to be half of the height of the SVG and the center-x to be half of the width.

Instead of hard-coding the values in, we can create variables for these width and height values in our JavaScript. To access the width and height values from the SVG in our index.html file, we can use svg.attr(). If you call svg.attr() without a second attribute, it returns the value of the attribute that you specify:

const width = svg.attr('width')

SVG attributes are strings by default, so we can parse the value into a float using parseFloat:

const width = parseFloat(svg.attr('width'));

You can also use the unary operator to parse into a float:

const height = +svg.attr('height');

Now, we can use the variables instead of hard-coded values to define our SVG elements:

circle 
    .attr('r', height / 2)   
    .attr('cx', width / 2)
    .attr('cy', height / 2);

We can also add fill and stroke attributes to give the circle a fill color and outline color:

const circle = svg.append('circle') 
    .attr('r', height / 2)    
    .attr('cx', width / 2)  
    .attr('cy', height / 2)
    .attr('fill', 'yellow')
    .attr('stroke', 'black')

Now, we have the circle for the head:

Creating the Eyes and Mouth

We will make the eyes using circles, similar to how we made the head:

const leftEye = svg.append('circle')
    .attr('r', 10)    
    .attr('cx', width / 2 - 40)     
    .attr('cy', height / 2 - 40)
    .attr('fill', 'black')

const rightEye = svg.append('circle')
    .attr('r', 10)    
    .attr('cx', width / 2 + 40)     
    .attr('cy', height / 2 - 40)
    .attr('fill', 'black')

As you can see, we are defining the leftEye and rightEye variables in the same line in which we are method chaining the attributes.

For the mouth, we will create a group element and add a transform property to the group element to translate it to the center of the face:

const g = svg.append('g')    
    .attr('transform', `translate(${width / 2}, ${height / 2})`);

Then, we will use a d3.arc:

const mouth = g.append('path')
    .attr('d', d3.arc()({     
        innerRadius: 40,
        outerRadius: 50, 
        startAngle: Math.PI / 2, 
        endAngle: Math.PI * 3/2
    }))

Group Elements

Instead of constantly repeating width / 2 and height / 2 to move elements to the center, we can put everything in the group element so that we can leverage that fact that it’s translated by (width/2) and (height/2).

This update doesn’t change the look or functionality, but it just makes our code a little bit cleaner.

First, move the group element to the top of the screen, under the width and height variable declarations.

Then, append the face, eye and mouth elements to the group element instead of to the svg element directly. 

const circle = g.append('circle')

Now, we can remove the cx and cy attributes from the face because it is put in the center by default because its parent, g, is translated into the center:

const circle = g.append('circle') 
    .attr('r', height / 2)    
    .attr('fill', 'yellow')
    .attr('stroke', 'black')

We can also update the eyes:

const leftEye = g.append('circle')
    .attr('r', 10)    
    .attr('cx', -40)     
    .attr('cy', -40)
    .attr('fill', 'black')

const rightEye = g.append('circle')
    .attr('r', 10)    
    .attr('cx', 40)     
    .attr('cy', -40)
    .attr('fill', 'black')

Final Code

The final code is at https://github.com/jbowen4/d3-smiley-face.

The final code in index.html:

<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <script src="https://d3js.org/d3.v5.min.js" defer></script> 
    <script src="app.js" defer></script>
    <title>Let's Make a Face </title>
  </head>
  <body>
    <svg width="500" height="250"></svg>
  </body>
</html>

The final code in app.js:

const svg = d3.select('svg');

const width = parseFloat(svg.attr('width')); 
const height = +svg.attr('height'); 

const g = svg.append('g')  
    .attr('transform', `translate(${width / 2}, ${height / 2})`);

const circle = g.append('circle') 
    .attr('r', height / 2)    
    .attr('fill', 'yellow')
    .attr('stroke', 'black')

const leftEye = g.append('circle')
    .attr('r', 15)    
    .attr('cx', -50)     
    .attr('cy', -40)
    .attr('fill', 'black')

const rightEye = g.append('circle')
    .attr('r', 15)    
    .attr('cx', 50)     
    .attr('cy', -40)
    .attr('fill', 'black')

const mouth = g.append('path')
    .attr('d', d3.arc()({     
        innerRadius: 70,
        outerRadius: 80, 
        startAngle: Math.PI / 2, 
        endAngle: Math.PI * 3/2
    }))

How to Connect to a Remote Server with SSH on VSCode

Install VSCode

Please check the VSCode homepage. https://code.visualstudio.com/.

Install remote-ssh extension in VSCode

  1. Open the VSCode. On the left, there’s an Extension icon.
  2. Search for remote-ssh. Choose the first one and click install.
  3. You may need to reload VSCode to let the extension initialize.

Connect to the remote server

  1. Click View > Command Palette… or use the shortcut cmd+shift+p for Mac and ctrl+shift+p Windows. Type ssh and choose remote-ssh: connect to host.

2. Type the URL of the remote server

3. After that, it will open a new VSCode window.

Add your workspace

  1. After connect to the remote server, we need to cd to our workspace. Call your Command Palette again and type folder. Choose Add folder to your workspace in my case and enter your path to workspace.

Overlapping Histograms with Matplotlib Library in Python

In this tutorial, you will learn how to plot overlapping histograms on the same graph. This is helpful when you want to show a comparison between two sets of data.

Step 1: Import the matplotlib library and matplotlib.pyplot interface

import pandas as pd

import matplotlib
%matplotlib inline
import matplotlib.pyplot as plt

Step 2: Load the dataset

baby_df = pd.read_csv('baby.csv')
baby_df.head(5)

Step 3: Plot overlapping histograms

# Split the dataframe by column value
smoker_df = baby_df.loc[baby_df['Maternal Smoker'] == True]
nonsmoker_df = baby_df.loc[baby_df['Maternal Smoker'] == False]

# Generate histogram plot
plt.hist(smoker_df["bmi"], 
         label='Maternal Smokers BMI')
  
plt.hist(nonsmoker_df['bmi'], 
         label='Maternal Non-smokers BMI')
  
plt.legend(loc='upper right')
plt.title('Mother BMI for smokers and non-smokers')
plt.show()

We’ve generated overlapping histograms! But, in this graph, it’s hard to see the blue histogram. We can give the histograms an opacity value less than 1.0 so that they become translucent, or see-through. This will allow us to see both of them.

Set alpha values

The only difference is adding the optional alpha parameter to the hist method. The alpha value can be any decimal between 0 and 1. Each plot can have a unique alpha value.

# Generate histogram plot
plt.hist(smoker_df["bmi"], 
         alpha=0.5,
         label='Maternal Smokers BMI')
  
plt.hist(nonsmoker_df['bmi'], 
         alpha=0.5
         label='Maternal Non-smokers BMI')

You can also have more than 2 overlapping plots. In this case, it can be helpful to manually set the color for each histogram. We can do this by adding the color parameter to each hist call:

plt.hist(dataset['value'], 
         alpha=0.5, 
         label='val 1',
         color='red') # customized color parameter
  
plt.hist(dataset['value2'], 
         alpha=0.5,
         label='val 2',
         color='green')
  
plt.hist(dataset['value3'], 
         alpha=0.5,
         label='val3',
         color='yellow')

How to Split Pandas DataFrame into Multiple DataFrames by Column Value in Python

In this tutorial, I will show you how to create a separate DataFrame for each value for a given column.

Use the pandas.DataFrame.groupby(column) method to group the DataFrame by the values found in the column named column. 

grouped_df = df.groupby('Column')

This method returns a GroupBy object. You can see this yourself by printing the new dataframe by running print grouped_df:

<pandas.core.groupby.generic.DataFrameGroupBy object at 0x7efe3ec55670>

With the GroupBy object from the previous function, call the DataFrameGroupBy.get_group(group) method on the new dataframe grouped_df. 

This method will return a Dataframe of all the rows that have the value group in the column named column.

grouped_df.get_group('column_value')

Alternatively, you can call both methods in one line:

value_df = df.groupby('Column').get_group('column_value')