Day 2 – Max Average Subarray & Highest Altitude | Sliding Window + Prefix Sum | LeetCode Challenge

🗓️ Date: July 26, 2025
📌 Challenge:
🧩 Problem 1: Maximum Average Subarray I – LeetCode #643 (Easy)
🧩 Problem 2: Find the Highest Altitude – LeetCode #1732 (Easy)
💻 Topic: Sliding Window, Prefix Sum, Arrays

---

✅ Problem Statement (Summary):

🔹 Problem 1: Maximum Average Subarray I

Goal: Find the contiguous subarray of size k with the maximum average value.
Example:
Input: nums = [1,12,-5,-6,50,3], k = 4
→ Output: 12.75000
Explanation: Subarray [12,-5,-6,50] → Sum = 51 → Avg = 12.75

---

🧠 What I Learned (Problem 1):

• Sliding Window is efficient when we need to compute window sums repeatedly.

• Reusing previous window's sum: subtract the first element, add the next.

• Store the max window sum and divide at the end for result.

---

🧪 Code (C++):

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        int win_sum = 0, max_sum = 0;
        for (int i = 0; i < k; i++) {
            win_sum += nums[i];
        }
        max_sum = win_sum;
        for (int i = k; i < nums.size(); i++) {
            win_sum += (nums[i] - nums[i - k]);
            max_sum = max(win_sum, max_sum);
        }
        return double(max_sum) / k;
    }
};

🕒 Time Complexity: O(n)
📦 Space Complexity: O(1)

📸 LeetCode Submission Screenshot:

---

✅ Key Takeaways:

• Use fixed-size sliding window for k-length subarrays

• Keep track of running sum to optimize computation

• Divide by k only once at the end

---

🔹 Problem 2: Find the Highest Altitude

Goal: Return the highest point reached based on gain[] changes in altitude.
Example:
Input: gain = [-5,1,5,0,-7]
→ Output: 1
Explanation: Altitudes = [0, -5, -4, 1, 1, -6], max = 1

---

🧠 What I Learned (Problem 2):

• Treat gain array as prefix sum over time.

• Start from altitude 0 and keep updating cumulative gain.

• Track max altitude as we traverse.

---

🧪 Code (C++):

class Solution {
public:
    int largestAltitude(vector<int>& gain) {
        int maxGain = 0;
        int netGain = gain[0];
        maxGain = max(netGain, maxGain);
        for (int i = 1; i < gain.size(); i++) {
            netGain += gain[i];
            maxGain = max(netGain, maxGain);
        }
        return maxGain;
    }
};

🕒 Time Complexity: O(n)
📦 Space Complexity: O(1)

📸 LeetCode Submission Screenshot:

---

✅ Key Takeaways:

• Start altitude is always 0

• Running prefix sum tracks cumulative altitude

• Track max at each step to find peak

---

📈 Progress Tracker:
✅ Day: 2 / 30
🧩 Total Problems Solved: 3
🧭 Focus Today: Sliding Window + Prefix Sum

---

🗂️ Tags:
#leetcode #30DaysChallenge #slidingwindow #prefixsum #cpp #dsa #arrays #maxaverage #altitude #codingjourney