Two Pointers and Sliding Window

Question 1

125. Valid Palindrome

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.

Answer 1

Two pointers, while (p1 < p2) check if equal

1. Remove spaces from string and make lowercase

s = s.split(‘ ‘).join(‘’).toLowerCase()

2. Remove non alphanumeric characters with regex.
3. Create pointers for the beginning and end of the string.
4. while p1 < p2, check to see if letters are correct, then p1++ and p2–. if not equal, return false

Question 2

11. Container With Most Water

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Answer 2

Two pointers, get measurement, only shift in smaller pointer(either if equal)

Brute force is to iterate through each item in height and find the total area (product of heights) for each combination.

For linear time we can use two pointers. We can utilize a left pointer all the way to the left and all the way to the right to make the width as big as possible.

Since height is our limiting factor, only shift the smaller pointer in. If equal choose either.

1. Create two pointers
2. While p1 < p2, multiply the lower height (water cannot go past that mark) by the width (p2 - p1)
3. If p1 is smaller, move it forward. If p2 is smaller, move it backward.
4. Return Math.max(…results)

Question 3

121. Best Time to Buy and Sell Stock

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1:
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

Answer 3

Sliding Window, two pointers at 0 and 1, while p2 < length if p1 > p2 set p1 to p2 and p2++

1. Initialize an array to store results, and two pointers at 0 and 1.
2. While p2 < prices.length, if p1 is greater than p2, we want to set p1 to p2, and p2 to the next day.
3. If results.length > 0, return Math.max(…results). Otherwise, return 0 since there is no profit to be made.

Question 4

3. Longest Substring Without Repeating Characters (Medium)

Given a string s, find the length of the longest
substring without repeating characters.

Example 1:
Input: s = “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.

Example 2:
Input: s = “bbbbb”
Output: 1
Explanation: The answer is “b”, with the length of 1.

Example 3:
Input: s = “pwwkew”
Output: 3
Explanation: The answer is “wke”, with the length of 3.
Notice that the answer must be a substring, “pwke” is a subsequence and not a substring.

Answer 4

Sliding Window, make an object called soFar and use two pointers, iterate with p2 and add letters from the string at p2, when you encounter a value with end that is > 1, use inner while loop move p1 up at subtract that value from the object. Once end = 1, calculate the distance

Your first instinct might be to track the current substring by pushing letters to an array and calculating the length once you encounter a dupe character, but the problem is what do you do when you have a string like “dvdf” where you need to backtrack to ‘v’ from the second ‘d’ to get the correct answer.

Brute force: find all substrings and find the one with the longest length by using a nested for loop and slicing from i to j. Then you would hash each element of the string to make sure no character appears more than once.

1. Create two pointers (start and max) and a soFar object to track what letters have been used.
2. Create an outer for loop where we track end until it passes the length of the string.
3. Within the loop either add s[end] to the soFar object with a value of 1, or if the value exists, add 1 to it.

soFar[rightChar] = soFar[rightChar] + 1 || 1;

4. Create an inner while loop that keeps running while soFar[rightChar] is greater than one.
5. If s[start] is greater than 1, subtract it from the object. if it’s equal to one, delete it from the object. Then increment start by 1.
6. set max to to either currentMax or (end - start + 1)

max = Math.max(max, (end - start) +1 )

7. Return max

Question 5

27. Remove Element (Easy)

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.

Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:

Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.
Return k.

Answer 5

** Two pointers to copy in place. p1 and p2 are at 0, p2 iterates and checks to see if the value matches, if not, set [p1] to [p2], copying it over**

Use two pointers by setting left to 0 and using right as a for loop iterator.

On each iteration, check the loop to see if the right pointer !== val. If it doesn’t, set the left pointer to equal val and increment.

Return left.