two-pointers-problems.md

Two Pointers

Left/Right Pointers

Problem	Difficulty	Notes
344. Reverse String	Easy
1750. Minimum Length of String After Deleting Similar Ends	Medium (1501)	Shrink both ends, avoid overlapping.
11. Container With Most Water	Medium	Why moving shorter pointer inward?
658. Find K Closest Elements	Medium	Shring window from longer distance.
948. Bag of Tokens	Medium (1762)	Simulate greedily.
1775. Equal Sum Arrays With Minimum Number of Operations	Medium (1850)

• Solved: https://leetcode.com/problems/valid-palindrome/description/ e
• https://leetcode.com/problems/apply-operations-to-an-array/description/ 1223
• https://leetcode.com/problems/number-of-subsequences-that-satisfy-the-given-sum-condition/description/ 2276

Read/Write Pointers

In this section, please pay attention to the definition of write pointer. Always have a clear definition of write pointer:

• The next position to write.
• The current written position.

Problem	Difficulty	Notes
27. Remove Element	Easy	Overwrite.
283. Move Zeroes	Easy	Read non-zero, write to front.
977. Squares of a Sorted Array	Easy
26. Remove Duplicates from Sorted Array	Easy	Check nums[write - 1] != nums[read].
80. Remove Duplicates from Sorted Array II	Medium	Generalize to allow duplicate, check nums[write - k] != nums[read].
1089. Duplicate Zeros	Easy (1262)
905. Sort Array By Parity	Easy	Write even to front or write odd to back.
922. Sort Array By Parity II	Easy (1173)	Find misplaced even/odd and swap
202. Happy Number	Easy	Cycle detection.

nSum Problems

Problem	Difficulty	Notes
1. Two Sum	Easy
167. Two Sum II - Input Array Is Sorted	Medium
1679. Max Number of K-Sum Pairs	Medium (1345)	Count two sum == k.
15. 3Sum	Medium	How to avoid duplicate triplets?
16. 3Sum Closest	Medium
633. Sum of Square Numbers	Medium	Binary search or two pointers or hash table.
923. 3Sum With Multiplicity	Medium (1710)	(15. 3Sum two pointers) or (1. Two Sum hash table technique).

Two Pointers on Two Sorted Sequences

• Fix one pointer and search the other from sorted sequence.
• Most of the problems can be sovled by binary search.

Problem	Difficulty	Note
2300. Successful Pairs of Spells and Potions	Medium (1476)	Fix spells, binary search on sorted potions.
826. Most Profit Assigning Work	Medium (1708)	Sort + prefix max + binary search or two pointers.
1574. Shortest Subarray to be Removed to Make Array Sorted	Medium (1931)	Fix i, binary search j.
475. Heaters	Medium	Find the closest heater for each house.
633. Sum of Square Numbers	Medium	Binary search, two pointers, hash table.
1855. Maximum Distance Between a Pair of Values	Medium (1514)	Fix i, binary search j.

3 Pointers

Problem	Difficulty	Notes
611. Valid Triangle Number	Medium	How to iterate the 3 pointers and update count correctly? Sort + fix i, search with two pointers or binary search.
2563. Count the Number of Fair Pairs	Medium (1720)	count(<=R) - count(<=L-1). Two pointers.

• https://leetcode.com/problems/number-of-arithmetic-triplets/description/ 1203
• https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/description/ 1817
• https://leetcode.com/problems/count-subarrays-with-fixed-bounds/description/ 2092

Two Sequences Matching

Problem	Difficulty	Notes
88. Merge Sorted Array	Easy
925. Long Pressed Name	Easy	Implementation details.
844. Backspace String Compare	Easy (1227)	Scan from end, skip #.
2337. Move Pieces to Obtain a String	Medium (1693)	Match L/R positionally.
777. Swap Adjacent in LR String	Medium (1938)	(Same as 2337.)

• https://leetcode.com/problems/multiply-strings/description/
• https://leetcode.com/problems/minimum-common-value/description/ 1249
• https://leetcode.com/problems/merge-two-2d-arrays-by-summing-values/description/ 1281
• https://leetcode.com/problems/adding-spaces-to-a-string/description/ 1315
• https://leetcode.com/problems/get-the-maximum-score/description/ 1961

Intersection

Problem	Difficulty
350. Intersection of Two Arrays II	Easy
986. Interval List Intersections	Medium

• https://leetcode.com/problems/intersection-of-two-arrays/submissions/ e
• https://leetcode.com/problems/minimum-index-sum-of-two-lists/description/ e

Subsequence

Problem	Difficulty
392. Is Subsequence	Easy

• https://leetcode.com/problems/longest-word-in-dictionary-through-deleting/description/
• https://leetcode.com/problems/append-characters-to-string-to-make-subsequence/description/ 1362

Group By Consecutive (分组循环)

Problem	Difficulty	Notes
485. Max Consecutive Ones	Easy
1446. Consecutive Characters	Easy (1165)	Longest same character streak.
1578. Minimum Time to Make Rope Colorful	Medium (1574)
228. Summary Ranges	Easy	Longest increasing streak.
674. Longest Continuous Increasing Subsequence	Easy
2760. Longest Even Odd Subarray With Threshold	Medium
1887. Reduction Operations to Make the Array Elements Equal	Medium (1427)
845. Longest Mountain in Array	Medium (1436)

TODO: To understand 1887. Reduction Operations to Make the Array Elements Equal, and 845. Longest Mountain in Array.

• Solved,https://leetcode.com/problems/count-number-of-homogenous-substrings/ 1490, similar to 1446. Consecutive Characters
• Solved, https://leetcode.com/problems/count-alternating-subarrays/description/
• https://leetcode.com/problems/unique-substrings-in-wraparound-string/description/

Group By Edges

Problem	Difficulty	Notes
978. Longest Turbulent Subarray	Medium (1393)
413. Arithmetic Slices	Medium

Explanation

• 11. Container With Most Water
• 658. Find K Closest Elements
• 611. Valid Triangle Number
• 475. Heaters
• 1775. Equal Sum Arrays With Minimum Number of Operations
• 15. 3Sum
• 16. 3Sum Closest
• 923. 3Sum With Multiplicity
• 26. Remove Duplicates from Sorted Array
• 80. Remove Duplicates from Sorted Array II
• 1574. Shortest Subarray to be Removed to Make Array Sorted