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;
}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--;
}
}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()))
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)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 TrueUse 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 += 1Instead 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 += 1def 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] 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 idef 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 + 1One 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 i844. Backspace String Compare
Word Consisted by Another Word
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 resFollow 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?
Store the two strings in distributed system(whether self designed or not), then using MapReduce technique to solve the problem;
Processing the Strings by chunk, which fits the memory, then deal with each chunk of data at a time;
Processing the Strings by streaming, then check.
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() 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" 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 resultpublic 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
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 candUse 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;
}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
res = [ 15 ] then product = 2 * 1 = 2
res = [ . 30,15 ] then product = 1 * 2
res = [ 6, 30,15 ] then product = 5 * 2 = 10
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
This question can be solved by sort, which takes O(nlogn). A better way is to use a slow and fast pointer:
Start with index 0, find the point where two pointers meet. That indicates that there is a cycle in the array.
Move one pointer to the start point. Move both pointers forward in the same speed until they meet again.
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
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;
}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
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;
}Last updated
Was this helpful?