DSA 150+ Curated Problems

The classic Dynamic Programming approach uses two arrays, `leftMax` and `rightMax`, taking $O(N)$ space. To achieve $O(1)$ space, we use the **Two Pointers** pattern. We initialize `left = 0` and `right = n - 1`, keeping track of `leftMax` and `rightMax`. We move the pointer corresponding to the *smaller* maximum value inward. Why? Because the amount of water trapped at a position is strictly determined by the *minimum* of the highest bars on its left and right. If `leftMax < rightMax`, we know the limiting factor for the `left` pointer is `leftMax`, regardless of what lies between `left` and `right`. We calculate the trapped water at `left`, update `leftMax`, and increment `left`. We repeat this until the pointers meet.

The 'Course Schedule' problem asks if we can finish all courses given prerequisite pairs, which represents checking for a cycle in a Directed Graph. We solve this using **Kahn's Algorithm (Topological Sort via BFS)**: 1. Build an Adjacency List (graph) and an `inDegree` array counting incoming edges for each node. 2. Push all nodes with `inDegree == 0` (courses with no prerequisites) into a Queue. 3. While the Queue is not empty, pop a node. Increment our `processedNodes` count. 4. For each neighbor of the popped node, decrement its `inDegree`. If the neighbor's `inDegree` becomes 0, push it into the Queue. If `processedNodes == totalCourses`, no cycle exists, and the schedule is valid. If less, a cycle exists (deadlock).