Day 17: 100 Days of DSA

Welcome to Day 17 of my 100 Days of DSA challenge! Today, I solved five problems focused on prefix sum & two pointers technique. Here's a quick look at the questions I tackled and how I approached them 🤖✨ Check out my GitHub repository for all my solutions and progress. Let’s keep learning!

1. Subarray Sum Equals K (Prefix Sum)

To solve this:

1. Use a hashmap to store counts of prefix sums.

2. For each prefix sum, check if the difference current_sum - k exists in the hashmap.

3. Increment the count by the value of that difference in the hashmap.

Code:

#include <unordered_map>
#include<iostream>
#include <vector>
using namespace std;

int subarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> prefix_count;
    prefix_count[0] = 1;
    int current_sum = 0, count = 0;
    for (int num : nums) {
        current_sum += num;
        if (prefix_count.count(current_sum - k)) {
            count += prefix_count[current_sum - k];
        }
        prefix_count[current_sum]++;
    }
    return count;
}

int main(){
    vector<int> nums={12,3,4,5,-1,4,5};
    int k=5;
    int res=subarraySum(nums,k);
    cout<<"The subarrays with given sum are:"<<res<<endl;


}

2. Solve the "longest subarray with sum k" problem using prefix sum.

To solve this:

1. Use a hashmap to store the first occurrence of a prefix sum.

2. For each prefix sum, check if current_sum - k exists in the hashmap.

3. Update the maximum length when a valid subarray is found.

#include <unordered_map>
#include<iostream>
#include <vector>
using namespace std;

int longestSubarraySumK(vector<int>& nums, int k) {
    unordered_map<int, int> prefix_index;
    prefix_index[0] = -1;
    int current_sum = 0, max_length = 0;
    for (int i = 0; i < nums.size(); i++) {
        current_sum += nums[i];
        if (prefix_index.count(current_sum - k)) {
            max_length = max(max_length, i - prefix_index[current_sum - k]);
        }
        if (!prefix_index.count(current_sum)) {
            prefix_index[current_sum] = i;
        }
    }
    return max_length;
}

int main(){
    vector<int> nums={12,3,4,5,-1,4,5};
    int k=9;
    int res=longestSubarraySumK(nums,k);
    cout<<"The subarrays with given sum are:"<<res<<endl;
}

Output:

3. Solve the "find a pair with a given sum in a sorted array" problem using two pointers.

To solve this:

1. Use two pointers, one starting at the beginning and the other at the end.

2. Adjust pointers based on whether the current sum is less than or greater than the target.

Code:

#include <vector>
#include<iostream>
using namespace std;

bool findPairWithSum(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) return true;
        else if (sum < target) left++;
        else right--;
    }
    return false;
}

int main(){
    vector<int> nums={1,2,3,4,5};
    int target=9;
    if(findPairWithSum(nums,target)){
        cout<<"Target Exists"<<endl;
    }
    else{
        cout<<"The target does not exist";
    }
}

Output:

4. Solve the "three sum" problem using two pointers.

To solve this:

1. Sort the array and fix one element at a time.

2. Use two pointers for the remaining two numbers to find combinations summing to zero.

Code:

#include <vector>
#include <algorithm>
#include<iostream>
using namespace std;

vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> result;
    sort(nums.begin(), nums.end());
    for (int i = 0; i < nums.size() - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        int left = i + 1, right = nums.size() - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                result.push_back({nums[i], nums[left], nums[right]});
                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;
                left++;
                right--;
            } else if (sum < 0) left++;
            else right--;
        }
    }
    return result;
}

int main(){vector<int> nums = {-1, 0, 1, 2, -1, -4};
    vector<vector<int>> result = threeSum(nums);

    cout << "Triplets with sum 0 are:" << endl;
    for (const auto& triplet : result) {
        cout << "[";
        for (int num : triplet) {
            cout << num << " ";
        }
        cout << "]" << endl;
    }

    return 0;}

Output:

5. Solve the "trap rainwater" problem using two pointers.

To solve this:

1. Use two pointers, one at the beginning and the other at the end.

2. Keep track of the maximum heights from the left and right while calculating trapped water.

Code:

    #include <vector>
    #include<iostream>
    using namespace std;

    int trapRainwater(vector<int>& height) {
        int left = 0, right = height.size() - 1, left_max = 0, right_max = 0, water = 0;
        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= left_max) left_max = height[left];
                else water += left_max - height[left];
                left++;
            } else {
                if (height[right] >= right_max) right_max = height[right];
                else water += right_max - height[right];
                right--;
            }
        }
        return water;
    }

    int main(){
        vector<int> height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        int trappedWater = trapRainwater(height);

        cout << "The total trapped rainwater is: " << trappedWater << " units." << endl;

        return 0;
    }

Output:

This is all for today! See you tomorrow :)