- Published on
Leetcode Pattern 2 Two Pointers
- Authors
- Name
- Yinhuan Yuan
Introduction
The two pointers algorithm involves using two distinct pointers, usually starting from different positions in a data structure, and moving them according to specific rules to achieve a desired outcome. These pointers can either converge towards each other, move in the same direction, or diverge, depending on the problem at hand. The goal is to utilize these pointers to traverse the data structure in an optimal way, often reducing the time complexity from O(n^2) to O(n) in the process.
The sliding window technique is a specific case of the two pointers pattern. However, we classify sliding window separately because its solving methods differ slightly. The two primary categories of the two pointers pattern are:
Converging Pointers:
This technique is often used in problems where you need to find a pair or a range that meets a specific condition. The pointers start at opposite ends of the array or string and move towards each other. The key difference between this category and the sliding window is that in converging pointers, the pointers begin at the first and last elements and move in opposite directions. The goal is to find a pair or range that satisfies the given condition.
function threeSumClosest(nums: number[], target: number): number { const n = nums.length; nums.sort((a: number, b: number) => a - b); // let closestSum = Infinity; for (let i = 0; i < n - 2; i++) { let left = i + 1; let right = n - 1; while (left < right) { const currentSum = nums[i] + nums[left] + nums[right]; if (currentSum === target) { // return currentSum; // or Add the indices to the final results. } if (currentSum > target) { right -= 1; } else if (currentSum < target) { left += 1; } } } return closestSum; };Fast and Slow Pointers:
Also known as the "tortoise and hare" technique, this approach is particularly useful for detecting cycles in data structures like linked lists. In this method, the fast pointer moves at twice the speed of the slow pointer. If there is a cycle in the linear data structure, the fast pointer will eventually catch up to the slow pointer after traversing the cycle, confirming the presence of a cycle. If there is no cycle, the fast pointer will reach the end, while the slow pointer will be in the middle of the list. Now, let's assume that there is a cycle. Let
xbe the distance from the starting point to the start of the cycle,ybe the distance from the start of the cycle to the meeting point, andLbe the perimeter of the cycle. The slow pointer travels a distance ofx + y, while the fast pointer travelsx + L + y. Since the fast pointer moves twice as fast as the slow pointer, we have the equation2 * (x + y) = x + L + y. Solving this, we find thatx + y = L. Therefore, if we walk a distance ofxfrom the meeting point, we will reach the start of the cycle. To find this point, we can start another pointer from the starting point and walk in the same speed. When both of them met, we have reach the starting of cycle.function hasCycle(head: ListNode | null): boolean { if (head === null || head.next === null) return false; let slow = head; let fast = head; while (true) { [fast, slow] = [fast.next.next, slow.next]; if (slow === fast || fast === null || fast.next === null) { break; } } if (slow !== fast) return false; // If we start from head again and move it as the same speed as slow foreward, we will reach the starting point of circle. let ans = head; while (slow !== ans) { [slow, ans] = [slow.next, ans.next]; } return slow; };
- 1. Converging Pointers Problems
- 1. Two Sum[Easy]
- 167. Two Sum II - Input Array Is Sorted[Medium]
- 15. 3Sum[Medium]
- 16. 3Sum Closest[Medium]
- 259. 3Sum Smaller[Medium]
- 18. 4Sum[Medium]
- 75. Sort Colors[Medium]
- 1574. Shortest Subarray to be Removed to Make Array Sorted[Medium]
- 26. Remove Duplicates from Sorted Array[Easy]
- 27. Remove Element[Easy]
- 977. Squares of a Sorted Array[Easy]
- 2. Fast and Slow Pointers Problems
1. Converging Pointers Problems
1. Two Sum[Easy]
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?
Solution: This problem can be solved using a hash map with a time complexity of O(N) and a space complexity of O(N). However, we can also use the two converging pointers approach. First, we sort the array by values while keeping track of the original indices. Then, we place one pointer at the beginning of the array and the other at the end. We calculate the sum of the values at these two positions. If the sum equals the target, the original indices corresponding to these pointers are the solution. If the sum is greater than the target, we need to decrease the total, so we move the right pointer one step to the left. If the sum is less than the target, we need to increase the total, so we move the left pointer one step to the right. We continue this process until the left pointer surpasses the right pointer.
function twoSum(nums: number[], target: number): number[] {
const n = nums.length;
const numbers = nums.map((num, index) => [num, index]);
numbers.sort((a, b) => {
if (a[0] !== b[0]) {
return a[0] - b[0];
}
return a[1] - b[1];
});
let left = 0;
let right = n - 1;
while (left < right) {
const total = numbers[left][0] + numbers[right][0];
if (total === target) {
return [numbers[left][1], numbers[right][1]];
}
if (total > target) {
right -= 1;
} else {
left += 1;
}
}
return [];
};
Here's the solution using a hash map, which has a time complexity of O(N).
function twoSum(nums: number[], target: number): number[] {
const hashTable: Map<number, number> = new Map<number, number>();
let ans: number[] = [];
nums.forEach((num, index) => {
if (hashTable.has(num)) {
ans = [hashTable.get(num), index];
} else {
hashTable.set(target - num, index);
}
});
return ans;
};
167. Two Sum II - Input Array Is Sorted[Medium]
Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.
Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.
The tests are generated such that there is exactly one solution. You may not use the same element twice.
Your solution must use only constant extra space.
function twoSum(numbers: number[], target: number): number[] {
const n = numbers.length;
let lo = 0;
let hi = n - 1;
while (lo < hi) {
if (numbers[lo] + numbers[hi] === target) {
return [lo + 1, hi + 1];
} else if (numbers[lo] + numbers[hi] < target) {
lo += 1;
} else {
hi -= 1;
}
}
};
15. 3Sum[Medium]
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
Solution: First, we sort the array nums. Then, for each element in the array, if it differs from the previous element, we check whether we can find two elements after it whose sum equals the negative of the current element. We only check elements different from the previous one to avoid duplication. Finding two elements that sum to a specific value becomes a Two Sum problem, which can be solved using two converging pointers. As we move these pointers, we skip positions with the same value as the previous ones if they have already been included in the results, thus avoiding possible duplicates.
The time complexity is O(N^2) and the space complexity is O(1).
function threeSum(nums: number[]): number[][] {
const n = nums.length;
const target = 0;
nums.sort((a, b) => a - b);
const triplets: number[][] = [];
for (let i = 0; i < n - 2; i++) {
// Avoid duplicates
if(i > 0 && nums[i - 1] === nums[i]) {
continue;
}
let left = i + 1;
let right = n - 1;
while (left < right) {
const currentSum = nums[i] + nums[left] + nums[right];
if (currentSum === target) {
triplets.push([nums[i], nums[left], nums[right]]);
// Avoid duplicates
left++;
right--;
while (left < right && nums[left - 1] === nums[left]) {
left++;
}
while (left < right && nums[right + 1] === nums[right]) {
right--;
}
}
if (currentSum > target) {
right -= 1;
} else if (currentSum < target) {
left += 1;
}
}
}
return triplets;
};
16. 3Sum Closest[Medium]
Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.
Return the sum of the three integers.
You may assume that each input would have exactly one solution.
Solution: Similar to 15. 3Sum [Medium], we first sort the array. For each element, we use the converging two pointers method to find two other elements. In each step, we update the final result if the sum of these three elements is closer to the target. If the sum of the three elements equals the target, we return it immediately.
function threeSumClosest(nums: number[], target: number): number {
const n = nums.length;
nums.sort((a: number, b: number) => a - b);
let closestSum = Infinity;
for (let i = 0; i < n - 2; i++) {
let left = i + 1;
let right = n - 1;
while (left < right) {
const currentSum = nums[i] + nums[left] + nums[right];
if (currentSum === target) {
return currentSum;
}
if (currentSum > target) {
right -= 1;
} else if (currentSum < target) {
left += 1;
}
if (Math.abs(currentSum - target) < Math.abs(closestSum - target)) {
closestSum = currentSum;
}
}
}
return closestSum;
};
259. 3Sum Smaller[Medium]
Given an array of n integers nums and an integer target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.
Solution: Similar to 15. 3Sum [Medium], we start by sorting the array. For each element, we use the converging two pointers method to find two other elements. If we find indices i, left, and right where the sum is less than the target, it indicates that all elements from left + 1 to right can be the third element because their values are less than or equal to the value at right. The count of these combinations is right - left. We add this count to the final result.
function threeSumSmaller(nums: number[], target: number): number {
const n = nums.length;
nums.sort((a: number, b: number) => a - b);
let count = 0;
for(let i = 0; i < n - 2; i++) {
let left = i + 1;
let right = n - 1;
while (left < right) {
const currentSum = nums[i] + nums[left] + nums[right];
if (currentSum < target) {
// If currentSum is less than target, it means the right pointer can be left + 1, left + 2, ..... right.
// The total count is right - (left + 1) + 1 = right - left
count += right - (left + 1) + 1;
left += 1;
} else {
right -= 1;
}
}
}
return count;
};
18. 4Sum[Medium]
Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:
0 <= a, b, c, d < n a, b, c, and d are distinct. nums[a] + nums[b] + nums[c] + nums[d] == target You may return the answer in any order.
Solution: Similar to 15. 3Sum [Medium], we begin by sorting the array. We then need to add additional layers of loops to account for the solutions found in 3Sum.
function fourSum(nums: number[], target: number): number[][] {
const n = nums.length;
nums.sort((a: number, b: number) => a - b);
const quadruplets: number[][] = [];
for (let i = 0; i < n - 3; i++) {
// Avoid duplicates
if (i > 0 && nums[i] === nums[i - 1]) continue;
for (let j = i + 1; j < n - 2; j++) {
// Avoid duplicates
if (j > i + 1 && nums[j] === nums[j - 1]) continue;
let left = j + 1;
let right = n - 1;
while (left < right) {
const currentSum = nums[i] + nums[j] + nums[left] + nums[right];
if (currentSum === target) {
quadruplets.push([nums[i], nums[j], nums[left], nums[right]]);
// Avoid duplicates
while (left < right && nums[left] === nums[left + 1]) {
left += 1;
}
while (left < right && nums[right] === nums[right - 1]) {
right -= 1;
}
left += 1;
right -= 1;
} else if (currentSum > target) {
right -= 1;
} else {
left += 1;
}
}
}
}
return quadruplets;
};
75. Sort Colors[Medium]
Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.
We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.
You must solve this problem without using the library's sort function.
Follow up: Could you come up with a one-pass algorithm using only constant extra space?
Solution: The simple solution is to use counting sort.
function sortColors(nums: number[]): void {
const n = nums.length;
const count: number[] = Array(3).fill(0);
for(let i = 0; i < n; i++) {
count[nums[i]] += 1;
}
let k = 0;
for (let i = 0; i < 3; i++) {
for (let j = 0; j < count[i]; j++) {
nums[k] = i;
k += 1;
}
}
};
To solve this problem with one-pass algorithm using only constant extra space, you can use the Dutch National Flag algorithm, which is a single-pass algorithm that sorts the array in-place using constant space. This algorithm works by maintaining three pointers:
low: Tracks the position where the next 0 (red) should be placed.mid: Traverses the array and is used to identify the current element being inspected.high: Tracks the position where the next 2 (blue) should be placed.
Here's the algorithm:
- Initialize
lowandmidto 0, andhighton - 1(wherenis the length of the array). - Iterate over the array with
midfrom the start tohigh. - Depending on the value at
nums[mid]:- If
nums[mid]is 0, swapnums[mid]withnums[low], then increment bothlowandmid. - If
nums[mid]is 1, just incrementmid. - If
nums[mid]is 2, swapnums[mid]withnums[high], then decrementhigh(don't incrementmidbecause the newnums[mid]needs to be inspected).
- If
function sortColors(nums: number[]): void {
const n = nums.length;
let left = 0;
let mid = 0;
let right = n - 1;
while (mid <= right) {
if (nums[mid] === 0) {
[nums[left], nums[mid]] = [nums[mid], nums[left]];
left += 1;
mid += 1;
} else if (nums[mid] === 1) {
mid += 1;
} else {
[nums[right], nums[mid]] = [nums[mid], nums[right]];
right -= 1;
}
}
}
1574. Shortest Subarray to be Removed to Make Array Sorted[Medium]
Given an integer array arr, remove a subarray (can be empty) from arr such that the remaining elements in arr are non-decreasing.
Return the length of the shortest subarray to remove.
A subarray is a contiguous subsequence of the array.
Solution: First, we identify two longest non-decreasing subarrays: one starting from the beginning of the array and the other from the end. We can keep either the first subarray or the second subarray to ensure the result remains non-decreasing. Finally, we check if it's possible to merge these two subarrays together. If arr[i] <= arr[j], it indicates that removing the subarray [i + 1, j - 1] will satisfy the condition. The length of this subarray is j - 1 - (i + 1) + 1. We compare this length with the current result, and if it is smaller, we update the final result.
function findLengthOfShortestSubarray(arr: number[]): number {
const n = arr.length;
let left = 0;
while (left < n - 1 && arr[left] <= arr[left + 1]) {
left += 1;
}
// Sorted Array
if (left === n - 1) {
return 0;
}
let right = n - 1;
while (right >= 1 && arr[right] >= arr[right - 1]) {
right -= 1;
}
// Now [0, left] and [right, n - 1] are increasing subarray
// drop [0, right - 1] or [left + 1, n - 1] can meet the needs.
let result = Math.min(n - left - 1, right)
let i = 0;
let j = right;
while (i < left + 1 && j < n) {
if (arr[i] <= arr[j]) {
// dropping [i + 1, j - 1] will create an array meets the needs.
// arr[0], arr[1]....arr[i], arr[j], arr[j + 1]....arr[n - 1] is the array after the middle part is removed.
result = Math.min(result, j - 1 - (i + 1) + 1);
i += 1;
} else {
j += 1;
}
}
return result;
};
26. Remove Duplicates from Sorted Array[Easy]
Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.
Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:
Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums. Return k. Custom Judge:
The judge will test your solution with the following code:
int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length
int k = removeDuplicates(nums); // Calls your implementation
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
If all assertions pass, then your solution will be accepted.
Solution: We can initialize both the left and right indices at 0. If we find that nums[left] !== nums[right], it indicates that the range [left, right - 1] consists of identical numbers, and nums[right] contains a different value from nums[left]. We can then move the value of nums[right] to nums[left + 1] and repeat the process starting from left + 1.
function removeDuplicates(nums: number[]): number {
const n = nums.length;
if (n === 1) {
return 1;
}
let i = 0, j = 0;
while (i < n) {
while (i < n && nums[i] === nums[j]) {
i += 1;
}
if (i === n) {
break;
}
// Find nums[i] !== nums[j]
j += 1;
nums[j] = nums[i];
}
for (let k = j; k < n - 1; k++) {
nums.pop();
}
return i;
};
27. Remove Element[Easy]
Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.
Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:
Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums. Return k. Custom Judge:
The judge will test your solution with the following code:
int[] nums = [...]; // Input array
int val = ...; // Value to remove
int[] expectedNums = [...]; // The expected answer with correct length.
// It is sorted with no values equaling val.
int k = removeElement(nums, val); // Calls your implementation
assert k == expectedNums.length;
sort(nums, 0, k); // Sort the first k elements of nums
for (int i = 0; i < actualLength; i++) {
assert nums[i] == expectedNums[i];
}
If all assertions pass, then your solution will be accepted.
Solution: We first locate the index of the first occurrence of val. Next, we find the first index of a non-val element after the previous result. We then swap the values at these two indices. Finally, we repeat the process from the start.
function removeElement(nums: number[], val: number): number {
const n = nums.length;
const findIndex = (i, fn) => {
let k = i;
while (k < n && !fn(k)) {
k += 1;
}
return k;
};
let [left, right] = [0, 0];
while (right < n) {
[nums[left], nums[right]] = [nums[right], nums[left]];
left = findIndex(left, k => nums[k] === val);
right = findIndex(left, k => nums[k] !== val);
}
return n - nums.filter(num => num === val).length;
};
977. Squares of a Sorted Array[Easy]
Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.
Follow up: Squaring each element and sorting the new array is very trivial, could you find an O(n) solution using a different approach?
Solution: First, we locate the first non-zero element in the array. If all the elements are either negative or positive, we can square each element and reverse the result if needed. Next, we divide the array into negative and positive parts. We then merge these two parts using two pointers: one pointer moves forward through the positive part, while the other moves backward through the negative part. We compare the squares of the elements and add the smaller value to the result first.
function sortedSquares(nums: number[]): number[] {
const n = nums.length;
const index = nums.findIndex(val => val >= 0);
// All positive
if (index === 0) {
return nums.map(num => num * num);
}
// All negative
if (index === -1) {
nums.reverse();
return nums.map(num => num * num);
}
// First array from index ... n - 1
// Second array: from [index - 1, 0]
let i = index;
let j = index - 1;
const result: number[] = [];
while (i < n && j >= 0) {
const sq1 = nums[i] * nums[i];
const sq2 = nums[j] * nums[j];
if (sq1 >= sq2) {
result.push(sq2);
j -= 1;
} else {
result.push(sq1);
i += 1;
}
}
if (i < n) {
for (let k = i; k < n; k++) {
result.push(nums[k] * nums[k]);
}
}
if (j >= 0) {
for (let k = j; k>=0; k--) {
result.push(nums[k] * nums[k]);
}
}
return result;
};
2. Fast and Slow Pointers Problems
141. Linked List Cycle[Easy]
Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked list. Otherwise, return false.
Solution: We use two pointers, one moving slowly and the other moving quickly, to solve this problem. The fast pointer moves twice as fast as the slow pointer. The cycle is detected when the fast pointer meets the slow pointer or if the fast pointer reaches the end.
function hasCycle(head: ListNode | null): boolean {
// Edge case
if (head === null || head.next === null) return false;
let slow = head;
let fast = head;
while (true) {
[fast, slow] = [fast.next.next, slow.next];
// Find cycle or reach the end
if (slow === fast || fast !== null || fast.next !== null) {
break;
}
}
return slow === fast;
};
142. Linked List Cycle[Medium]
Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.
Do not modify the linked list.
Solution: Similar to the approach used in problem 141, Linked List Cycle [Easy], we can use slow and fast pointers to detect the presence of a cycle. If a cycle is detected, we can then start two pointers—one from the meeting point and the other from the starting point of the list. By moving both pointers at the same speed, they will meet at the starting point of the cycle.
function detectCycle(head: ListNode | null): ListNode | null {
if (head === null || head.next === null) return null;
let slow = head;
let fast = head;
while (true) {
[fast, slow] = [fast.next.next, slow.next];
if (slow === fast || fast !== null || fast.next !== null) {
break;
}
}
if (slow !== fast) {
return null;
}
// Starting from the head again
let ans = head;
while (slow !== ans) {
[slow, ans] = [slow.next, ans.next];
}
return slow;
};
202. Happy Number[Easy]
Write an algorithm to determine if a number n is happy.
A happy number is a number defined by the following process:
Starting with any positive integer, replace the number by the sum of the squares of its digits. Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy. Return true if n is a happy number, and false if not.
Solution: We define a function called move to simulate the process of replacing a number with the sum of the squares of its digits. We then use slow and fast pointers to check for the presence of a cycle.
function isHappy(n: number): boolean {
let fast = n;
let slow = n;
const move = (n: number): number => {
let ans = 0;
while (n > 0) {
ans += (n % 10) ** 2
n = Math.floor(n / 10);
}
return ans;
};
while (true) {
[fast, slow] = [move(move(fast)), move(slow)];
if (fast === 1 || fast === slow) {
break;
}
}
return fast === 1;
};
876. Middle of the Linked List[Easy]
Given the head of a singly linked list, return the middle node of the linked list.
If there are two middle nodes, return the second middle node.
Solution: We use a slow pointer and a fast pointer to solve the problem. When the fast pointer reaches the end, the slow pointer will be at the middle point.
function middleNode(head: ListNode | null): ListNode | null {
let fast = head, slow = head;
while (fast !== null && fast.next !== null) {
[fast, slow] = [fast.next.next, slow.next];
}
return slow;
};
234. Palindrome Linked List[Easy]
Given the head of a singly linked list, return true if it is a palindrome or false otherwise.
Follow up: Could you do it in O(n) time and O(1) space?
Solution: We use the fast and slow pointers to find the middle of the linked list and split it into two halves. Next, we reverse the second half. Finally, we compare the two halves to determine if they are identical.
function isPalindrome(head: ListNode | null): boolean {
if (head === null || head.next === null) return true;
const findMiddle = (head: ListNode): ListNode => {
let fast = head, slow = head;
while (fast !== null && fast.next !== null) {
[fast, slow] = [fast.next.next, slow.next];
}
return slow;
};
const reverse = (head: ListNode | null): ListNode => {
if (head === null || head.next === null) return head;
const rest = reverse(head.next);
head.next.next = head;
head.next = null;
return rest;
};
const areSameLinkedLists = (head1: ListNode | null, head2: ListNode | null): boolean => {
let p1 = head1;
let p2 = head2;
while (p1 !== null && p2 !== null) {
if (p1.val !== p2.val) {
return false;
}
p1 = p1.next;
p2 = p2.next;
}
return true;
};
const mid = findMiddle(head);
const reversedMiddle = reverse(mid);
return areSameLinkedLists(head, reversedMiddle);
};
143. Reorder List[Medium]
You are given the head of a singly linked-list. The list can be represented as:
L0 → L1 → … → Ln - 1 → Ln Reorder the list to be on the following form:
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … You may not modify the values in the list's nodes. Only nodes themselves may be changed.
Solution: We use the fast and slow pointers to find the middle of the linked list and split it into two halves. Next, we reverse the second half. Finally, we merge the two halves to get the final linked list.
function reorderList(head: ListNode | null): void {
if (head === null || head.next === null) return;
const findMiddle = (head: ListNode): ListNode => {
let fast = head, slow = head;
while (fast !== null && fast.next !== null) {
[fast, slow] = [fast.next.next, slow.next];
}
return slow;
};
const reverse = (head: ListNode | null): ListNode => {
if (head === null || head.next === null) return head;
const rest = reverse(head.next);
head.next.next = head;
head.next = null;
return rest;
};
const mergeLinkedLists = (head1: ListNode | null, head2: ListNode | null): void => {
let p1 = head1;
let p2 = head2;
let chooseP1 = true;
let dummy = new ListNode(0);
let p = dummy;
while (p1 !== null && p2 !== null) {
if (chooseP1) {
p.next = p1;
p1 = p1.next;
chooseP1 = false;
} else {
p.next = p2;
p2 = p2.next;
chooseP1 = true;
}
p = p.next;
}
return;
};
const mid = findMiddle(head);
const reversedMiddle = reverse(mid);
mergeLinkedLists(head, reversedMiddle);
};
457. Circular Array Loop[Medium]
You are playing a game involving a circular array of non-zero integers nums. Each nums[i] denotes the number of indices forward/backward you must move if you are located at index i:
If nums[i] is positive, move nums[i] steps forward, and If nums[i] is negative, move nums[i] steps backward. Since the array is circular, you may assume that moving forward from the last element puts you on the first element, and moving backwards from the first element puts you on the last element.
A cycle in the array consists of a sequence of indices seq of length k where:
Following the movement rules above results in the repeating index sequence seq[0] -> seq[1] -> ... -> seq[k - 1] -> seq[0] -> ... Every nums[seq[j]] is either all positive or all negative. k > 1 Return true if there is a cycle in nums, or false otherwise.
Solution: We define a helper function called next to calculate the next step. If it cannot find the next step, it returns -1. We then use fast and slow pointers to check for the presence of a cycle.
function circularArrayLoop(nums: number[]): boolean {
const n = nums.length;
const next = (i: number, forward: boolean): number => {
if ((nums[i] > 0) !== forward) return -1; // same direction
let ans = (i + nums[i]) % n;
if (ans < 0) {
ans += n;
}
if (ans === i) return -1; // one element.
return ans;
};
const solver = (i: number, forward: boolean): boolean => {
let slow = i, fast = i;
while (true) {
[slow, fast] = [next(slow, forward), next(fast, forward)];
if (fast !== -1) {
fast = next(fast, forward);
}
if (slow === -1 || fast === -1 || fast === slow) {
break;
}
}
if (slow !== -1 && slow === fast) {// also means fast !== -1
return true;
}
return false;
};
for (let i = 0; i < n; i++) {
if (solver(i, nums[i] > 0)) return true;
}
return false;
};
287. Find the Duplicate Number[Medium]
Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.
There is only one repeated number in nums, return this repeated number.
You must solve the problem without modifying the array nums and uses only constant extra space.
Follow up:
How can we prove that at least one duplicate number must exist in nums? Can you solve the problem in linear runtime complexity?
Solution: We can find duplicate numbers by treating the array and its indices as a directional path. For example, given nums = [1, 3, 4, 2, 2] and indices [0, 1, 2, 3, 4], we can form the path 0 -> 1 -> 3 -> 2 -> 4 -> 2. This path creates a cycle, where the duplicate number is the entry point of the cycle. We can use the method from problem 142, Linked List Cycle, to identify the start of the cycle and thus find the duplicate number.
function findDuplicate(nums: number[]): number {
let slow = 0, fast = 0;
while (true) {
[slow, fast] = [nums[slow], nums[nums[fast]]];
if (slow === fast) break;
}
// Start from the beginning again and check the meeting point.
slow = 0;
while (slow !== fast) {
[slow, fast] = [nums[slow], nums[fast]];
}
return slow;
};