Two Pointers

167. Two Sum II - Input array is sorted

Use two pointers to move from beginning and end. Until two pointers converge:

• Move end pointer when the sum of two numbers at the pointers are larger than the target.

• Move start pointer when the sum is smaller than the target

• return pointer positions when the sum equals to the target

public int[] twoSum(int[] numbers, int target) {
    int i = 0;
    int j = numbers.length - 1;
    while (i < j) {
        if (numbers[i] + numbers[j] == target) {
            return new int[]{i + 1, j + 1};
        } else if (numbers[i] + numbers[j] < target) {
            i++;
        } else {
            j--;
        }
    }
    return null;
}

344. Reverse String

public void reverseString(char[] s) {
    int i = 0, j = s.length - 1;
    while (i < j) {
        char temp = s[i];
        s[i] = s[j];
        s[j] = temp;
        i++;
        j--;
    }
}

151. Reverse Words in a String

Split words by " ". Reverse order by using two pointers technique.

Java:

public String reverseWords(String s) {
    String[] sArr = s.trim().split(" ");
    StringBuilder sb = new StringBuilder();
    for (int i = sArr.length - 1; i >= 0; i--) {
        if (!sArr[i].isEmpty()) {
            sb.append(sArr[i]).append(" ");
        }
    }
    return sb.toString().trim();
}

Python:

 def reverseWords(self, s: str) -> str:
        # strs = s.strip().split(" ")
        # i = 0
        # j = len(strs) - 1
        # while i < j:
        #     strs[i], strs[j] = strs[j], strs[i]
        #     i += 1
        #     j -= 1
   return " ".join(reversed(s.split()))

345. Reverse Vowels of a String

Save all vowels to a set. Use two pointers to move from beginning and end. Keep moving the pointer until the pointer encounter a vowel character. Swap vowels.

    def reverseVowels(self, s: str) -> str:
        _set = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'}
        i = 0
        j = len(s) - 1
        strs = list(s)
        while i < j :
            while i < j and strs[i] not in _set :
                i += 1
            while i < j and strs[j] not in _set :
                j -= 1
            strs[i], strs[j] = strs[j], strs[i]
            i += 1
            j -= 1
        return ''.join(strs)

125. Valid Palindrome

Use two pointers to move from beginning and end. Keep moving the pointer until the pointer encounter an alphanumeric character. Check if both characters are the same.

    def isPalindrome(self, s: str) -> bool:
        i = 0
        j = len(s) - 1
        s = list(s)
        while i < j:
            while i < j and not s[i].isalnum():
                i += 1
            while i < j and not s[j].isalnum():
                j -= 1
            if s[i].lower() != s[j].lower():
                return False
            i += 1
            j -= 1
        return True

283. Move Zeroes

Use two pointers to start both at the beginning of array. i to count the numbers of non-zero elements, j to traverse to find none zero elements. When j detects a candidate, swap with i, i++.

    def moveZeroes(self, nums: List[int]) -> None:
     	   i = 0
            for j in range(len(nums)):
                if nums[j] != 0:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1

Instead of swap, filling the rest of i with 0 also works. This is because i counts the number of non-zeros, the rest would be zeros.

    def moveZeroes(self, nums: List[int]) -> None:
        i = 0
        for j in range(0, len(nums)):
            if nums[j] != 0 :
                nums[i] = nums[j]
                i += 1
        while i < len(nums):
            nums[i] = 0
            i += 1

88. Merge Sorted Array

def merge(self, nums1: List[int], m: int, 
           nums2: List[int], n: int) -> None:
    i = m - 1
    j = n - 1
    k = m + n - 1
    while i >= 0 and j >= 0:
        if nums2[j] > nums1[i]:
            nums1[k] = nums2[j]
            j -= 1
        else :
            nums1[k] = nums1[i]
            i -= 1
        k -= 1
    nums1[:j + 1] = nums2[:j + 1]

27. Remove Element

   def removeElement(self, nums: List[int], val: int) -> int:
        i = 0
        for j in range(0, len(nums)):
            if nums[j] != val:
                nums[i] = nums[j]
                i += 1
        return i

26. Remove Duplicates from Sorted Array

def removeDuplicates(self, nums: List[int]) -> int:
    i = 0
    for j in range(0, len(nums)) :
        if nums[i] != nums[j]:
            i += 1
            nums[i] = nums[j]
    return i + 1

80. Remove Duplicates from Sorted Array II*

One j pointer to loop over the array, the other pointer stores the right sequence of the result, which satisfy that 2 digits behind was smaller than number at j. If the numbers one those two pointers are the same, it means that there are 3 or more than 3 same numbers, thus move j only until you find the next larger element.

For example:

i j

[1,1,1,2,2,4,5,6,6,6]

This is a situation to replace the number at i with the number at j.

def removeDuplicates(self, nums: List[int]) -> int:
    i = 0
    for j in range(0, len(nums)) :
        if i < 2 or nums[i - 2] < nums[j]:
            nums[i] = nums[j]
            i += 1
    return i

844. Backspace String Compare

Word Consisted by Another Word

349. Intersection of Two Arrays & 350. Intersection of Two Arrays II

Use set to store the shorter array and check on the array.

    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        _set = set() 
        for n in nums1:
            _set.add(n)
        res = set()
        for n in nums2:
            if n in _set: 
                res.add(n)
        return list(res)

Use HashMap on 350 to count each element. If sorted. Use two pointers start from beginning.

   def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()
        nums2.sort()
        res = []
        i = 0
        j = 0
        while i < len(nums1) and j < len(nums2):
            if nums1[i] == nums2[j]:
                res.append(nums1[i])
                i += 1
                j += 1
            elif nums1[i] < nums2[j]:
                i += 1
            else:
                j += 1
        return res

Follow up:

What if nums1's size is small compared to nums2's size? Which algorithm is better? HashMap

What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

1. Store the two strings in distributed system(whether self designed or not), then using MapReduce technique to solve the problem;

2. Processing the Strings by chunk, which fits the memory, then deal with each chunk of data at a time;

3. Processing the Strings by streaming, then check.

189. Rotate Array

Flip 0 to n - k and flip n - k to n, then flip the entire array

    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        nums[0:n-k] = nums[0:n-k][::-1]
        nums[n-k:] = nums[n-k:][::-1]
        nums = nums.reverse()

299. Bulls and Cows

    def getHint(self, secret: str, guess: str) -> str:
        bullset = set()
        count = {}
        bull = 0
        for i in range(0, len(secret)):
            if secret[i] == guess[i]: 
                bull += 1
                bullset.add(i)
            else :
                if secret[i] in count:
                    count[secret[i]] += 1
                else:
                    count[secret[i]] = 1
        cow = 0
        for i in range(0, len(guess)):
            if i not in bullset:
                if guess[i] in count and count[guess[i]] > 0:
                    cow += 1
                    count[guess[i]] -= 1
        return str(bull) + "A" + str(cow) + "B"

11. Container With Most Water

    def maxArea(self, height: List[int]) -> int:
        i = 0
        j = len(height) - 1
        result = 0
        while i < j:
            result = max(result, min(height[i], height[j]) * (j - i))
            if height[i] < height[j]:
                i += 1
            else:
                j -= 1
        return result

42. Trapping Rain Water

public int trap(int[] height) {
    int LMax = 0, RMax = 0;
    int L = 0, R = height.length - 1;
    int res = 0;
    while (L < R) {
        if (height[L] < height[R]) {
            if (height[L] > LMax) {
                LMax = height[L];
            } else {
                res += LMax - height[L];
            }
            L++;
        } else {
            if (height[R] > RMax) {
                RMax = height[R];
            } else {
                res += RMax - height[R];
            }
            R--;
        }
    }
    return res;
}

217. Contains Duplicate

219. Contains Duplicate II

220. Contains Duplicate III

277. Find the Celebrity

    def findCelebrity(self, n: int) -> int:
        cand = 0
        for i in range(1, n):
            if not knows(i, cand):
                cand = i
        for i in range(n):
            if cand != i and (not knows(i, cand) or knows(cand, i)):
                return -1
        return cand

75. Sort Colors

Use L and R on each k

    public void sortColors(int[] nums) {
        int L = 0, R = nums.length - 1, k = 0;
        while (k <= R) {
            if (nums[k] == 0) {
                swap(nums, L++, k++);
            } else if (nums[k] == 2) {
                swap(nums, R--, k);
            } else {
                k++;
            }
        }
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

238. Product of Array Except Self

Since the requirement states "can't use division", we can only generate the result by multiplication. It starts to build an array with all product of the elements before current. For example:

Array = [3,5,1,2], res start withs [1,1,1, 1], then res[i] = res[i - 1] * array[i - 1]

res = [1, 3, 15, 15]

Then multiply from the right, with a start variable as 1, keeps the variable as all the products along the way.

product = 1

1. res = [ 15 ] then product = 2 * 1 = 2

2. res = [ . 30,15 ] then product = 1 * 2

3. res = [ 6, 30,15 ] then product = 5 * 2 = 10

4. res = [10, 6, 30,15 ]

This method is due to multiply all elements before the current product from left, then multiply all products from the right. It skips the current element.

public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    Arrays.fill(res, 1);
    for (int i = 1; i < n; i++) {
        res[i] = res[i - 1] * nums[i - 1];
    }
    int product = 1;
    for (int i = n - 1; i >= 0; i--) {
        res[i] = res[i] * product;
        product *= nums[i];
    }
    return res;
}

334. Increasing Triplet Subsequence

287. Find the Duplicate Number

This question can be solved by sort, which takes O(nlogn). A better way is to use a slow and fast pointer:

Floyd's Tortoise and Hare

1. Start with index 0, find the point where two pointers meet. That indicates that there is a cycle in the array.

2. Move one pointer to the start point. Move both pointers forward in the same speed until they meet again.

3. Return the index, which is the entrance of the cycle

Refer to Linked List Cycle II

    public int findDuplicate(int[] nums) {
        int slow = 0;
        int fast = 0;
        while (true) {
            slow = nums[slow];
            fast = nums[nums[fast]];
            if (slow == fast) break;
        }
        slow = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }

169. Majority Element

229. Majority Element II

Trapping Rain Water

41. First Missing Positive

243. Shortest Word Distance

public int shortestDistance(String[] words, String word1, String word2) {
    int ind1 = -1;
    int ind2 = -1;
    int min = Integer.MAX_VALUE;
    for (int i = 0 ; i < words.length; i++) {
        if (words[i].equals(word1)) {
            ind1 = i;
        } else if (words[i].equals(word2)) {
            ind2 = i;
        }
        if (ind1 != -1 && ind2 != -1) min = Math.min(min, Math.abs(ind1 - ind2));
    }
    return min;
}

244. Shortest Word Distance II

Map<String, List<Integer>> map;
public WordDistance(String[] words) {
    map = new HashMap<>();
    for (int i = 0; i < words.length; i++) {
        map.putIfAbsent(words[i], new ArrayList<>());
        map.get(words[i]).add(i);
    }
}

public int shortest(String word1, String word2) {
    List<Integer> l1 = map.get(word1);
    List<Integer> l2 = map.get(word2);
    int i = 0, j = 0;
    int min = Integer.MAX_VALUE;
    while (i < l1.size() && j < l2.size()) {
        int a = l1.get(i), b = l2.get(j);
        min = Math.min(min, Math.abs(a - b));
        if (a < b) {
            i++;
        } else {
            j++;
        }
    }
    return min;
}

245. Shortest Word Distance III

611. Valid Triangle Number

55. Jump Game

45. Jump Game II

274. H-Index

275. H-Index II

128. Longest Consecutive Sequence

697. Degree of an Array

public int findShortestSubArray(int[] nums) {
    Map<Integer, Integer> left = new HashMap<>();
    Map<Integer, Integer> right = new HashMap<>();
    Map<Integer, Integer> count = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int num = nums[i];
        if (!left.containsKey(num)) {
            left.put(num, i);
        }
        right.put(num, i);
        count.put(num, count.getOrDefault(num, 0) + 1);
    }

    int max = Collections.max(count.values());
    int res = nums.length;
    for (int key : count.keySet()) {
        if (count.get(key) == max) {
            res = Math.min(res, right.get(key) - left.get(key) + 1);
        }
    }
    return res;
}

2444. Count Subarrays With Fixed Bounds

Explanation: https://leetcode.com/problems/count-subarrays-with-fixed-bounds/editorial

long long countSubarrays(vector<int>& nums, int minK, int maxK) {
    int left = -1;
    int minPos = -1, maxPos = -1;
    long res = 0;
    for (int i = 0; i < nums.size(); ++i) {
        if (nums[i] < minK || nums[i] > maxK) {
            left = i;
        }
        if (nums[i] == minK) minPos = i;
        if (nums[i] == maxK) maxPos = i;
        res += max(0, min(minPos, maxPos) - left);
    }
    return res;
}