IFS Content
- Introduction - Introduction to agentic architectures & frameworks
- MCP, RAG & Tool Calls - Explanation and differentiation between each function
- Agentic Frameworks - Mastra, Langraph, CrewAI, etc
- FINAL INTERVIEW PREP
Leetcode
- Find the Celebrity
- Find the town Judge
- Gas Station Problem
- Find the Majority Element I
- Find the Majority Element II
- Keys and Rooms
- Container with most water
- Trapping Rain Water
- Maximum Subarray
- Find center of star graph
- Maximum Star Sum of a Graph
- Jump Game
- Two Sum
- Three Sum
- Three Sum Smaller
Leetcode Notes
| Problem | Brute Force Time | Brute Force Space | Optimal Time | Optimal Space | Optimal Strategy Used |
|---|---|---|---|---|---|
| Find the Celebrity | O(n²) | O(1) | O(n) | O(1) | Greedy Candidate Elimination |
| Find the Town Judge | O(n²) | O(n²) | O(n + e) | O(n) | Degree Tallying (1D Array) |
| Gas Station | O(n²) | O(1) | O(n) | O(1) | Greedy Single-Pass |
| Majority Element I | O(n²) | O(1) | O(n) | O(1) | Boyer-Moore Voting |
| Majority Element II | O(n²) | O(1) | O(n) | O(1) | Modified Boyer-Moore |
| Keys and Rooms | N/A* | N/A* | O(n + e) | O(n) | Graph Traversal (DFS/BFS) |
| Container With Most Water | O(n²) | O(1) | O(n) | O(1) | Two Pointers (Shrinking) |
| Trapping Rain Water | O(n²) | O(1) | O(n) | O(1) | Two Pointers (Dynamic Max) |
| Maximum Subarray | O(n |
O(1) | O(n) | O(1) | Two Pointers (Dynamic Max) |
| Find the center of the star graph | O(n |
O(1) | O(1) | O(1) | Graph Topology and traversal |
| Find the sum of star graphs | O(V+E) | O(V+E) | Greedy filtering and sorting | ||
| Jump Game | O(n |
O(1) | O(n) | O(1) | Greedy Dynamic Programming |
| Two Sum | O(n |
O(1) | O(n) | O(n) | Hashmap, Greedy |
| Three sum | O(n |
O(n) | O(n |
O(1) | Two Pointer, Sorting, Greedy |
| Three sum smaller | O(n |
O(1) | O(n |
O(1) | Two Pointer, Sorting |
Important Context Notes
-
Variables:
nrefers to the number of elements, people, or nodes.erefers to the number of edges (e.g., the length of thetrustarray in Town Judge, or the total number of keys in Keys and Rooms). -
*Keys and Rooms (No Brute Force): Graph reachability problems don't have a traditional "brute-force" vs "optimal" comparison in the same way array problems do. You must traverse the graph using DFS or BFS. Without tracking visited rooms, an algorithm would get stuck in an infinite loop, so standard traversal (Time:
O(n + e), Space:O(n)) is both the baseline and the optimal solution. -
Majority Elements: A very common "middle ground" approach for these is using a HashMap. A HashMap takes O(n) Time but costs O(n) Space. The true optimal (Boyer-Moore) brings that space complexity down to O(1).
-
Trapping Rain Water: There is an intermediate Dynamic Programming approach that calculates maximum heights beforehand. That DP approach takes O(n) Time and O(n) Space. The Two Pointer approach listed in the table is the ultimate optimal solution because it brings the space down to O(1).