Leet code Problems
18. 4Sum
https://leetcode.com/problems/4sum/description/
Problem Statement:
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 < na,b,c, anddare distinct.nums[a] + nums[b] + nums[c] + nums[d] == target
You may return the answer in any order.
Constraints:
1 <= nums.length <= 200-109 <= nums[i] <= 109-109 <= target <= 109
Example 1:
Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]Example 2:
Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]Algorithm:
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
int n = nums.size();
vector<vector<int>> ans;
if (n < 4) {
return ans;
}
sort(nums.begin(), nums.end());
for (int i = 0; i < n - 3; ++i) {
if (i && nums[i] == nums[i - 1]) {
continue;
}
for (int j = i + 1; j < n - 2; ++j) {
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
int k = j + 1, l = n - 1;
while (k < l) {
long long x = (long long) nums[i] + nums[j] + nums[k] + nums[l];
if (x < target) {
++k;
} else if (x > target) {
--l;
} else {
ans.push_back({nums[i], nums[j], nums[k++], nums[l--]});
while (k < l && nums[k] == nums[k - 1]) {
++k;
}
while (k < l && nums[l] == nums[l + 1]) {
--l;
}
}
}
}
}
return ans;
}
};This 4Sum algorithm finds all unique quadruplets (groups of 4 numbers) from an array that sum up to a given target.
Test Case 1 : [1,0,-1,0,-2,2], Target: 0
- Sort the Array: The input array becomes [-2, -1, 0 , 0 , 1, 2].
- Loop Structure:
- The outer two loops (i and j) pick two numbers at a time. i starts at the first element, jstarts just after i.
- Then, two pointers (k and l) are used. k starts after j , and l starts at the end of the array.
3. Process:
- For each combination of i and j , you check sums of nums[i] , nums[j], nums[k] , and nums[l].
- If the sum equals the target, add the quadruplet to the result list.
- If the sum is less than the target, move k (to try a larger value).
- If the sum is greater, move l (to try a smaller value).
- Skip duplicates (to ensure only unique quadruplets).
Breakdown:
- For i = 0 (nums[0] = -2), j = 1 (nums[1] = -1):
- k = 2 (nums[2] = 0), l = 5 (nums[5] = 2): sum = (-2) + (-1) + 0 + 2 = -1 (less than 0, move k )
- k = 3 (nums[3] = 0), l = 5 : sum = -2 + (-1) + 0 + 1 = 0 (match, add [-2, -1, 1, 2] to the result)
- Continue with other combinations like i = 0, j = 2 , etc., to find more matches ([-2, 0, 0, 2] , [-1, 0, 0, 1]).
Final result for this case: [[ -2, -1, 1, 2] , [-2, 0, 0, 2] , [-1, 0, 0, 1]].
Get ABHINAV ANAND’s stories in your inbox
Join Medium for free to get updates from this writer.
In short, the algorithm sorts the array and uses a two-pointer approach for efficient searching of all quadruplets that sum to the target. It avoids duplicates by skipping over repeated values.
Test Case 2 : [2, 2, 2, 2, 2], Target: 8
- Sort the Array: The array is already sorted: [2, 2, 2, 2, 2].
- Loop Structure:
- The outer loops ( i and j ) pick the first two numbers, while k and l pointers try to find the other two numbers that, when added together, hit the target.
3. Process:
- For i = 0 (nums[0] = 2), j = 1(nums[1] = 2):
- k = 2 (nums[2] = 2), l = 4 (nums[4] = 2): sum = 2 + 2 + 2 + 2 = 8 (match, so add [2, 2, 2, 2] to the result).
- After this, move both k and l , but since all the values are the same, you skip the duplicates.
4. Skipping Duplicates:
- After adding [2, 2, 2, 2] , the algorithm continues, but the subsequent iterations will skip over repeated values to avoid adding the same quadruplet again.
Final result for this case: [[2, 2, 2, 2]].
Summary:
Since all the numbers are the same and the target is 8 , the only valid quadruplet is [2, 2, 2, 2] . The algorithm efficiently avoids duplicates and only returns this unique solution.
24. Swap Nodes in Pairs
https://leetcode.com/problems/swap-nodes-in-pairs/description/
Problem Statement:
Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list’s nodes (i.e., only nodes themselves may be changed.)
Constraints:
- The number of nodes in the list is in the range
[0, 100]. 0 <= Node.val <= 100
Example 1:
Input: head = [1,2,3,4]
Output: [2,1,4,3]
Explanation:
Example 2:
Input: head = []
Output: []
Example 3:
Input: head = [1]
Output: [1]
Example 4:
Input: head = [1,2,3]
Output: [2,1,3]
Algorithm:
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if (!head || !head->next) {
return head;
}
ListNode* t = swapPairs(head->next->next);
ListNode* p = head->next;
p->next = head;
head->next = t;
return p;
}
};Explanation using Test cases:
This algorithm swaps every two adjacent nodes in a linked list using recursion.
Test Case 1: [1, 2, 3, 4]
- First Recursive Call:
- head = 1, head->next = 2. The function is called on the next pair starting from 3 (swapPairs(3->4) ).
2. Second Recursive Call:
- head = 3, head->next = 4. The function calls itself again on null (swapPairs(nullptr) ), as there are no more nodes left.
3. Base Case (End of List):
- When the function hits null, it returns null .
4. Swapping the Pairs:
- Now, the function starts returning and swapping:
- For 3->4 , the result is 4->3->null .
- For 1->2 , the result is 2->1->(4->3).
Final result: [2, 1, 4, 3].
Test Case 2: [] (Empty List)
- The list is empty, so the base case if ( !head || !head->next ) is immediately hit, and it returns null .
Final result: [ ] .
Summary:
The algorithm swaps adjacent nodes recursively, stopping when no more pairs are left. For the list [1, 2, 3, 4] , it returns [2, 1, 4, 3] . For an empty list, it returns [ ].
