Algorithms & Complexities

Pattern: Prefix Sum / Cumulative Sum Optimization

• Brute Force Complexity: $O(n^2)$ time, $O(n)$ space. Uses nested loops to recompute sums from scratch.
• Optimal Complexity: $O(n)$ time, $O(1)$ extra space. Reuses the cumulative sum from the previous index.
• Core Concept: When a problem needs a running total, update the current state using the previous state.

Pattern: Array Replication / Duplication

• Brute Force Complexity: $O(n)$ time, $O(n)$ space. Uses loops to append elements one-by-one into a new array.
• Optimal Complexity: $O(n)$ time, $O(n)$ space. Use Python’s built-in sequence operators (e.g., + or *) to duplicate/merge lists more cleanly.
• Core Concept: When duplicating or merging lists, prefer language-specific sequence operators to simplify code.

Pattern: Two-Pointer Approach / In-Place Swapping Optimization

• Brute Force Complexity: $O(n)$ time, $O(n)$ space. Uses an extra array/string copy to build the reversed result.
• Optimal Complexity: $O(n)$ time, $O(1)$ extra space. Swaps elements in-place using two pointers from both ends.
• Core Concept: For in-place reversing/reordering, move left and right pointers toward the center and swap.

Pattern: Two-Pointer Approach / Boundary Comparison Optimization

• Brute Force Complexity: $O(N \log N)$ time, $O(1)$ extra space (if sorted in-place). Uses direct squaring followed by standard sorting.

• Optimal Complexity: $O(N)$ time, $O(N)$ space. Compares values from both ends simultaneously using two pointers.

• Core Concept: When an array is sorted but contains negative values, the absolute maximum values reside at the outer boundaries. Use two pointers to pull the maximums inward.