Notes
Algorithms Interview
Searching

Searching

Sliding Window

Overview

When to Use This Pattern

  • When asked to find the minimum/maximum subarray that meets certain requirements, a brute-force approach will have to look at O(N^2) subarrays. Also, checking whether a subarray meets the requirement in the inner loop can also take O(N).
  • However, when requirement has the property, that if subarray [i:j] does not meet the requirements, then for all k <= i, l >= j subarray [k:l] also fails to meet the requirements, we can apply the sliding window approach to reduce time complexity.
  • First, we set left=0, right=0. We expand the subarray to the right, until subarray [left, right] meets the requirement and [left, right-1] does not. Then we shrink the subarray from left. In a brute-force approach, each time we increment left, we need to look at all the subarray starting with left. But because [left, right-1] does not meet the requirement, for any j < right, [left, j] fails to meet the requirement, and for any j > j, the length of [i, k] is shorter than the previous subarray that meets the requirement
  • First, we set i=0, j=0; We expand the subarray to the right, until [i,j] doesn’t meet the requirement and [i, j-1] does. Then we shrink the subarray from left. In a brute-force approach, each time we increment i, we need to look at all the subarray. But if [i, j] does not meet the requirement, for any k > j, [i, k] fails to meet the requirement, and for any k < j, the length of [i, k] is shorter than the previous subarray that meets the requirement. So we can just keep increment i without making change to j, until subarray [i, j] meets the requirement again.
  • Furthermore, when using a sliding window approach, , and the requirement checking time for each subarray can be reduced to O(1)
  • Time Complexity:

Code Pattern 1: Update maxlen on the first invalid subarray 

 left = 0
 maxlen = 0
 for (right = 0; right < nums.length; right++) // keep incrementing right if [left, right] is valid
   if [left, right] is not valid // then [left, right - 1] is the longest valid subarray starting from the current left
     maxlen = max(maxlen, left - right)
     while ([left, right] is not valid) // keep incrementing left until [left, right] is valid again
       left++;
 maxlen = max(maxlen, left - right) // when right is out of bound, [left, right-1] is valid, but might not yet be updated to maxlen, so update it to maxlen now

Code Pattern 2: Update maxlen on every valid subarray 

 left = 0
 maxlen = 0
 for (right = 0; right < nums.length; right++)
   while ([left, right] is not valid)
     left++;
   maxlen = max(maxlen, left - right + 1) // we reach this statement for every right with its leftmost left that [left, right] is valid

Code pattern 3: non-decreasing window

  • Since we are asked for subarray of maximum length, we can only pay attention to subarray which length is larger than the current maximum length. So when we trying to expand the window from the right, if it is still valid, we add max length by 1, and if it is invalid, we can simply shrink the window from left window once to maintain its window size, and try to expand the window again. And we can even get rid of the left pointer, because it equals to right - max_window_size.

#+BEGIN_SRC maxlen = 0 for (right = 0; right < nums.length; right++) if subarray is valid: left++ maxlen++ if subaary is not valid remove (right - maxlen) from subarray // we do not need to shrink the window to be valid since it will be smaller than the current maximum window anyway

More Efficient Shrinking

Longest window

Longest Subarray of Consecutive 1s after Replacing k 0’s

  • Checking validity: Use an counter to track the numbers of 0’s in the subarray
  • Non-decreasing window: we can use the Code pattern 3: non-decreasing window trick to reduce times of shrinking

Longest Substring with At Most K Distinct Characters

  • Sliding Window property: If a substring has more than K distinct characters, then any other substring containing the substring also has more than K distint characters
  • Checking validity: Use an hashmap to store the occurrences and check map.size() <= k to decide whether the window is valid
  • Non-decreasing window: we can use the Code pattern 3: non-decreasing window trick.

Longest Substring Without Repeating Characters

  • Description: Given a string s, return ind the length of the longest substring without repeating characters.
  • Sliding window property: If a substring has repeating characters, then any other substring containing the substring also has repeating characters
  • Checking validity: Use a hashset to store characters in the current substring. When expanding, if the character to add is in the hashset, then the new substring will have repeating characters and we should start shrinking. When shrinking, increment the left pointer and remove characters from the subset until the repeating character is removed.
  • More efficient shrinking: In the previous approach we need to remove characters one by one until the repeating character is removed, but if you use a hashmap to store the index of the last occurrence of each character, you can move the left pointer straight to the next position after the last occurrence of the repeating character when shrinking. And we don’t need to explicitly remove characters from the hashmap, because having its index less than the left pointer implies not being in the current substring.

Longest Substring with the Same Character After K Replacement

  • Description: Given a string s and an integer k, return the length of the longest substring containing the same characters after k replacement
  • What it means: contain the same letter after k replacement means that for c that has max frequency, frequency(c) >= length(substring) - k~
  • Sliding window property: If a substring has length - maxFrequency > k, then for any substring containing the substring: 1. If the character having the max frequency remains the same, because the length is longer, newLength - maxFrequency is sill larger than k; 2. If another character has overtaken the previous to have the max frequency, then the remaining characters at least contains all the characters in the previous substring other than the new max frequency letter which is larger than k.
  • Checking validity: We use a hash map to keep track of the frequency of each in the window, and maxFreqency to keep track of the maximum frequency in the window. Because we need a larger maxFrequency to get larger maxlen, we can only update maxFrequency when we encountered a larger frequency of a letter.
  • Checking validity: we can use the Code pattern 3: non-decreasing window trick. The final code can look like
         maxlen = 0
     for right = 0 to len(s) - 1 do
       freq[s[right]] += 1
       max_freq = max(max_freq, freq[s[right]]
       if (maxlen + 1 - max_freq <= k) maxlen += 1
       else freq[s[right - maxlen]] -= 1

Exercise

  • Leetcode - 1004. Max Consecutive Ones III (Longest Subarray of Consecutive 1s after Replacin k 0’s)
  • Leetcode - 1493. Longest Subarray of 1’s After Deleting One Element (Exactly same as the previous one with k=1, and we need to return maxlen-1 since it ask us to delete rather than replace)
  • Leetcode - 340. Longest Substring with At Most K Distinct Characters
  • Leetcode - 904. Fruit Into Baskets (Longest Subarray with At Most 2 Distinct Elements)
  • Leetcode - 3. Longest Substring Without Repeating Characters
  • Leetcode - 424. Longest Repeating Character Replacement (Longest Substring with the Same Character After K Replacement)

Minimum window

Minimum Size Subarray with a Given Sum

  • Description: Given an array of positive integers nums and a positive integer target

Return the minimal length of a subarray whose sum is greater or equal to target

  • Because all nums[i] > 0, if sum([i, j]) < target, then for all k >= i, l <= j, sum[k, l] < target. With this property, we can use the sliding window approach to find the minimal length.

Minimum Substring that Contains Every Character of Another String

Exercise

Fixed Size Window

  • Leetcode - 643. Maximum Average Subarray I
  • Leetcode - 1456. Maximum Number of Vowels in a Substring of Given Length
  • Leetcode - 567. Permutation in String link Grok
  • Leetcode - 438. Find All Anagrams in a String link Grok

Two Pointers

Find numbers in a array that sums to a target

2-Sum (Sorted Array)

  • Solution: Because the array is in ascending order, if the sum of the two pointers is less than the target value, only the left pointer can move to the right. If the sum is greater than the target value, only the right pointer can move to the left. Neither pointer needs to backtrack, so the search time is O(n).

2-Sum (Unsorted)

  • Sort the array, then perform Two Sum (Sorted Array). Sorting takes O(nlogn), thus the time complexity is O(nlogn)
  • We can also use a hashset to solve this problem. Iterate through the

Number of 2-sum-pairs we can take from an array

  • Same as previous, but when nums[left] + nums[right] equals target, we also increment the counter.

3-Sum

  • Description: Given an integer array nums. Find all non-duplicate triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0
  • First sort the array, iterate through the array with variale i, then you can transform this problem to the 2 Sum problem on nums[i+1:] to find j and k
  • Avoiding duplicates: When iterating though the array and moving the left pointer, check whether the number is distint from the previous number before proceed
  • Time Complexity: Sort O(N), 2Sum O(N), O(nlogn) + N*O(N) = O(N^2)

3-sum-closest

  • Same as 3-sum, we increment j on the sum is less than target and decrement k on the sum is grater than target. But each time we compute diff as abs(nums[i] + nums[j] + nums[k] - target), and if diff is less than minDiff, we update res as nums[i] + nums[j] + nums[k].

Number of 3-sum-smaller-triples exists in an array

4-sum

  • 2-sum plus backtracking

Exercise

Sort mountain array in O(n)

Sort Squares of a Sorted Array in O(n)

  • Description: Given a non-decreasing array nums, return the array of the squares of each number sorted in non-decreasing order

Exercise

  • Leetcode - 977. Squares of a Sorted Array

When the value we want to optimize is limited by one of two pointers

Container With Most Water

  • Description: 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.
  • We observe that the maximum amount of water it can hold is limited by the shorter line. And for the same shorter line, two lines closer to each other holds less water. So we can start with two pointers at 0 and height.length - 1. Identify the pointer at the shorter line, and move the pointer towards the other pointer until it is longer than the line the other pointer is at, because by then it is possible to holder more water.

Exercise

  • Leetcode - 11. Container With Most Water

In-place rearrangement of array/string

Move zeros elements to the end

  • Traverse through the array, keep a pointer at the place non-zero elements should be placed next: for i = 0 to nums.length - 1 do if nums[i] != 0 ~nums[nonZeroDest++] = nums[i]. Then we fill the rest of the array nums[nonZeroDest:] with 0s.
  • We can also do a swapping approach, which automatically moves all zeros to the end.

Remove duplicate elements in a sorted array

  • Traverse through the array, keep a pointer at the place each unique elements should be placed next: dest = 1; for i = 1 to nums.length - 1 do if nums[i] != nums[i-1] ~nums[dest++] = nums[i].

Exercise

Matching

Is Subsequence

  • s is a subsequence of t if all elements of s have occurred in order in t. We use a pointer p to track up to which index in s we has matched, and we traverse though t with index i, increment p if we have matched s[p] and t[i]. And if we matched all elements in t, it is a subsequence of t, otherwise it is not.

Is Palindrome

Exercise

  • Leetcode - 392. Is Subsequence
  • Leetcode - 125. Valid Palindrome

TODO grok

Binary Search

Normal Binary Search

Algorithm 

 int lo = 0, hi = nums.length;
 while (lo <= hi) {
   int mid = (lo + hi) / 2;
   if (nums[mid] == target)
     return mid;
   if (target > nums[mid])
     lo = mid + 1;
   else
     hi = mid - 1;
 }
 return -1;

Proof

  • We maintain a loop variant that nums[0..lo-1] < target, and nums[hi+1..nums.length-1] > target. So when lo>hi and the loop terminates, (lo-1)+1<=(hi+1), so elements the entire array are either less than or greater than target. So target is not in the array.

Exercise

  • Leetcode - 704. Binary Search link
  • Leetcode - 374. Guess Number Higher or Lower

Find Largest-Smaller/Smallest-Greater Element / Find First/Last Position of Element

Find the smallest greater element

  • Desciption: Given an array of non-decreasing numbers, and a target. Return the smallest number in the array that is greater than the target.
  • Solution: In normal binary search we maintain a loop invariant that nums[0..lo-1] < target, and nums[hi+1..nums.length-1] > target, and returns when when encounter nums[mid] = target. In this case, we are not looking for target, but the smallest number that is greater than target, so we can set lo = mid + 1 when nums[mid] = target, then our loop invariant becomes nums[0..lo-1] <= target. So when the loop terminates, nums[0..lo-1] <= target, num[hi+1..] > target. Also we can proof that lo = hi + 1, so num[lo] will be the smallest greater element.

Find the last position of element

  • Solution: Follow the same approach, but return nums[hi]

Find the largest smaller element

  • Solution: Follow the similar approach, but set hi = mid - 1 when nums[mid] = target and return nums[hi]

Find the first position of element

  • Solution: Follow the same approach, but return nums[lo]

Find the first and last position of element

  • Solution: We can find the first and last position separately. We can also find one element first using binary search, and find the first position on [lo, mid] and the last position on [mid, hi]

Serach insert position

  • Solution:

Exercise

Peak Element in a Mountain Array / Peak Element in a Array

Description

Solution

  • In this problem we want to rule out [0..lo-1] that is ascending, and [hi+1..nums.length-1] that is descending.

Find in a Mountain Array

Find in a Mountain Array: Early Stopping and Cache

Exercise

Rotated array

Exercise

K Closest Elements

Sorted Array with Unknown Size

Exercise

  • Leetcode (Premium) - 702. Search in a Sorted Array of Unknown Size: link grok

Others

  • 53.2 0 ~ n-1中缺失的数字 268. Missing Number
  • 53.3 排序数组中数值和下标相等的元素

Cyclic Sort

Overview

grok

Missing Number

Solution: Cyclic Sort

Solution: Bitwise XOR

Exercise

TODO Grokking 未学习

Sorting and Selection