Table of contents
- Q1. Solve the "subarray sum equals k" problem using prefix sum.
- Q2. Solve the "longest subarray with sum k" problem using prefix sum.
- Q3. Solve the "find a pair with a given sum in a sorted array" problem using two pointers.
- Q4. Solve the "three sum" problem using two pointers.
- Q5. Solve the "trap rainwater" problem using two pointers.
Today, I focused on mastering the prefix sum technique and the two pointers approach to solve challenging problems. I began by solving the "subarray sum equals k" problem using prefix sum, followed by tackling the "longest subarray with sum k" problem, leveraging prefix sums for efficient computation. Next, I applied the two pointers technique to solve the "find a pair with a given sum in a sorted array" problem, followed by solving the classic "three sum" problem. Finally, I used two pointers to efficiently solve the "trap rainwater" problem. These exercises deepened my understanding of how prefix sum and two pointers can optimize solutions.
Check out my progress in my GitHub repository: github.com/AayJayTee/100-Days-DSA.
Q1. Solve the "subarray sum equals k" problem using prefix sum.
#include <iostream>
using namespace std;
void prefix_sum_subarray(int arr[], int n) {
int prefix_sum[n];
prefix_sum[0] = arr[0]; // Initialize the first element of the prefix sum
for (int i = 1; i < n; i++) {
prefix_sum[i] = prefix_sum[i - 1] + arr[i]; // Calculate the prefix sum for each element
}
}
void subarray_sum_equals_k(int arr[], int n, int k) {
int prefix_sum[n];
prefix_sum[0] = arr[0];
for (int i = 1; i < n; i++) {
prefix_sum[i] = prefix_sum[i - 1] + arr[i];
}
for (int start = 0; start < n; start++) {
for (int end = start; end < n; end++) {
int curr_sum = start == 0 ? prefix_sum[end] : prefix_sum[end] - prefix_sum[start - 1];
if (curr_sum == k) { // Check if the sum of the subarray equals k
cout << "Subarray found from index " << start << " to " << end << " with sum " << k << endl;
}
}
}
}
int main() {
int n,k;
cout << "Enter length of array: ";
cin >> n;
cout << "Enter elements of the array: ";
int arr[n];
for (int i = 0; i < n; i++) {
cin >> arr[i]; // Input array elements
}
cout<<"Enter value of k: ";
cin>>k;
cout << "Subarrays with sum equals k:" << endl;
subarray_sum_equals_k(arr, n, k);
return 0;
}
This code finds and prints subarrays in an array whose sum equals a specified value k. It first computes the prefix sum array, which stores the cumulative sum of elements up to each index. The subarray_sum_equals_k function then iterates through all possible subarrays by using two nested loops: one for the starting index (start) and one for the ending index (end). For each subarray, it calculates the sum using the prefix sum array. If the sum equals k, it prints the subarray's indices and the sum. The program takes input for the array and then searches for subarrays whose sum equals k.
Q2. Solve the "longest subarray with sum k" problem using prefix sum.
#include <iostream>
using namespace std;
#include <unordered_map>
// Function to find the longest subarray with sum k using prefix sum
int longest_sum_subarray(int arr[], int n, int k) {
int prefixSum[n];
prefixSum[0] = arr[0]; // Initialize the prefix sum array
for (int i = 1; i < n; i++) {
prefixSum[i] = prefixSum[i - 1] + arr[i]; // Compute prefix sum for each element
}
int count = 0;
unordered_map<int, int> m; // HashMap to store frequency of prefix sums
for (int j = 0; j < n; j++) {
if (prefixSum[j] == k) { // If prefix sum is equal to k, increment count
count++;
}
int val = prefixSum[j] - k; // Calculate the required sum to check if it exists
if (m.find(val) != m.end()) { // If the required sum exists, add its frequency to count
count += m[val];
}
if (m.find(prefixSum[j]) == m.end()) { // If the prefix sum is not already in the map, add it
m[prefixSum[j]] = 0;
}
m[prefixSum[j]]++; // Increment the frequency of the current prefix sum
}
return count; // Return the count of subarrays with sum k
}
int main() {
int n, k;
cout << "Enter length of array: ";
cin >> n;
cout << "Enter elements of the array: ";
int arr[n];
for (int i = 0; i < n; i++) {
cin >> arr[i]; // Input array elements
}
cout << "Enter value of k: ";
cin >> k; // Input target sum k
cout << "The max no of times the subarray of sum exists is: " << longest_sum_subarray(arr, n, k) << endl;
return 0;
}
This code finds the number of subarrays in a given array arr[] that have a sum equal to a target value k. It uses a prefix sum approach combined with a hash map (unordered_map) to efficiently count subarrays with the desired sum. The prefix sum array stores cumulative sums of the elements up to each index, and the hash map tracks how many times each prefix sum has occurred. As the code iterates through the array, it checks if the current prefix sum equals k, or if the difference between the current prefix sum and k has been seen before (indicating the existence of a subarray with sum k). For each match, the count is incremented. The final result is the total count of subarrays whose sum equals k. This approach reduces the time complexity to O(n), making it more efficient than a brute force solution.
Q3. Solve the "find a pair with a given sum in a sorted array" problem using two pointers.
#include <iostream>
using namespace std;
// Function to find a pair with the given sum in a sorted array using two pointers
void findpair(int arr[], int n, int sum) {
int i = 0, j = n - 1; // Initialize two pointers, i at the start and j at the end
bool pairfound = false; // Flag to track if a pair is found
while (i < j) { // Continue while the pointers don't cross
if (arr[i] + arr[j] == sum) { // If the pair is found
cout << "The first element is: " << arr[i] << endl;
cout << "The second element is: " << arr[j] << endl;
pairfound = true; // Set flag to true
break;
}
else if (arr[i] + arr[j] < sum) { // If the sum is less, move the left pointer right
i++;
}
else { // If the sum is greater, move the right pointer left
j--;
}
}
if (!pairfound) { // If no pair is found after the loop
cout << "No pair of elements is found for the given sum" << endl;
}
}
int main() {
int n, sum;
cout << "Enter length of array: ";
cin >> n;
cout << "Enter elements of the array: ";
int arr[n];
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
cout << "Enter value of sum: ";
cin >> sum;
findpair(arr, n, sum); // Call the function to find the pair with the given sum
return 0;
}
This code finds a pair of elements in a sorted array that add up to a given sum using the two-pointer technique. It initializes two pointers: one (i) at the start of the array and the other (j) at the end. The sum of the elements at these pointers is checked in each iteration. If the sum equals the target value, the pair is printed, and the loop terminates. If the sum is less than the target, the left pointer (i) is moved right to increase the sum, and if the sum is greater, the right pointer (j) is moved left to decrease the sum. This continues until the two pointers meet or a pair is found. If no such pair is found by the end of the loop, a message is printed indicating no pair was found. The program uses this approach to efficiently find pairs in a sorted array with a time complexity of O(n).
Q4. Solve the "three sum" problem using two pointers.
#include <iostream>
using namespace std;
#include <algorithm>
void threesum(int arr[], int n, int sum) {
sort(arr, arr + n); // Sort the array
for (int i = 0; i < n; i++) {
if (i > 0 && arr[i] == arr[i - 1]) continue; // Skip duplicates for arr[i]
int left = i + 1;
int right = n - 1;
while (left < right) {
int curr_sum = arr[i] + arr[left] + arr[right];
if (curr_sum == sum) {
cout << "The elements adding up to the sum are: ";
cout << arr[i] << " " << arr[left] << " " << arr[right] << endl;
left++;
right--;
while (left < right && arr[left] == arr[left - 1]) left++; // Skip duplicates for arr[left]
while (left < right && arr[right] == arr[right + 1]) right--; // Skip duplicates for arr[right]
} else if (curr_sum < sum) {
left++;
} else {
right--;
}
}
}
}
int main() {
int n, sum;
cout << "Enter length of array: ";
cin >> n;
cout << "Enter elements of the array: ";
int arr[n];
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
cout << "Enter the sum: ";
cin >> sum;
threesum(arr, n, sum);
return 0;
}
This code implements the "Three Sum" problem, where the goal is to find all unique triplets in an array that sum up to a given value. The algorithm first sorts the input array to make it easier to find combinations using two pointers. For each element arr[i] (except the first element if it's a duplicate), two pointers, left and right, are initialized to the positions right after i and at the end of the array, respectively. The sum of the current triplet (arr[i] + arr[left] + arr[right]) is compared with the target sum. If the sum matches, the triplet is printed, and the pointers are adjusted to skip duplicate values. If the sum is less than the target, the left pointer is moved right, and if the sum is greater, the right pointer is moved left. This process continues until all possible triplets are checked. The program ensures no duplicates are printed by skipping over repeated values of arr[i], arr[left], and arr[right].
Q5. Solve the "trap rainwater" problem using two pointers.
#include <iostream>
using namespace std;
// Function to calculate the total trapped rainwater in an elevation map
void total_trapped_rainwater(int arr[], int n) {
// Initialize left and right pointers, and their respective maximum heights
int left = 0, right = n - 1;
int left_max = arr[left], right_max = arr[right];
int water_amt = 0;
// Loop to calculate trapped water between the left and right pointers
while (left < right) {
// Move the left pointer if the left max is smaller than the right max
if (left_max < right_max) {
left += 1;
left_max = max(left_max, arr[left]); // Update left max height
water_amt += left_max - arr[left]; // Add water trapped at this position
}
// Move the right pointer if the right max is smaller than the left max
else {
right -= 1;
right_max = max(right_max, arr[right]); // Update right max height
water_amt += right_max - arr[right]; // Add water trapped at this position
}
}
// Output the total amount of trapped water
cout << "The amount of water trapped is: " << water_amt;
}
int main() {
int n;
cout << "Enter length of array: ";
cin >> n;
// Declare and input the elevation array
cout << "Enter elements of the array: ";
int arr[n];
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
// Call the function to calculate and display the total trapped water
total_trapped_rainwater(arr, n);
return 0;
}
This code calculates the total amount of trapped rainwater in an elevation map represented by an array. The array values correspond to the height of the terrain at each index. It uses a two-pointer approach to efficiently calculate the trapped water. Initially, two pointers (left and right) are set at the start and end of the array, and two variables (left_max and right_max) track the maximum heights encountered from both ends. The algorithm moves the pointers inward, comparing the current heights, and updates the trapped water amount based on the difference between the current height and the maximum height seen so far. If the left height is smaller than the right height, the left pointer is moved to the right; otherwise, the right pointer is moved to the left. The total trapped water is accumulated and displayed at the end.
Today's practice strengthened my grasp of both the prefix sum and two pointers techniques. From solving subarray sum problems to tackling more complex challenges like trapping rainwater and finding pairs with given sums, I learned how these techniques can dramatically improve efficiency. These exercises have equipped me with a broader range of problem-solving tools, and I look forward to applying these techniques to even more advanced problems in the coming days!