two_pointers

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

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+)

PreviousrecursionNextOffline processing

Last updated