Data Structures Based on Array

Arrays are where we start as devs. But what if I told you arrays secretly stack superpowers?

Let's go beginner → expert: mastering arrays, stacks, monotonic stacks, and deques

1. Arrays: Where It All Begins

Arrays are simple ordered lists, but processing them often leads to O(n²) nested loops.

🔹 Example Problem: "For each element, find the next greater element."

Brute Force: For every element, scan right until you find a larger one → O(n²).

2. Stacks: The First Power-Up 🧙‍♂️

LIFO: Last In First Out Structures

A stack (LIFO) helps process elements in reverse order of arrival.

When we stack books like:

The book that are accessible are simple, the ones on the top.

Core ops:

push() – add to top
pop() – remove from top

Stacks are simple. Stacks are just LIFO structures. But it can be more than that:

The real power?

Strategic usage, especially when paired with monotonicity.

they’re algorithmic powerhouses when combined with monotonicity.

they unlock O(n) solutions for problems you'd otherwise brute-force.

3. Monotonic Stacks: Sorted Stack

A monotonic stack maintains sorted order (increasing or decreasing) while pushing elements.

🔻Decreasing Monotonic Stack

const stack = [];

for (let i = 0; i < nums.length; i++) {
 while (0 < stack.length 
 && nums[stack[stack.length - 1]] < nums[i]) {
    stack.pop();
  }
  stack.push(i);
}

Think of organising nested bowls in your kitchen. Each new bowl must fit inside the previous one.

If the incoming bowl is smaller, it stacks nicely (push).

If it's bigger, you must remove bowls (pop) until it fits.

decreasing sizes = [🟡, 🟠, 🟢, ⚪️, 🔵] 

Large → Medium → Small → Smaller → Smallest

🔹 Use case: Next Smaller Element

💡 We pop until the current element is smaller than the top, then push.

 🔺 Increasing Monotonic Stack

🧍‍♂️ People Standing in Ascending Order of Height

Imagine people lining up for a photo, but there’s a rule:

Everyone wants to see someone taller in front of them, no short people can block tall ones.

const stack = [];

for (let i = 0; i < nums.length; i++) {
 while (0 < stack.length 
 && nums[i] < nums[stack[stack.length - 1]]) {
    stack.pop();
  }
  stack.push(i);
}

🔹 Use case: Next Greater Element

💡 We pop until the stack top is larger than the incoming celeb, then push.

➡️ You keep popping until the tallest (so far) is at the front.

Types:

📈 Increasing stack (bottom→top): [1, 3, 5] → used for next smaller

📉 Decreasing stack: [7, 4, 2] → used for next greater

 Expanding Ordered Elements to Queues and Deques

The idea of ordered element processing doesn’t stop at stacks.

Stacks are powerful — they solve "next greater/smaller" problems in O(n).

But they have one blind spot:

⛔ They can’t adapt to moving windows or dynamic ranges.

⚠️ Why?

• A stack is one-directional: you only push/pop from the top.
• It works for static problems (where the array doesn’t move).
• But the moment your data slides or expires, stack can’t remove from the front.

Thus comes queue

4. 📦 Queue (FIFO): First-In-First-Out

Think of people lining up to buy coffee:

• The person who enters the line first is served first.
• This is a queue.

Core ops:

• enqueue(x) → add to the back
• dequeue() → remove from the front

📌 Use Case: Breadth-First Search (BFS), scheduling tasks, stream processing

5. Deque (Double-Ended Queue 🚪)

Now imagine a line where people can enter or exit from either end like a room with two doors.

That’s a deque:

• You can pushFront(x) or pushBack(x)
• And popFront() or popBack()

🧠 Why it’s powerful:

You can maintain ordered windows of elements, dynamically adding/removing from both ends.

6 . Deque + Monotonicity

Building deque logic is the same as stack. In both, you maintain monotonic order by popping elements that violate the desired pattern.

Stacks are amazing when working with static arrays.

But what if our array moves like a window sliding across a stream of data?

That’s when stacks fall short.

Really??

A deque lets you:

• Push and pop from the back (like a stack)
• Remove outdated elements from the front (critical for window logic)

When you combine monotonic stacks with deques

When monotonicity meets the flexibility of a deque, you unlock blazing-fast solutions for moving-window problems.

 You Unlock a Power Weapon of data structure.

A simple analogy imagine you’re watching a group of influencers trying to stay trending on a live ranking board that updates every minute.

The board only shows the top trending person in the last 5 minutes i.e sliding window of size 5.

Every time a new person walks in (a new minute of data), the board checks:

1. Are they more popular than anyone currently on the board?
2. → Kick out everyone less popular than them, they’ll never trend again.
3. Is the oldest person on the board outside the 5-minute window?
4. → Kick them out, their trend window expired.

📈 Monotonic Increasing (for Sliding Min):

while (0 < dDeque.length
&& nums[i] < nums[dDeque[dDeque.length - 1]] ) {
 dDeque.pop();
}

dDeque.push(i);

// Remove from front if it's out of the window
if (dDeque[0] <= i - k) dDeque.shift();

1. 🧠 Front of increasing deque always holds the smallest value
2. Ideal when you care about min value in window

🔻 Monotonic Decreasing Deque (for Sliding Max):

while (0 < iDeque.length 
&& nums[iDeque[iDeque.length - 1]] < nums[i]) {
  iDeque.pop();
}

iDeque.push(i);
if (iDeque[0] <= i - k) iDeque.shift();

1. 🧠 Front of decreasing deque always holds the largest value
2. Ideal for max value in sliding window

sometimes both can be combined like:

while (limit < dStack[0] - iStack[0]) {
 if(nums[l] === dDeque[0]) dDeque.shift()
 if(nums[l] === iDeque[0]) iDeque.shift()
 l++
}

a. Sliding Window Max/Min in O(n)

1. Track the optimal value as the window moves no rescanning, no duplicates, no wasted ops.

b. Live Range Queries: Perfect for real-time analytics like:

1. Sensor smoothing
2. Stock market trend tracking
3. Stream-based monitoring

c. Optimized Greedy & DP: Enables efficient subarray calculations like:

1. Longest subarray under a constraint
2. Shortest subarray to meet a target
3. Minimizing cost in rolling decisions

👉 Why it works:

Monotonicity prunes irrelevant elements.

Deque gives control from both ends perfect for dynamic, streaming problems.

Leetcode Question:

Now that we learn the technique let's see the list of problem that simply solved using this technique.

🧱 Regular Stack Problems (LIFO)

Classic usage of stacks

1. Valid Parentheses
2. Min Add to Make Parentheses Valid
3. Evaluate Reverse Polish Notation
4. Implement Stack Using Queues
5. Implement Queue Using Stacks
6. Backspace String Compare
7. Validate Stack Sequences
8. Decode String
9. Remove All Adjacent Duplicates
10. Asteroid Collision

📈 Monotonic Increasing Stack Problems

1. Next Smaller Element
2. Previous Smaller Element
3. Largest Rectangle in Histogram
4. Sum of Subarray Minimums
5. Remove K Digits
6. Daily Temperatures (reverse variant)

📉 Monotonic Decreasing Stack Problems

Stack maintains descending order (bottom → top).

Used for next/previous greater, range maximums, etc.

1. Next Greater Element
2. Next Greater Element II (circular array)
3. Previous Greater Element
4. Daily Temperatures
5. Stock Span Problem
6. Sum of Subarray Maximums
7. 132 Pattern
8. Trapping Rain Water (stack version)
9. Building Sunset/Ocean View

🚪 Monotonic Deque + Sliding Window

Double-ended queue + monotonicity = windowed min/max.

Used for dynamic range, streaming, and sliding window problems.

1. Sliding Window Maximum
2. Longest Subarray with Absolute Diff ≤ Limit
3. Shortest Subarray with Sum ≥ K (prefix sum + increasing deque)
4. Sliding Window Minimum (increasing deque)
5. Max/Min of All Subarrays of Size K