🗓 Daily LeetCode Progress – Day 8

Problems Solved:

#76 Minimum Window Substring
#33 Search in Rotated Sorted Array

This continues my daily series (Day 8: Sliding Window + Binary Search patterns). Today I focused on two important window and search problems: finding the minimum substring that contains all characters of another string, and locating an element in a rotated sorted array using modified binary search. Both are implemented in Python and C++.

💡 What I Learned

Today’s focus was on two different but fundamental techniques:

For Minimum Window Substring, the key is a dynamic sliding window with frequency maps and a have vs need condition to shrink/expand optimally.
For Search in Rotated Sorted Array, the trick is to identify which half of the array is sorted at each step and then decide where to continue binary search.
Learned how careful pointer updates (left, right) and boundary conditions (<= vs <) are crucial in both problems.
Practiced combining hash maps (Counter in Python / arrays in C++) with two-pointer logic in sliding windows.

🧩 #76 — Minimum Window Substring

Python (Sliding window with frequency tracking)

from collections import Counter

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if len(t) > len(s):
            return ""

        need = Counter(t)
        window = {}
        have, need_count = 0, len(need)
        res, res_len = [-1, -1], float("inf")
        left = 0

        for right, char in enumerate(s):
            window[char] = window.get(char, 0) + 1
            if char in need and window[char] == need[char]:
                have += 1

            while have == need_count:
                if (right - left + 1) < res_len:
                    res = [left, right]
                    res_len = right - left + 1
                window[s[left]] -= 1
                if s[left] in need and window[s[left]] < need[s[left]]:
                    have -= 1
                left += 1

        l, r = res
        return s[l:r+1] if res_len != float("inf") else ""

C++ (Sliding window with hash map)

#include <string>
#include <unordered_map>
using namespace std;

class Solution {
public:
    string minWindow(string s, string t) {
        if (t.size() > s.size()) return "";

        unordered_map<char,int> need;
        for (char c : t) need[c]++;

        unordered_map<char,int> window;
        int have = 0, needCount = need.size();
        int bestLen = INT_MAX, bestL = 0;

        int l = 0;
        for (int r = 0; r < (int)s.size(); r++) {
            window[s[r]]++;
            if (need.count(s[r]) && window[s[r]] == need[s[r]]) {
                have++;
            }

            while (have == needCount) {
                if (r - l + 1 < bestLen) {
                    bestLen = r - l + 1;
                    bestL = l;
                }
                window[s[l]]--;
                if (need.count(s[l]) && window[s[l]] < need[s[l]]) {
                    have--;
                }
                l++;
            }
        }

        return (bestLen == INT_MAX) ? "" : s.substr(bestL, bestLen);
    }
};

Why it works:
We expand the window until all characters are included, then shrink it from the left while keeping validity. This ensures we always track the minimum valid substring.

Time: O(m + n)
Space: O(26) (or O(unique chars))

🧩 #33 — Search in Rotated Sorted Array

Python (Modified binary search)

class Solution:
    def search(self, nums: List[int], t: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == t:
                return mid

            if nums[left] <= nums[mid]:  # left half is sorted
                if nums[left] <= t < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:  # right half is sorted
                if nums[mid] < t <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        return -1

C++ (Modified binary search)

class Solution {
public:
    int search(vector<int>& nums, int t) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == t) return mid;

            if (nums[left] <= nums[mid]) { // left sorted
                if (nums[left] <= t && t < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else { // right sorted
                if (nums[mid] < t && t <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
};

Why it works:
At every step, one half of the array must be sorted. We use that property to decide if the target lies in the sorted half or the other half, cutting the search space in half each time.

Time: O(log n)
Space: O(1)

📸 Achievements

Minimum Window Substring (Python & C++)

Search in Rotated Sorted Array (Python & C++)

📦 Complexity Recap

Minimum Window Substring: O(m+n) time, O(1) space (fixed alphabet)
Search in Rotated Sorted Array: O(log n) time, O(1) space

📣 Join the Journey

I’m solving and documenting problems daily in both Python and C++, highlighting sliding window and binary search patterns. Follow along if you’re into algorithms and optimization.

Links