100% Beat in Python Using Stack 🥇
IntuitionThe problem involves partitioning the array into chunks such that when each chunk is sorted individually and then concatenated, the result is a fully s
# Intuition
The problem involves partitioning the array into chunks such that when each chunk is sorted individually and then concatenated, the result is a fully sorted array. This can be visualized as maintaining the order of elements in a stack-like structure. A stack can help keep track of chunks and manage conditions when merging is required.

# Approach
1. Stack-Based Approach: Use a stack to simulate chunk boundaries.
    - Traverse the array and compare each element with the top of the stack.
    - If the current element is greater than or equal to the top of the stack, it indicates that the current element can be part of the current chunk. Push it onto the stack.
    - If the current element is less than the top of the stack, it indicates that merging of chunks is required. Pop elements from the stack until the stack top is smaller than or equal to the current element. This ensures that all elements in the merged chunk satisfy the sorting condition. Finally, push the maximum element from the merged chunk onto the stack.
2. Count Chunks: At the end of the traversal, the size of the stack gives the number of chunks, as each entry in the stack corresponds to a valid chunk.

# Complexity
- Time complexity:
$$O(n)$$

- Space complexity:
$$O(n)$$
![Screenshot From 2024-12-19 19-26-47.png](https://assets.leetcode.com/users/images/b3500753-2592-41d2-8313-b59f30764d36_1734616686.1042347.png)

# Code
```python3 []
class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        stack = []
        for num in arr:
            if not stack or stack[-1] <= num:
                stack.append(num)
            else:
                element = stack[-1]
                while stack and stack[-1] > num:
                    stack.pop()
                stack.append(element)
        return len(stack)
```
['Array', 'Stack', 'Greedy', 'Monotonic Stack', 'Python3']