two_pointers.md

• Two Pointers
  • Sliding window
  • Begin and end type
    • Greedy
  • Partition type
  • Slow and fast
  • Window type
  • Sliding window : Distinct Characters
  • Two pointers for two seuqences

Two Pointers

011.Container-With-Most-Water (M+)
015.3Sum (M)
016.3Sum-Closet (M)
018.4Sum (M)
259.3Sum-Smaller (M+)
030.Substring-with-Concatenation-of-All-Words (H)
075.Sort-Colors (M+)
026.Remove Duplicates from Sorted Array (H-)
080.Remove Duplicates from Sorted Array II (H)
209.Minimum-Size-Subarray-Sum (M)
088.Merge Sorted Array (M)
283.Move-Zeroes (M)
141.Linked-List-Cycle (E+)
142.Linked-List-Cycle-II (M+)
360.Sort-Transformed-Array (M)
713.Subarray-Product-Less-Than-K (M+)
923.3Sum-With-Multiplicity (H-)
1234.Replace-the-Substring-for-Balanced-String (H-)
1498.Number-of-Subsequences-That-Satisfy-the-Given-Sum-Condition (H-)
1574.Shortest-Subarray-to-be-Removed-to-Make-Array-Sorted (H-)
1687.Delivering-Boxes-from-Storage-to-Ports (H)
1793.Maximum-Score-of-a-Good-Subarray (M+)

Sliding window

532.K-diff-Pairs-in-an-Array (H-)
611.Valid-Triangle-Number (M+)
1004.Max-Consecutive-Ones-III (M)
1052.Grumpy-Bookstore-Owner (M)
1838.Frequency-of-the-Most-Frequent-Element (H-)
395.Longest-Substring-with-At-Least-K-Repeating-Characters (H)
1763.Longest-Nice-Substring (H)

Begin and end type

• example problems: two sum (sorted), three sum, four sum, three sum closest, three sum smaller

if A[i] and A[j] satisfy some condition:
  j--; // do not need to consider pairs composed of [i+1, j-1] and j
  // do something
elif A[i] and A[j] do not satisfy some condition:
  i++; // do not need to consider pairs composed of [i+1, j-1] and i
  // do something
else:
  // do something
  i++ or j--

• Example problem: KSum

def kSum(kVal: int, target: int, startIndex: int, nums: List[int]) -> List[List[int]]:
  result = []
  if kVal == 0:
    if target == 0:
      result.append([]);
    return result;

  for i in range(startIndex, len(nums) - kVal + 1):
    if (i > startIndex) and (nums[i] == nums[i - 1]):
      continue;

    for partialResult in kSum( kVal - 1, target - nums[i], i + 1, nums )
        partialResult.add( 0, nums[i] );
        result.add( partialResult );

  return result;

Greedy

• Squeeze the biggest first 1580.Put-Boxes-Into-the-Warehouse-II (H-)
• Put in the first 1798.Maximum-Number-of-Consecutive-Values-You-Can-Make/Readme.md (H-)

Partition type

• example problems: two sum (sorted), three sum, four sum, three sum closest, three sum smaller

# int[] input, int left, int right
pivot = input[(left+right)/2];
while i <= j:
    while input[i] < pivot:
        i++

    while input[j] > pivot:
        j--

    if i <= j:
        swap(data, i, j);
        i++;
        j--;

Slow and fast

• Find the middle of linked list
• Find linked list cycle

Window type

• Improve naive two level for loop to for-outer loop + while inner loop
• E.g. minimum window substring, minimum size subarray sum, Longest substring with at most K distinct characters, Longest substring without repeating characters

for i in range(n):
  while j < n:
    # update j status
    if satisfy some condition:
      j++
    else:
      break
  }
}

Sliding window : Distinct Characters

076.Minimum-Window-Substring (M+)
003.Longest-Substring-Without-Repeating-Character (E+)
159.Longest-Substring-with-At-Most-Two-Distinct-Characters(H-)
340.Longest-Substring-with-At-Most-K-Distinct-Characters (H)
992.Subarrays-with-K-Different-Integers (H-)

Two pointers for two seuqences

986.Interval-List-Intersections (M)
1229.Meeting-Scheduler (M+)
1537.Get-the-Maximum-Score (H-)
1577.Number-of-Ways-Where-Square-of-Number-Is-Equal-to-Product-of-Two-Numbers (H-)
1775.Equal-Sum-Arrays-With-Minimum-Number-of-Operations (M+)
1868.Product-of-Two-Run-Length-Encoded-Arrays (M+)