DEV Community

Ertugrul
Ertugrul

Posted on • Edited on

🗓 Daily LeetCode Progress – Day 21

Problems Solved:

  • #739 Daily Temperatures
  • #56 Merge Intervals

This continues my daily series (Day 21: Monotonic Stack + Interval Merging). Today I solved two fundamental interview patterns: using a monotonic stack to find the next warmer day, and sorting + single pass to merge overlapping intervals.

💡 What I Learned

  • For Daily Temperatures (#739), a monotonic decreasing stack of indices lets us pop and resolve days as soon as we encounter a warmer temperature: every index is pushed and popped at most once → O(n).
  • For Merge Intervals (#56), always sort by start, then sweep left→right. If the current start <= last merged end, they overlap → extend the end; otherwise, start a new interval.
  • Both problems demonstrate how the right data structure (stack) or preprocessing (sort) yields linear-time passes after a cheap setup.

🧩 #739 — Daily Temperatures

Python (Monotonic Stack, O(n)) 

from typing import List

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        ans = [0] * n
        stack = []

        for i, t in enumerate(temperatures):
            while stack and temperatures[stack[-1]] < t:
                j = stack.pop()
                ans[j] = i - j
            stack.append(i)

        return ans
Enter fullscreen mode Exit fullscreen mode

C++ (Monotonic Stack, O(n)) 

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

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = (int)temperatures.size();
        vector<int> ans(n, 0);
        stack<int> st;
        for (int i = 0; i < n; ++i) {
            while (!st.empty() && temperatures[st.top()] < temperatures[i]) {
                int j = st.top(); st.pop();
                ans[j] = i - j;
            }
            st.push(i);
        }
        return ans;
    }
};
Enter fullscreen mode Exit fullscreen mode

Key idea: Keep indices of days with decreasing temperatures on the stack. When a warmer day appears, pop and fill the answer with the distance.

Complexity: O(n) time, O(n) space for the stack (worst-case strictly decreasing temps).

🧩 #56 — Merge Intervals

Python (Sort + Sweep, O(n log n)) 

from typing import List

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if not intervals:
            return []

        intervals.sort(key=lambda x: x[0])
        merged = [intervals[0]]

        for s, e in intervals[1:]:
            last_s, last_e = merged[-1]
            if s <= last_e:
                merged[-1][1] = max(last_e, e)
            else:
                merged.append([s, e])
        return merged
Enter fullscreen mode Exit fullscreen mode

C++ (Sort + Sweep, O(n log n)) 

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

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.empty()) return {};
        sort(intervals.begin(), intervals.end(),
             [](const vector<int>& a, const vector<int>& b){ return a[0] < b[0]; });

        vector<vector<int>> merged;
        merged.push_back(intervals[0]);

        for (size_t i = 1; i < intervals.size(); ++i) {
            auto& last = merged.back();
            if (intervals[i][0] <= last[1]) {
                last[1] = max(last[1], intervals[i][1]);
            } else {
                merged.push_back(intervals[i]);
            }
        }
        return merged;
    }
};
Enter fullscreen mode Exit fullscreen mode

Key idea: Sort by start; overlapping detection becomes local to the last merged interval. Touch each interval once after sorting.

Complexity: O(n log n) for sorting, O(n) sweep, O(1) extra apart from the output.

📸 Achievements

  • Implemented monotonic stack to solve next-warmer-day distances in linear time.

monotonic py

monotonic cpp

  • Merged arbitrary-ordered intervals correctly via sort + single pass.

Merged py

Merged cpp

📦 Complexity Recap

  • Daily Temperatures: O(n) time, O(n) space (stack).
  • Merge Intervals: O(n log n) time (sort), O(n) pass; O(1) extra space beyond result.

📣 Join the Journey

I’m solving and documenting problems daily in both Python and C++, covering arrays, stacks/queues, sliding windows, and classic interval problems. Follow along if you’re interested in

Links:

Top comments (0)