Day 49: Competitive Programming Journal

Date: November 12, 2024
Hello Everyone,

Today marks Day 49 of my competitive programming journey. Here's what I worked on today:

What I Did Today:
I solved two problems: Count the number of subarrays with a given sum and Find the maximum sum of a subarray using Kadane’s Algorithm.

1. Count the number of subarrays with a given sum (Sliding Window):
Problem:
You are given an array and a target sum. Count the number of subarrays that add up to the target sum.

Explanation:

• Use a hashmap to store the cumulative sum at each point in the array.
• Check if the difference between the current cumulative sum and the target exists in the hashmap. If it does, that means a subarray with the target sum exists.

Implementation:

int countSubarraysWithSum(vector<int>& nums, int target) {
    unordered_map<int, int> prefixSum;
    int count = 0, currentSum = 0;

    prefixSum[0] = 1;

    for (int num : nums) {
        currentSum += num;

        if (prefixSum.find(currentSum - target) != prefixSum.end()) {
            count += prefixSum[currentSum - target];
        }

        prefixSum[currentSum]++;
    }

    return count;
}

2. Find the maximum sum of a subarray (Kadane’s Algorithm):
Problem:
Given an array, find the maximum possible sum of a subarray.

Explanation:

• Use a variable to track the current sum (currentSum) and update the maximum sum (maxSum) whenever currentSum exceeds maxSum.
• If currentSum drops below 0, reset it to 0 since a negative sum cannot contribute to a maximum.

Implementation:

int maxSubarraySum(vector<int>& nums) {
    int maxSum = nums[0], currentSum = 0;

    for (int num : nums) {
        currentSum += num;

        if (currentSum > maxSum) {
            maxSum = currentSum;
        }

        if (currentSum < 0) {
            currentSum = 0;
        }
    }

    return maxSum;
}

Reflection:
Today’s problems highlighted the power of efficient algorithms like prefix sums and Kadane's algorithm. It was great to revisit these fundamental yet powerful techniques that are frequently used in competitive programming.

Stay tuned for more updates, and happy coding!