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