Two Pointers / Sliding Window / Binary Search

Question 1

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.

Answer 1

Helper function to check if alphanum using ASCII (or isalphanum()). While loop L < R and go through the string.

O(n) / O(1)

Question 2

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Answer 2

Sort the input array. If list[i] == list[I - 1] skip that number because it’ll cause duplicate. Outer for loop, with inner while loop with L and R pointers. Move the pointers based on whether the 3Sum is > or < than 0.

O(nlogn + n^2) = O(n^2) / O(1)

Question 3

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.

Answer 3

L = 0, R = len(array), move the pointer with the smaller height (key with these problems is to figure out how to INTELLIGENTLY move pointers)

O(n) / O(1)

Question 4

Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.

Answer 4

Map closingPar to openingPar in hashmap. If char in closing, check if stack is not empty and check stack is there are matching openingPar. If it’s opening, append to stack. Return True if stack is empty at the end.

O(n) / O(n)

Question 5

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Answer 5

• Determine if you’re in the left portion or right portion.
  — if arr[left] <= arr[mid]: # you’re in left, <= BECAUSE if len(arr) == 2
  — else: # you’re in right
• In each portion, check whether you need to move left or right
  — left portion:
  —– if target < left OR target > mid: # move right
  —– else: # move left
  — right portion:
  —– if target < mid OR target > right: # move left
  —– else: # move right

Question 6

Write a basic binary search algorithm.

Answer 6

l, r = 0, len(arr) - 1
while l <= r: # <= covers when length of arr is 1
m = (l + r) // 2

if target == arr[m]:
return m

if target > arr[m]:
l = m + 1

elif target < arr[m]:
r = m - 1

Question 7

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

[4,5,6,7,0,1,2] if it was rotated 4 times.
[0,1,2,4,5,6,7] if it was rotated 7 times.
Notice that rotating an array [a[0], a[1], a[2], …, a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], …, a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

Answer 7

https://www.youtube.com/watch?v=nIVW4P8b1VA

Revisit this for better solution.

Question 8

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.

Answer 8

• Use two pointers.
• While r is before end of the list, check if current pointers are profitable.
• If profitable update maxProfit.
• If not profitable set L = R
• Increment R.

Question 9

List 5 different ways you can move two pointers.

Answer 9

1. Moving pointer(s) while a certain condition is met.
2. Starting from 0, 1 and incrementing.
3. One moves slowly, the other moves quickly (useful for finding middle of linked list)
4. Start one pointer at the beginning, start the other at the end.
5. Set L equal to R when a certain condition is met.

Question 10

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

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

Answer 10

• R and L = 0
• Increment R and add to set() until you hit a duplicate.
• Now you’ve reached the longest substring starting from L.
• While R is a duplicate, remove L from set and increment.
• Now you’ve found the new L to start from.

class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
l = 0
visited = set()
maxLen = 0
for r in range(len(s)):
while s[r] in visited:
visited.remove(s[l])
l += 1
visited.add(s[r])
maxLen = max(maxLen, r - l + 1)
return maxLen

Question 11

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.

Answer 11

• Sliding window, but track the count of the characters in the substring using hashmap.
• Substring valid if len(substring) - maxCharCount <= k.
• While above condition not true shift the L pointer
• calc your max

class Solution:
def characterReplacement(self, s: str, k: int) -> int:
l, r = 0, 0
result = 0
charmap = {}

    while r < len(s):
        charmap[s[r]] = 1 + charmap.get(s[r], 0)

        while (r - l + 1 - max(charmap.values())) > k:
            charmap[s[l]] -= 1
            l += 1

        result = max(result, r - l + 1)
        r += 1
 
    return result

Question 12

How should sliding window pointers generally move?

Answer 12

Start both at 0 and move through the string ascending.

Question 13

Given two strings s and t of lengths m and n respectively, return the minimum window
substring
of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string “”.

The testcases will be generated such that the answer is unique.

Example 1:

Input: s = “ADOBECODEBANC”, t = “ABC”
Output: “BANC”
Explanation: The minimum window substring “BANC” includes ‘A’, ‘B’, and ‘C’ from string t.

Answer 13

• Make two hashmaps, one to track chars in current window, other to track num of chars you need.
• Start L and R at 0 and increment R until window is valid.
• While window is valid, increment L.
• For efficiency, you can’t check hashmap equality each time. Use “have” and “need” counts to reduce repeated work.