yitonghe00

// Two pointer solution: one pointer for each array
// Time：O(m * n) where m is the length of haystack and n is the length of needle, 3ms
// Space: O(1), 37mb
class Solution {
    public int strStr(String haystack, String needle) {
        // Corner case
        if(needle.length() == 0) return 0;
        
        // hp points to char in haystack, np points to char in needle
        for(int hp = 0, np = 0; hp < haystack.length(); hp++) {

yitonghe00

// Two pointer solution
// Time: O(n), 0ms
// Space: O(1), 35.1mb
class Solution {
    public void sortColors(int[] nums) {
        // 2 pointers: [0, l) - 0, [l, r] - 1, [r, nums.length - 1] - 2
        // m for traversing
        int l = 0, r = nums.length - 1, m = 0;
        
        while(m <= r) {

yitonghe00

// Two pointer: read/write pointers (slow/fast pointers)
// Time: O(n), 0ms
// Space: O(1), 37.2mb
class Solution {
    public int removeDuplicates(int[] nums) {
        // Corner cases
        if(nums.length < 3) return nums.length;
        
        int w = 2, r = 2;
        // Read pointer moves every loop

yitonghe00

// Two pointer solution: read/write (end/end) pointer
// Time: O(m + n), 0ms
// Space: O(1), 36.3mb
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // Two read pointers for nums1 and nums2, and 1 write pointer for nums1
        int r1 = m - 1, r2 = n - 1, w = m + n - 1;
        
        while(w >= 0) {
            // **: Merge two into one: handle the cases when one of them is out of elements 658 #1.1

yitonghe00

// Two pointer solution
// Time: O(n), 4ms
// Space: O(1), 37.5mb
class Solution {
    public boolean isPalindrome(String s) {
        int l = 0, r = s.length() - 1;
        
        while(l < r) {
            // Ignore non alphanumeric characters
            while(l < r && !Character.isLetterOrDigit(s.charAt(l))) {

yitonghe00

// Two pointer solution: begin/end pointer
// Time: O(n), 1ms
// Space: O(1), 37.9mb
class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0, right = numbers.length - 1;
        
        while(left < right) {
            if(numbers[left] + numbers[right] == target) {
                return new int[]{left + 1, right + 1};

yitonghe00

// Two pointer solution: min/max substring template
// Time: O(n), 1ms
// Space: O(1), 37.9mb
class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        // Window is [beign, end)
        int begin = 0, end = 0, minLen = nums.length + 1, sum = 0;
        while(end < nums.length) {
            // Expand window to the right
            sum += nums[end++];

yitonghe00

// Two pointer solution: slow/fast pointers
// Time: O(n), 0ms
// Space: O(1), 36mb
public class Solution {
    public ListNode detectCycle(ListNode head) {
        // Slow fast pointer
        ListNode slow = head, fast = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

yitonghe00

// Two pointer solution: slow/fast pointers
// Time: O(n), 0ms
// Space: O(1), 36.9mb
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast) return true;

yitonghe00

// Two pointer solution: slow/fast pointer
// Time: O(n), 0ms
// Space: O(1), 36.8mb
class Solution {
    public int findDuplicate(int[] nums) {
        // Treat the nums as a singly linked list
        // The duplicate num is where the cycle begins
        int slow = 0, fast = 0;
        while(true) {
            slow = nums[slow];