DSA Sheet - Day 5 Arrays

🚀 DSA Sheet – Day 5: Arrays (Part 5)

This set covers some of the toughest array problems. These require deep understanding of Monotonic Stack, Deque, and advanced two-pointer techniques.

📊 Progress Tracker

Progress: 0 / 4 Completed

Done	Problem	Practice	Level	Companies
	Trapping Rainwater	Solve	Hard	Samsung
	Sliding Window Maximum	Solve	Hard	Amazon, Microsoft, Directi
	Largest Rectangle in Histogram	Solve	Hard	Google, Myntra, TCS
	Reverse Pairs	Solve	Hard	Amazon, Adobe, Uber

🧠 Key Approaches

• Trapping Rainwater: Two pointers OR prefix max arrays
• Sliding Window Maximum: Monotonic Deque
• Largest Rectangle: Monotonic Stack
• Reverse Pairs: Merge Sort based counting

⚡ Quick Cheatsheet

Trapping Rainwater (Two Pointer)

int l = 0, r = n - 1;
int leftMax = 0, rightMax = 0;
int res = 0;

while(l < r){
  if(height[l] < height[r]){
    if(height[l] >= leftMax) 
      leftMax = height[l];
    else 
      res += leftMax - height[l];
    l++;
  } else {
    if(height[r] >= rightMax) 
      rightMax = height[r];
    else 
      res += rightMax - height[r];
    r--;
  }
}
    

Sliding Window Maximum (Deque)

deque dq;

for(int i = 0; i < n; i++){
  while(!dq.empty() && dq.front() <= i - k) 
    dq.pop_front();

  while(!dq.empty() && nums[dq.back()] < nums[i]) 
    dq.pop_back();

  dq.push_back(i);
}
    

Largest Rectangle in Histogram

stack st;

for(int i = 0; i <= n; i++){
  while(!st.empty() && (i == n || h[st.top()] >= h[i])){
    int height = h[st.top()];
    st.pop();

    int width = st.empty() ? i : i - st.top() - 1;
    maxArea = max(maxArea, height * width);
  }
  st.push(i);
}
    

🔥 Pro Tip

These are high-level interview patterns:

• Monotonic Stack & Deque
• Advanced Two Pointer Techniques
• Divide & Conquer (Merge Sort)

Once you master these, you’ll be ready for hard-level interview problems.

🏠 All Days ⬅ Previous Next ➡