Welcome to Day 17 of my 100 Days of DSA challenge! Today, I explored two essential techniques: Prefix Sum and Two Pointers. These techniques are incredibly efficient for solving problems related to subarray sums and optimized array traversal. The problems I tackled demonstrated how they simplify complex tasks while improving performance.
Check out my GitHub repository for all the solutions and progress updates at: 100 Days of DSA
Let’s dive into today’s challenges and learnings! 🚀
1. Subarray Sum Equals K (Prefix Sum)
This program finds the total number of subarrays whose sum equals k using a prefix sum approach and a map. It iterates through the array, maintaining a cumulative sum (current_sum) and checks if a prefix sum exists such that the difference current_sum - k has been seen before. If it exists, it means there is a subarray with sum k, and the count is updated. The cumulative sum is stored in a map to efficiently track and update occurrences of prefix sums.
Code:
#include <iostream>
#include <map>
using namespace std;
// Function to find the total number of subarrays with sum equal to k
int subarray_sum_k(int arr[], int n, int k) {
map<int, int> prefix_sum_count; // Map to store the count of prefix sums
int current_sum = 0; // Variable to track the cumulative sum
int count = 0; // Variable to store the total count of subarrays
prefix_sum_count[0] = 1; // Initialize with sum 0 to handle subarrays starting from index 0
for (int i = 0; i < n; i++) {
current_sum += arr[i]; // Update the cumulative sum
// Check if there exists a prefix sum such that current_sum - prefix_sum = k
if (prefix_sum_count.find(current_sum - k) != prefix_sum_count.end()) {
count += prefix_sum_count[current_sum - k];
}
// Add the current cumulative sum to the prefix_sum_count map
prefix_sum_count[current_sum]++;
}
return count;
}
int main() {
int arr[] = {1, 2, 3, -3, 1, 2, 1, -1, 2};
int k = 3;
int n = sizeof(arr) / sizeof(arr[0]);
int result = subarray_sum_k(arr, n, k);
cout << "Total number of subarrays with sum " << k << ": " << result << endl;
return 0;
}
Output:
2. Longest Subarray With Sum K (Prefix Sum)
This program finds the length of the longest subarray with a sum equal to k using the prefix sum approach. It keeps track of the cumulative sum while iterating through the array and uses a map to store the first occurrence of each prefix sum. For each index, it checks if there is a previous prefix sum such that the difference equals k, and calculates the length of the corresponding subarray. The maximum length is updated as needed. If the current cumulative sum equals k, the subarray starting from the beginning is also considered.
Code:
#include <iostream>
#include <map>
using namespace std;
// Function to find the length of the longest subarray with sum k
int longest_subarray_sum_k(int arr[], int n, int k) {
map<int, int> prefix_sum_map; // To store the first occurrence of prefix sums
int current_sum = 0; // Variable to keep track of cumulative sum
int max_length = 0; // To store the length of the longest subarray
for (int i = 0; i < n; i++) {
current_sum += arr[i]; // Update the cumulative sum
// If current_sum equals k, the subarray [0..i] has sum k
if (current_sum == k) {
max_length = i + 1;
}
// Check if there is a prefix sum such that current_sum - k exists
if (prefix_sum_map.find(current_sum - k) != prefix_sum_map.end()) {
// Calculate the length of the subarray
int subarray_length = i - prefix_sum_map[current_sum - k];
max_length = max(max_length, subarray_length);
}
// Store the first occurrence of current_sum
if (prefix_sum_map.find(current_sum) == prefix_sum_map.end()) {
prefix_sum_map[current_sum] = i;
}
}
return max_length;
}
int main() {
int arr[] = {1, 2, 3, 1, 1, 1, 4, 2, -1};
int k = 5;
int n = sizeof(arr) / sizeof(arr[0]);
int result = longest_subarray_sum_k(arr, n, k);
cout << "Length of the longest subarray with sum " << k << ": " << result << endl;
return 0;
}
Output:
3. Find a Pair With a Given Sum in a Sorted Array
This program finds a pair of elements in a sorted array whose sum matches a given target k using the two-pointer technique. It initializes two pointers—one at the start and one at the end of the array—and calculates their sum. If the sum equals k, it prints the pair. If the sum is smaller, it moves the left pointer to the right; if the sum is larger, it moves the right pointer to the left. This process continues until the pair is found or the pointers cross each other.
Code:
#include <iostream>
using namespace std;
// Function to find a pair with the given sum k
bool find_pair_with_sum(int arr[], int n, int k) {
int left = 0; // Start pointer
int right = n - 1; // End pointer
while (left < right) {
int current_sum = arr[left] + arr[right];
// Check if the current sum matches the target
if (current_sum == k) {
cout << "Pair found: (" << arr[left] << ", " << arr[right] << ")" << endl;
return true;
}
// If the current sum is less, move the left pointer to the right
else if (current_sum < k) {
left++;
}
// If the current sum is greater, move the right pointer to the left
else {
right--;
}
}
cout << "No pair found with the given sum." << endl;
return false;
}
int main() {
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 10;
find_pair_with_sum(arr, n, k);
return 0;
}
Output:
4. Three Sum Problem
This program finds all unique triplets in an array whose sum equals zero. It first sorts the array and fixes one element in each iteration. Using two pointers (left and right), it searches for two other elements that sum to the negative of the fixed element. It avoids duplicate triplets by skipping repeated values and adjusts pointers to find all valid combinations.
Code:
#include <iostream>
#include <algorithm>
using namespace std;
// Function to find all unique triplets with a sum of zero
void three_sum(int arr[], int n) {
sort(arr, arr + n); // Sort the array for two-pointer approach
for (int i = 0; i < n - 2; i++) {
// Avoid duplicates for the first element
if (i > 0 && arr[i] == arr[i - 1]) continue;
int target = -arr[i]; // Fix arr[i] and find two numbers with sum equal to -arr[i]
int left = i + 1, right = n - 1;
while (left < right) {
int current_sum = arr[left] + arr[right];
if (current_sum == target) {
cout << "Triplet: (" << arr[i] << ", " << arr[left] << ", " << arr[right] << ")" << endl;
// Avoid duplicates for the second and third elements
while (left < right && arr[left] == arr[left + 1]) left++;
while (left < right && arr[right] == arr[right - 1]) right--;
left++;
right--;
}
else if (current_sum < target) {
left++; // Move left pointer to increase the sum
}
else {
right--; // Move right pointer to decrease the sum
}
}
}
}
int main() {
int arr[] = {-1, 0, 1, 2, -1, -4};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Unique triplets with sum zero:" << endl;
three_sum(arr, n);
return 0;
}
Output:
5. Trap Rainwater Problem
This program calculates the total amount of water trapped between bars in an elevation map using the two-pointer technique. Two pointers, left and right, traverse the array from both ends. At each step, the program compares the heights at these pointers and determines how much water can be trapped based on the maximum heights encountered from the left and right. The pointers move towards each other, and the trapped water is accumulated. This process continues until the two pointers meet, and the total trapped water is returned.
Code:
#include <iostream>
#include <algorithm>
using namespace std;
// Function to calculate the total trapped water
int trap_rainwater(int arr[], int n) {
int left = 0, right = n - 1; // Two pointers
int left_max = 0, right_max = 0; // Max height to the left and right
int water_trapped = 0;
while (left <= right) {
if (arr[left] <= arr[right]) {
if (arr[left] >= left_max) {
left_max = arr[left]; // Update left_max
} else {
water_trapped += left_max - arr[left]; // Water trapped at left pointer
}
left++; // Move left pointer to the right
} else {
if (arr[right] >= right_max) {
right_max = arr[right]; // Update right_max
} else {
water_trapped += right_max - arr[right]; // Water trapped at right pointer
}
right--; // Move right pointer to the left
}
}
return water_trapped;
}
int main() {
int arr[] = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
int n = sizeof(arr) / sizeof(arr[0]);
int result = trap_rainwater(arr, n);
cout << "Total water trapped: " << result << " units" << endl;
return 0;
}
Output:
Day 17 showcased the power of Prefix Sum and Two Pointers in solving complex array problems efficiently. These techniques not only enhance problem-solving speed but also improve the clarity of solutions. By applying them, I gained deeper insights into optimizing array-based challenges and refining my approach to algorithmic problems. Looking forward to more exciting techniques ahead! 🚀