- Brute force means checking all possible cases directly.
- It is often easier to write first.
- It is useful for understanding the problem and verifying results.
Example:
- checking every subarray sum using three loops
- Optimized solutions reduce unnecessary repeated work.
- They use smarter logic, precomputation, or better data structures.
Example:
- using prefix sums instead of recalculating subarray sums every time
- A brute force solution may pass small inputs but fail large ones.
- An optimized solution improves performance and is often expected in interviews.
- brute force: easier to think of first
- optimized: faster and better for large input
- Understand the problem
- Write the brute force solution
- Analyze time complexity
- Improve it step by step
- print all subarrays: brute force with nested loops in PrintAllSubarrays.java
- max subarray sum:
- brute force can be
O(n^3)in MaxMinSubarraySumBruteForce.java - prefix sum can be
O(n^2)in MaxMinSubarraySumPrefix.java - Kadane's algorithm can be
O(n)in KadanesAlgorithm.java