DEV Community: jayk0001

DSA Fundamentals: Two Pointers & Sliding Window - From Theory to LeetCode Practice

jayk0001 — Fri, 05 Dec 2025 04:25:56 +0000

Two Pointers and Sliding Window are powerful algorithmic techniques that optimize array and string problems from O(n²) brute force to O(n) linear time. These patterns appear frequently in coding interviews and real-world applications, especially when dealing with subsequences, subarrays, or substring problems.

This comprehensive guide combines theoretical understanding with practical problem-solving, featuring solutions to essential LeetCode problems that demonstrate core concepts.

Understanding Two Pointers Technique

Two Pointers Fundamentals

Two Pointers is an efficient technique that uses two indices to traverse data structures, typically arrays or strings. Instead of nested loops, two pointers move through the data structure based on specific conditions.

Common Two Pointers Patterns

1. Opposite Directional (Convergent):

Pointers start from both ends (index 0 and last index)
Move inward based on conditions
Loop terminates when pointers meet
Use cases: Palindrome validation, sorted array problems, container problems

2. Same Directional (Chasing):

Both pointers start from the same end
Move at different speeds based on conditions
Use cases: Fast-slow pointer, removing duplicates

3. Applications:

Can be used standalone
Combined with binary search
Integrated within sliding window
Part of multi-pointer algorithms (e.g., 3Sum)

Time Complexity Analysis

Pattern	Time Complexity	Space Complexity	Notes
Basic Two Pointers	O(n)	O(1)	Single pass through array
With Binary Search	O(log n)	O(1)	Halves search space each iteration
Three Pointers (3Sum)	O(n²)	O(1)	One fixed, two moving pointers
With Sorting	O(n log n)	O(1)	Dominated by sort operation

Understanding Sliding Window Technique

Sliding Window Fundamentals

Sliding Window is an optimization technique for solving problems involving contiguous subarrays or substrings. Instead of recalculating for each window position, we maintain a window and slide it through the data structure.

Two Types of Sliding Windows

1. Variable Length Window

Pattern:

Expand window by moving right pointer
Process elements as they enter window
When condition violated, shrink by moving left pointer
Update result (max/min window size, count, etc.)
Continue until right pointer reaches end

Use cases: Longest substring problems, dynamic size constraints

# Variable Length Window Template
def variable_window(arr):
    left = 0
    result = 0
    window_state = {}  # Track window state

    for right in range(len(arr)):
        # Expand window: add arr[right]
        # Update window state

        while condition_violated:
            # Shrink window: remove arr[left]
            # Update window state
            left += 1

        # Update result with current window
        result = max(result, right - left + 1)

    return result

2. Fixed Length Window

Pattern:

Calculate result for first window of size k
Slide window: remove leftmost element, add new rightmost element
Update result for each window position
Continue until end of array

Use cases: Maximum sum of k elements, average calculations

# Fixed Length Window Template
def fixed_window(arr, k):
    # Calculate first window
    window_sum = sum(arr[:k])
    result = window_sum

    # Slide window through array
    for i in range(k, len(arr)):
        window_sum = window_sum - arr[i - k] + arr[i]
        result = max(result, window_sum)

    return result

Window Operations Time Complexity

Operation	Time Complexity	Notes
Initialize window	O(k)	First k elements
Slide window	O(1)	Add one, remove one
Variable window (full pass)	O(n)	Each element visited at most twice
Fixed window (full pass)	O(n)	Single pass after initialization

Essential LeetCode Problems & Solutions

Let's explore fundamental two pointers and sliding window problems that demonstrate core algorithmic patterns.

Two Pointers Problems

1. Valid Palindrome (LeetCode 125)

Problem: Check if a string is a palindrome, considering only alphanumeric characters and ignoring case.

Approach: Use two pointers from both ends, skip non-alphanumeric characters, compare values.

class Solution:
    def isPalindrome(self, s: str) -> bool:
        # Convert to lowercase for case-insensitive comparison
        s = s.lower()
        left = 0
        right = len(s) - 1

        while left < right:
            # Skip non-alphanumeric characters from left
            while left < right and not s[left].isalnum():
                left += 1

            # Skip non-alphanumeric characters from right
            while left < right and not s[right].isalnum():
                right -= 1

            # Compare characters
            if s[left] != s[right]:
                return False

            left += 1
            right -= 1

        return True

Time Complexity: O(n) - Single pass through string

Space Complexity: O(1) - Only using two pointers

Key Concepts:

Two-pointer convergence: Start from both ends, meet in middle
Character filtering: Skip non-alphanumeric on the fly
Early termination: Return False immediately on mismatch
Edge case handling: Empty strings and single characters are palindromes

2. Two Sum II - Input Array Is Sorted (LeetCode 167)

Problem: Find two numbers in a sorted array that add up to a target value. Return 1-indexed positions.

Approach: Use two pointers from both ends, adjust based on sum comparison with target.

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left = 0
        right = len(numbers) - 1

        while left < right:
            current_sum = numbers[left] + numbers[right]

            # Found the target
            if current_sum == target:
                return [left + 1, right + 1]  # 1-indexed

            # Sum too small, need larger number
            if current_sum < target:
                left += 1
            # Sum too large, need smaller number
            else:
                right -= 1

        return []  # No solution found

Time Complexity: O(n) - Single pass through array

Space Complexity: O(1) - Only using two pointers

Key Concepts:

Sorted array advantage: Enables two-pointer approach
Binary decision: Move left (increase sum) or right (decrease sum)
Guaranteed solution: Problem guarantees exactly one solution
Comparison with unsorted: O(n) here vs O(n²) brute force or O(n) with hash map

3. Container With Most Water (LeetCode 11)

Problem: Given array of heights, find two lines that form container holding the most water.

Approach: Two pointers from both ends, move pointer with shorter height inward to potentially find larger area.

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left = 0
        right = len(height) - 1
        max_area = 0

        while left < right:
            # Calculate current area
            width = right - left
            current_height = min(height[left], height[right])
            current_area = width * current_height

            # Update maximum area
            max_area = max(max_area, current_area)

            # Move pointer with shorter height
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1

        return max_area

Time Complexity: O(n) - Single pass through array

Space Complexity: O(1) - Only tracking area variables

Key Concepts:

Greedy approach: Always move shorter height pointer
Area calculation: width * min(height[left], height[right])
Why move shorter height?: Moving taller height can only decrease width without height benefit
Optimal substructure: Each step makes locally optimal choice

4. 3Sum (LeetCode 15)

Problem: Find all unique triplets in array that sum to zero.

Approach: Fix one element, use two pointers for remaining two elements. Sort first to handle duplicates and enable two-pointer technique.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # Sort for two-pointer approach and duplicate handling
        nums.sort()
        n = len(nums)
        result = []

        for i in range(n):
            # Early termination: if current number positive, no way to sum to 0
            if nums[i] > 0:
                break

            # Skip duplicate elements for first number
            if i > 0 and nums[i] == nums[i-1]:
                continue

            # Two pointers for remaining elements
            left = i + 1
            right = n - 1

            while left < right:
                current_sum = nums[i] + nums[left] + nums[right]

                if current_sum == 0:
                    result.append([nums[i], nums[left], nums[right]])

                    # Skip duplicates for second number
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    # Skip duplicates for third number
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1

                    left += 1
                    right -= 1

                elif current_sum < 0:
                    left += 1  # Need larger sum
                else:
                    right -= 1  # Need smaller sum

        return result

Time Complexity: O(n²) - Outer loop O(n) × inner two pointers O(n)

Space Complexity: O(1) - Ignoring output array, only using pointers

Key Concepts:

Fixed + two pointers: Reduces 3Sum to 2Sum problem
Duplicate handling: Skip same values to avoid duplicate triplets
Sorting requirement: Enables two-pointer approach and duplicate skipping
Early termination: If smallest number is positive, impossible to sum to 0

5. Trapping Rain Water (LeetCode 42)

Problem: Calculate how much rainwater can be trapped between elevation heights.

Approach: Two pointers with max height tracking from both ends. Water trapped at each position depends on minimum of max heights from both sides.

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0

        left = 0
        right = len(height) - 1
        left_max = 0
        right_max = 0
        total_water = 0

        while left < right:
            # Process from side with lower maximum
            if height[left] <= height[right]:
                # Update left max height
                left_max = max(left_max, height[left])
                # Water trapped = max height - current height
                total_water += left_max - height[left]
                left += 1
            else:
                # Update right max height
                right_max = max(right_max, height[right])
                # Water trapped = max height - current height
                total_water += right_max - height[right]
                right -= 1

        return total_water

Time Complexity: O(n) - Single pass through array

Space Complexity: O(1) - Only tracking max values and pointers

Key Concepts:

Two-pointer optimization: Avoid two-pass solution
Max height tracking: Water level determined by minimum of left_max and right_max
Water calculation: max_height - current_height at each position
Greedy processing: Always process side with lower maximum height
Why it works: Water trapped at position depends only on minimum barrier height

Sliding Window Problems

6. Best Time to Buy and Sell Stock (LeetCode 121)

Problem: Find maximum profit from single buy and sell transaction. Can only sell after buying.

Approach: Track minimum price seen so far, calculate profit at each position, update maximum profit.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price = prices[0]
        max_profit = 0

        for price in prices:
            # Update minimum price seen so far
            min_price = min(price, min_price)

            # Calculate profit if we sell today
            current_profit = price - min_price

            # Update maximum profit
            max_profit = max(current_profit, max_profit)

        return max_profit

Time Complexity: O(n) - Single pass through array

Space Complexity: O(1) - Only tracking min and max values

Key Concepts:

One-pass solution: No need to check all pairs
Running minimum: Track lowest price seen so far (best buy point)
Profit calculation: Current price - minimum price
Greedy approach: Always buy at lowest seen price, sell at current
Edge case: If prices only decrease, max_profit remains 0

7. Longest Substring Without Repeating Characters (LeetCode 3)

Problem: Find length of longest substring without repeating characters.

Approach: Variable-length sliding window with set to track characters. Expand window until duplicate found, then shrink until duplicate removed.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        char_set = set()
        left = 0
        longest = 0

        for right in range(len(s)):
            # Shrink window while duplicate exists
            while s[right] in char_set:
                char_set.remove(s[left])
                left += 1

            # Add current character to window
            char_set.add(s[right])

            # Calculate window size and update longest
            window_size = right - left + 1
            longest = max(longest, window_size)

        return longest

Time Complexity: O(n) - Each character visited at most twice (once by right, once by left)

Space Complexity: O(min(n, k)) - k is character set size (26 for lowercase letters)

Key Concepts:

Variable window: Expands and shrinks based on duplicate condition
Set for tracking: O(1) lookup for duplicates
Window maintenance: Remove from left until no duplicates
Size calculation: right - left + 1
Each element visited twice maximum: Right pointer adds, left pointer removes

8. Longest Repeating Character Replacement (LeetCode 424)

Problem: Find length of longest substring with same letter after replacing at most k characters.

Approach: Variable-length window tracking character frequencies. Shrink when window_size - max_frequency > k.

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        char_count = {}
        left = 0
        longest = 0

        for right in range(len(s)):
            # Add current character to window
            char_count[s[right]] = char_count.get(s[right], 0) + 1

            # Shrink window if replacement count exceeds k
            # window_size - most_frequent_char = replacements_needed
            while (right - left + 1) - max(char_count.values()) > k:
                char_count[s[left]] -= 1
                left += 1

            # Update longest valid window
            window_size = right - left + 1
            longest = max(longest, window_size)

        return longest

Time Complexity: O(n × 26) = O(n) - For each position, find max in char_count (at most 26 characters)

Space Complexity: O(26) = O(1) - Fixed size hash map for alphabet

Key Concepts:

Replacement logic: window_size - max_frequency = replacements_needed
Window validity: Valid when replacements needed ≤ k
Frequency tracking: Count each character in current window
Max frequency optimization: Most frequent character should stay, replace others
No need to shrink perfectly: Window never shrinks below previously valid size

9. Permutation in String (LeetCode 567)

Problem: Check if one string's permutation is substring of another string.

Approach: Fixed-length sliding window matching character frequencies. Compare frequency maps.

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        len1 = len(s1)
        len2 = len(s2)

        # Edge case: s1 longer than s2
        if len1 > len2:
            return False

        # Build frequency maps
        s1_map = {}
        s2_map = {}

        # Initialize first window
        for i in range(len1):
            s1_map[s1[i]] = s1_map.get(s1[i], 0) + 1
            s2_map[s2[i]] = s2_map.get(s2[i], 0) + 1

        # Check first window
        if s1_map == s2_map:
            return True

        # Slide window through rest of s2
        for i in range(len1, len2):
            # Add new character to window
            s2_map[s2[i]] = s2_map.get(s2[i], 0) + 1

            # Remove old character from window
            old_char = s2[i - len1]
            s2_map[old_char] -= 1
            if s2_map[old_char] == 0:
                del s2_map[old_char]

            # Check if current window matches s1
            if s1_map == s2_map:
                return True

        return False

Time Complexity: O(n) - Slide window through s2 once, map comparison is O(26) = O(1)

Space Complexity: O(1) - Hash maps store at most 26 characters

Key Concepts:

Fixed window size: Length of s1
Permutation = same frequency: Order doesn't matter
Sliding optimization: Update frequency map instead of recalculating
Map comparison: Python dict equality checks keys and values
Cleanup: Remove characters with 0 count for accurate comparison

Core Algorithm Patterns from Today's Problems

1. Two Pointers - Opposite Directional Pattern

When to use:

Array is sorted or sorting is beneficial
Looking for pairs/triplets that meet certain conditions
Optimizing from both ends simultaneously

Examples: Two Sum II, Valid Palindrome, Container With Most Water, 3Sum

Key characteristics:

Start from both ends (left = 0, right = n-1)
Move pointers based on comparison
O(n) time complexity for sorted arrays
Often combined with sorting for O(n log n) total

Template:

def two_pointers_opposite(arr):
    left = 0
    right = len(arr) - 1

    while left < right:
        if condition_met(arr[left], arr[right]):
            return result
        elif need_larger_value:
            left += 1
        else:
            right -= 1

    return default_result

2. Variable-Length Sliding Window Pattern

When to use:

Finding longest/shortest subarray/substring with certain property
Condition can be checked incrementally
Need to maintain a contiguous sequence

Examples: Longest Substring Without Repeating Characters, Longest Repeating Character Replacement

Key characteristics:

Expand window by incrementing right pointer
Shrink window by incrementing left pointer
Maintain window state (set, map, count)
Each element visited at most twice → O(n)

Template:

def variable_sliding_window(arr):
    left = 0
    window_state = {}
    result = 0

    for right in range(len(arr)):
        # Add arr[right] to window
        update_window_state(arr[right])

        # Shrink while invalid
        while not valid_window():
            remove_from_window(arr[left])
            left += 1

        # Update result
        result = max(result, right - left + 1)

    return result

3. Fixed-Length Sliding Window Pattern

When to use:

Window size is predetermined
Need to check all subarrays/substrings of specific length
Frequency/sum calculations over fixed ranges

Examples: Permutation in String, Maximum Average Subarray

Key characteristics:

Build initial window of size k
Slide: remove left element, add right element
O(n) time complexity after O(k) initialization
Simple sliding mechanism

Template:

def fixed_sliding_window(arr, k):
    # Build first window
    window_state = initialize_window(arr[:k])
    result = calculate_result(window_state)

    # Slide window
    for i in range(k, len(arr)):
        remove_element(arr[i - k])
        add_element(arr[i])
        result = update_result(window_state, result)

    return result

4. Multi-Pointer Pattern (3Sum)

When to use:

Problems requiring k elements with certain sum
Can be reduced to (k-1)-pointer problem
Sorting enables efficient searching

Example: 3Sum, 4Sum

Key characteristics:

Fix (k-2) elements with outer loops
Use two-pointer technique for remaining 2 elements
Time complexity: O(n^(k-1))
Careful duplicate handling required

Performance Optimization Tips

1. Two Pointers vs Hash Map Trade-offs

# Unsorted array: Hash map approach
def two_sum_unsorted(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        if target - num in seen:
            return [seen[target - num], i]
        seen[num] = i
# Time: O(n), Space: O(n)

# Sorted array: Two pointers approach  
def two_sum_sorted(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        curr_sum = nums[left] + nums[right]
        if curr_sum == target:
            return [left, right]
        elif curr_sum < target:
            left += 1
        else:
            right -= 1
# Time: O(n), Space: O(1)

Key insight: Two pointers saves space when array is sorted or sorting cost is acceptable.

2. Set vs Hash Map for Sliding Window

# When only membership matters: Use Set
def longest_unique_substring(s):
    char_set = set()  # O(1) operations
    left = 0
    longest = 0

    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        longest = max(longest, right - left + 1)
    return longest

# When frequency matters: Use Hash Map
def character_replacement(s, k):
    char_count = {}  # Need frequency for validation
    left = 0
    longest = 0

    for right in range(len(s)):
        char_count[s[right]] = char_count.get(s[right], 0) + 1
        while (right - left + 1) - max(char_count.values()) > k:
            char_count[s[left]] -= 1
            left += 1
        longest = max(longest, right - left + 1)
    return longest

Key insight: Use simplest data structure that satisfies requirements.

3. Early Termination in Two Pointers

def three_sum_optimized(nums):
    nums.sort()
    result = []

    for i in range(len(nums)):
        # Early termination: impossible to reach 0
        if nums[i] > 0:
            break  # All remaining numbers are positive

        # Skip duplicates
        if i > 0 and nums[i] == nums[i-1]:
            continue

        # Two pointers for remaining elements
        left, right = i + 1, len(nums) - 1
        while left < right:
            # ... rest of logic

Key insight: Check for impossible conditions before processing.

4. Avoiding Redundant Calculations

# Inefficient: Recalculate max every iteration
for right in range(len(s)):
    char_count[s[right]] += 1
    while (right - left + 1) - max(char_count.values()) > k:  # O(26) every iteration
        char_count[s[left]] -= 1
        left += 1

# Optimized: Track max frequency
max_freq = 0
for right in range(len(s)):
    char_count[s[right]] += 1
    max_freq = max(max_freq, char_count[s[right]])  # O(1) update
    while (right - left + 1) - max_freq > k:
        char_count[s[left]] -= 1
        left += 1

Key insight: For character replacement problem, max_freq only needs to increase (never decrease matters for longest result).

Common Pitfalls and Solutions

1. Off-by-One Errors in Window Size

# Wrong: Window size calculation
window_size = right - left  # Missing the +1

# Correct: Window size includes both endpoints
window_size = right - left + 1

# Example: left=2, right=5
# Elements at indices: [2, 3, 4, 5] = 4 elements
# Calculation: 5 - 2 + 1 = 4 ✓

2. Forgetting to Update Window State

# Wrong: Forget to add new element
for right in range(len(s)):
    # Process window
    while s[right] in char_set:
        char_set.remove(s[left])
        left += 1
    # ❌ Missing: char_set.add(s[right])
    longest = max(longest, right - left + 1)

# Correct: Always update window state
for right in range(len(s)):
    while s[right] in char_set:
        char_set.remove(s[left])
        left += 1
    char_set.add(s[right])  # ✓ Add current element
    longest = max(longest, right - left + 1)

3. Incorrect Duplicate Skipping in 3Sum

# Wrong: Skip current element
if nums[i] == nums[i-1]:  # Will skip first occurrence too!
    continue

# Correct: Skip after processing first occurrence
if i > 0 and nums[i] == nums[i-1]:  # Protect against i=0
    continue

4. Boundary Conditions in Two Pointers

# Dangerous: No boundary check in nested while loops
while s[right] in char_set:
    char_set.remove(s[left])
    left += 1  # Could exceed right

# Safe: Always check boundaries
while left < right and s[right] in char_set:
    char_set.remove(s[left])
    left += 1

5. Hash Map Cleanup Oversight

# Wrong: Leave zero-count entries
char_count[old_char] -= 1  # Could become 0, affecting map comparison

# Correct: Remove zero-count entries
char_count[old_char] -= 1
if char_count[old_char] == 0:
    del char_count[old_char]  # Clean up for accurate comparison

Time Complexity Comparison

Problem Complexity Summary

Problem	Brute Force	Optimized	Space	Technique
Valid Palindrome	O(n)	O(n)	O(1)	Two Pointers
Two Sum II	O(n²)	O(n)	O(1)	Two Pointers
Container With Most Water	O(n²)	O(n)	O(1)	Two Pointers
3Sum	O(n³)	O(n²)	O(1)	Sort + Two Pointers
Trapping Rain Water	O(n²)	O(n)	O(1)	Two Pointers
Best Time to Buy/Sell	O(n²)	O(n)	O(1)	Sliding Window
Longest Substring Unique	O(n³)	O(n)	O(k)	Variable Window + Set
Character Replacement	O(n² × k)	O(n × 26)	O(26)	Variable Window + Map
Permutation in String	O(n × m!)	O(n)	O(26)	Fixed Window + Map

Why These Techniques Are Efficient

Two Pointers eliminates nested loops:

Brute force: Check all pairs → O(n²)
Two pointers: Single pass from both ends → O(n)
Savings: O(n²) → O(n)

Sliding Window eliminates redundant calculations:

Brute force: Recalculate each subarray from scratch → O(n² × k)
Sliding window: Update incrementally → O(n)
Savings: O(n²) → O(n) or O(n³) → O(n)

Conclusion

Two Pointers and Sliding Window are essential optimization techniques that transform inefficient brute-force solutions into elegant, linear-time algorithms. Key takeaways:

Core Concepts Mastered:

Two Pointers:

Opposite directional: Converging from both ends (palindrome, two sum, container)
Same directional: Fast-slow pointer, removing duplicates
Multi-pointer: Extending to 3Sum, 4Sum problems
Sorted array advantage: Enables O(n) solutions

Sliding Window:

Variable length: Dynamic window based on conditions (longest substring)
Fixed length: Predetermined window size (permutation matching)
Window state: Set for membership, hash map for frequency
Incremental updates: Add/remove elements efficiently

Essential Patterns Mastered Today:

Pattern 1: Two-pointer convergence (Valid Palindrome, Two Sum II, Container With Most Water)

Pattern 2: Multi-pointer with sorting (3Sum, Trapping Rain Water)

Pattern 3: Variable-length sliding window (Longest Substring, Character Replacement)

Pattern 4: Fixed-length sliding window (Permutation in String)

Problem-Solving Strategies:

Identify contiguous sequences: Consider sliding window
Sorted array or pairs: Consider two pointers
Substring/subarray problems: Usually sliding window
Sum/product targets: Two pointers on sorted array
Longest/shortest with condition: Variable sliding window
Fixed-size calculations: Fixed sliding window

Optimization Principles:

Eliminate nested loops with two pointers
Update incrementally instead of recalculating
Use appropriate data structure (set vs map)
Sort when beneficial (enables two-pointer approach)
Skip duplicates efficiently (sorted arrays)
Early termination when possible

Next Steps:

Building on these patterns, future topics will cover:

Binary Search (can incorporate two pointers)
Stack and Queue Applications (monotonic structures)
Backtracking (with pruning optimizations)
Dynamic Programming (optimizing with sliding window)

The problems covered here represent fundamental optimization patterns that appear across technical interviews and competitive programming. Master these techniques, and you'll recognize opportunities to optimize O(n²) or O(n³) solutions to O(n) in many problems.

Practice Problems for Mastery:

Two Pointers:

15. 3Sum
16. 3Sum Closest
18. 4Sum
26. Remove Duplicates from Sorted Array
283. Move Zeroes
344. Reverse String
977. Squares of a Sorted Array

Sliding Window:

209. Minimum Size Subarray Sum
438. Find All Anagrams in a String
485. Max Consecutive Ones
643. Maximum Average Subarray I
713. Subarray Product Less Than K
904. Fruit Into Baskets
1004. Max Consecutive Ones III

References:

NeetCode - Algorithms
LeetCode Patterns
Greg Hogg DSA Algorithm YouTube Channel
Algorithm Design Manual by Steven Skiena
Elements of Programming Interviews

This comprehensive guide combines theoretical understanding with practical problem-solving, providing a solid foundation for mastering two pointers and sliding window techniques.

DSA Fundamentals: Linked Lists - Mastering Dynamic Data Structures

jayk0001 — Fri, 21 Nov 2025 00:36:14 +0000

Linked Lists are fundamental data structures that overcome key limitations of arrays, particularly when it comes to insertion and deletion operations. This comprehensive guide explores linked list theory and demonstrates essential patterns through practical LeetCode solutions.

Understanding Linked Lists: Core Concepts

What is a Linked List?

A Linked List is a linear data structure where elements (nodes) are stored in non-contiguous memory locations. Each node contains:

Value: The data being stored
Pointer: Reference to the next node in the sequence

This non-contiguous memory allocation is the fundamental difference from arrays, enabling efficient insertions and deletions.

Linked List vs Array Comparison

Operation	Array	Linked List
Random Access	O(1)	O(n)
Search	O(n)	O(n)
Insertion at Beginning	O(n)	O(1)
Insertion at End	O(1)*	O(n) or O(1)**
Deletion at Beginning	O(n)	O(1)
Memory	Contiguous	Non-contiguous

*Amortized for dynamic arrays
**O(1) if tail pointer is maintained

Types of Linked Lists

Singly Linked List:

One-directional traversal (head → tail)
Each node points to the next node
Less memory overhead

Doubly Linked List:

Bi-directional traversal
Each node has next and prev pointers
More flexible but requires more memory

# Singly Linked List Node Definition
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# Doubly Linked List Node Definition
class DoublyListNode:
    def __init__(self, val=0, next=None, prev=None):
        self.val = val
        self.next = next
        self.prev = prev

Essential Linked List Patterns

Pattern 1: Reverse a Linked List

Problem: Given the head of a singly linked list, reverse the list and return the reversed list.

Approach: Use three pointers (prev, curr, tmp) to iteratively reverse the direction of each node's pointer.

Time Complexity: O(n)

Space Complexity: O(1)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None

        prev = None
        curr = head

        while curr:
            tmp = curr.next      # Save next node
            curr.next = prev     # Reverse pointer
            prev = curr          # Move prev forward
            curr = tmp           # Move curr forward

        return prev  # prev is the new head

Key Insight: Reversing requires maintaining three pointers to avoid losing references during pointer manipulation.

Pattern 2: Detect Cycle (Floyd's Tortoise and Hare)

Problem: Given a linked list, detect if the list has a cycle.

Approach: Use two pointers moving at different speeds. If there's a cycle, the fast pointer will eventually catch up to the slow pointer.

Time Complexity: O(n)

Space Complexity: O(1)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        # Floyd's Cycle Detection Algorithm
        # Use two pointers: slow (1 step) and fast (2 steps)

        slow, fast = head, head

        while fast and fast.next:
            fast = fast.next.next  # Move fast by 2
            slow = slow.next       # Move slow by 1

            if slow == fast:       # Pointers met = cycle exists
                return True

        return False  # fast reached end = no cycle

Key Insight: Floyd's algorithm is elegant because it uses O(1) space instead of a hash set, and the fast pointer will always catch the slow pointer if a cycle exists.

Pattern 3: Merge Two Sorted Lists

Problem: Merge two sorted linked lists into one sorted list.

Approach: Use a dummy node and compare values from both lists, attaching the smaller node to the result list.

Time Complexity: O(n + m)

Space Complexity: O(1)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if not list1 and not list2:
            return None

        # Dummy node to simplify edge cases
        dummy = ListNode()
        curr = dummy

        # Compare and merge
        while list1 and list2:
            if list1.val <= list2.val:
                curr.next = list1
                curr = curr.next
                list1 = list1.next
            else:
                curr.next = list2
                curr = curr.next
                list2 = list2.next

        # Attach remaining nodes
        curr.next = list1 if list1 else list2

        return dummy.next  # Skip dummy node

Key Insight: The dummy node technique simplifies handling edge cases and eliminates special logic for the first node.

Pattern 4: Remove Nth Node From End

Problem: Remove the nth node from the end of a linked list.

Approach: Use two pointers with a gap of n+1 nodes. When the fast pointer reaches the end, the slow pointer will be at the node before the target.

Time Complexity: O(n)

Space Complexity: O(1)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode()
        dummy.next = head

        slow, fast = dummy, dummy

        # Create gap of n+1 between pointers
        for _ in range(n + 1):
            fast = fast.next

        # Move both pointers until fast reaches end
        while fast:
            fast = fast.next
            slow = slow.next

        # Remove the nth node
        slow.next = slow.next.next

        return dummy.next

Key Insight: The two-pointer technique with proper gap allows single-pass removal without knowing the list length.

Pattern 5: Add Two Numbers

Problem: You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each node contains a single digit. Add the two numbers and return the sum as a linked list.

Time Complexity: O(max(n, m))

Space Complexity: O(max(n, m))

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()
        curr = dummy
        carry = 0

        while l1 or l2 or carry:
            l1_val = l1.val if l1 else 0
            l2_val = l2.val if l2 else 0

            curr_sum = l1_val + l2_val + carry
            carry = curr_sum // 10
            digit = curr_sum % 10

            curr.next = ListNode(digit)
            curr = curr.next

            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None

        return dummy.next

Key Insight: Handle carry properly and continue while any value exists (l1, l2, or carry).

Pattern 6: Reorder List

Problem: Given a singly linked list L: L₀ → L₁ → ... → Lₙ₋₁ → Lₙ, reorder it to: L₀ → Lₙ → L₁ → Lₙ₋₁ → L₂ → Lₙ₋₂ → ...

Approach:

Find middle using fast/slow pointers
Reverse second half
Merge two halves alternately

Time Complexity: O(n)

Space Complexity: O(1)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        # Step 1: Find middle
        fast, slow = head, head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next

        # Step 2: Reverse second half
        curr = slow.next
        prev = slow.next = None  # Split the list

        while curr:
            tmp = curr.next
            curr.next = prev
            prev = curr
            curr = tmp

        # Step 3: Merge two halves
        first, second = head, prev
        while second:
            tmp1, tmp2 = first.next, second.next
            first.next, second.next = second, tmp1
            first, second = tmp1, tmp2

Key Insight: Combines three patterns: find middle, reverse list, and merge lists.

Pattern 7: Copy List with Random Pointer

Problem: A linked list has both next and random pointers. Create a deep copy of the list.

Approach: Use a hash map to store old → new node mappings, then connect pointers in a second pass.

Time Complexity: O(n)

Space Complexity: O(n)

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head: 
            return None

        # First pass: Create all nodes and store in hash map
        h_map = {}
        curr = head

        while curr:
            new_node = Node(curr.val)
            h_map[curr] = new_node
            curr = curr.next

        # Second pass: Connect next and random pointers
        curr = head
        while curr:
            if curr.next:
                h_map[curr].next = h_map[curr.next]
            if curr.random:
                h_map[curr].random = h_map[curr.random]
            curr = curr.next

        return h_map[head]

Key Insight: Two-pass algorithm separates node creation from pointer connections, simplifying complex pointer relationships.

Common Linked List Techniques

1. Dummy Node Pattern

Simplifies edge cases (empty list, single node)
Eliminates special handling for head node
Used in: merge lists, insertion, deletion

2. Two Pointer Pattern

Fast/Slow (Floyd's algorithm): cycle detection, find middle
Gap pointers: remove nth from end
Different speeds reveal structural properties

3. Reversal Pattern

Essential for many problems
Can reverse entire list or subsections
Often combined with other patterns

4. Hash Map for Complex Pointers

Track node relationships
Deep copy problems
O(n) space tradeoff for simpler logic

When to Use Linked Lists

Advantages:

✅ Efficient insertions/deletions at beginning (O(1))
✅ Dynamic size (no pre-allocation needed)
✅ Efficient memory usage for sparse data
✅ Natural fit for queue/stack implementations

Disadvantages:

❌ No random access (must traverse from head)
❌ Extra memory for pointers
❌ Poor cache locality
❌ Traversal is O(n) for any position

Practice Strategy

Master the basics first:
- Reverse Linked List
- Detect Cycle
- Merge Two Lists
Learn pointer manipulation:
- Practice drawing pointer diagrams
- Understand null checks
- Handle edge cases (empty, single node)
Recognize patterns:
- Dummy node usage
- Two-pointer techniques
- When to use hash maps
Advanced problems:
- Combine multiple patterns
- Handle complex pointer relationships
- Optimize space complexity

Key Takeaways

Linked Lists excel at insertions/deletions but sacrifice random access
Non-contiguous memory enables O(1) modifications without shifting elements
Two-pointer techniques are powerful for cycle detection and finding middle
Dummy nodes simplify edge case handling
Practice pointer manipulation through visualization and careful null checking

Linked lists may seem simple, but mastering pointer manipulation and recognizing common patterns is crucial for technical interviews and real-world applications like LRU caches, undo functionality, and graph representations.

Continue your DSA journey by exploring more data structures and algorithms. Practice these patterns on LeetCode and gradually increase problem difficulty to build mastery.

DSA Fundamentals: Greedy Algorithms - From Theory to LeetCode Practice

jayk0001 — Wed, 19 Nov 2025 00:24:24 +0000

Greedy algorithms are a powerful problem-solving paradigm that makes locally optimal choices at each step, hoping to find a global optimum. While not always applicable, greedy algorithms provide elegant and efficient solutions to many optimization problems, especially those involving sequences, intervals, and resource allocation.

This comprehensive guide combines theoretical understanding with practical problem-solving, featuring solutions to essential LeetCode problems that demonstrate core greedy algorithmic patterns.

Understanding Greedy Algorithms

Greedy Algorithm Fundamentals

Greedy algorithms make the best local choice at each decision point, without considering future consequences. The key insight is that sometimes, making locally optimal choices leads to a globally optimal solution.

When to Use Greedy Algorithms

Greedy algorithms work well when:

Optimal substructure: Optimal solution contains optimal solutions to subproblems
Greedy choice property: Locally optimal choice leads to globally optimal solution
No need to reconsider: Once a choice is made, it's never reconsidered
Problem can be solved incrementally: Build solution step by step

Common problem types:

Maximum/minimum subarray problems
Jump and reachability problems
Interval scheduling
Resource allocation
Path finding with constraints

Greedy vs Dynamic Programming

Aspect	Greedy	Dynamic Programming
Decision making	Make best local choice	Consider all possibilities
Subproblems	Don't revisit decisions	May revisit subproblems
Time complexity	Usually O(n) or O(n log n)	Often O(n²) or exponential
Space complexity	Usually O(1)	Often O(n) or O(n²)
Proof	Requires proof of correctness	Naturally optimal
When to use	Greedy choice property holds	Overlapping subproblems

Key Greedy Patterns

1. Maximum/Minimum Subarray:

Track running sum/max/min
Reset when condition violated
Update global maximum/minimum

2. Jump Problems:

Track maximum reachable position
Make greedy choice to jump as far as possible
Verify reachability incrementally

3. Resource Allocation:

Process items in optimal order
Make greedy choices based on constraints
Track resource usage

4. Interval Problems:

Sort by specific criteria
Make greedy choices about which intervals to include
Process in order

Time Complexity Analysis

Pattern	Time Complexity	Space Complexity	Notes
Single pass greedy	O(n)	O(1)	One iteration through data
Greedy with sorting	O(n log n)	O(1)	Sorting dominates
Greedy with heap	O(n log n)	O(n)	Heap operations
Multiple passes	O(n)	O(1)	Forward and backward passes

Essential LeetCode Problems & Solutions

Let's explore fundamental greedy algorithm problems that demonstrate core decision-making patterns.

1. Maximum Subarray (LeetCode 53) - Kadane's Algorithm

Problem: Find the contiguous subarray with the largest sum.

Approach: Kadane's algorithm - track running sum, reset to 0 when sum becomes negative (greedy choice: discard negative prefix).

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        curr_sum = 0
        max_sum = float('-inf')

        for num in nums:
            # Greedy choice: reset if current sum is negative
            # Negative prefix can only reduce future sums
            if curr_sum < 0:
                curr_sum = 0

            # Add current number to running sum
            curr_sum += num

            # Update maximum sum seen so far
            max_sum = max(max_sum, curr_sum)

        return max_sum

Time Complexity: O(n) - Single pass through array

Space Complexity: O(1) - Only tracking two variables

Key Concepts:

Greedy reset: When curr_sum < 0, reset to 0 (negative prefix hurts future sums)
Kadane's insight: Maximum subarray ending at position i is either:
- Extend previous subarray: curr_sum + nums[i]
- Start new subarray: nums[i] (when previous sum is negative)
Global maximum tracking: Keep track of maximum sum across all positions
No need for DP table: Greedy approach eliminates need for O(n) space

Example Walkthrough:

Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

i=0: num=-2, curr_sum=-2 < 0 → reset to 0, curr_sum=0, max_sum=-2
i=1: num=1, curr_sum=1, max_sum=1
i=2: num=-3, curr_sum=-2 < 0 → reset to 0, curr_sum=0, max_sum=1
i=3: num=4, curr_sum=4, max_sum=4
i=4: num=-1, curr_sum=3, max_sum=4
i=5: num=2, curr_sum=5, max_sum=5
i=6: num=1, curr_sum=6, max_sum=6
i=7: num=-5, curr_sum=1, max_sum=6
i=8: num=4, curr_sum=5, max_sum=6

Result: 6 (subarray [4, -1, 2, 1])

Why Greedy Works:

If we have a negative prefix sum, starting fresh from current position always gives better or equal result
We never need to consider keeping a negative prefix because it can only reduce future sums
This local optimal choice (reset when negative) leads to global optimum

2. Jump Game (LeetCode 55)

Problem: Determine if you can reach the last index starting from index 0. Each element represents maximum jump length.

Approach 1: Backward Greedy (Target Tracking)

Start from the end and work backwards, tracking the target index we need to reach.

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        target = n - 1  # Start with last index as target

        # Work backwards from second-to-last index
        for i in range(n-1, -1, -1):
            # If we can reach target from current position, update target
            if nums[i] + i >= target:
                target = i

        # If target reached index 0, we can jump from start
        return target == 0

Time Complexity: O(n) - Single backward pass

Space Complexity: O(1) - Only tracking target index

Key Concepts:

Backward approach: Start from goal, work backwards to start
Target update: If position i can reach current target, i becomes new target
Greedy choice: If multiple positions can reach target, closest one is sufficient
Final check: If target reaches index 0, path exists

Example Walkthrough:

Input: [2, 3, 1, 1, 4]

Initial: target = 4 (last index)
i=3: nums[3]=1, 3+1=4 >= 4 → target = 3
i=2: nums[2]=1, 2+1=3 >= 3 → target = 2
i=1: nums[1]=3, 1+3=4 >= 2 → target = 1
i=0: nums[0]=2, 0+2=2 >= 1 → target = 0

target == 0 → return True

Approach 2: Forward Greedy (Maximum Reach)

Track maximum reachable position while iterating forward.

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        target = 0  # Maximum reachable position

        for i in range(n):
            # If current index is beyond reachable, impossible
            if i > target:
                return False

            # Update maximum reachable position
            target = max(target, nums[i] + i)

        # Check if we can reach last index
        return target >= n - 1

Time Complexity: O(n) - Single forward pass

Space Complexity: O(1) - Only tracking maximum reach

Key Concepts:

Forward approach: Process from start to end
Reachability check: If i > target, we can't reach position i
Greedy update: Always update to maximum reachable position
Early termination: Return False immediately if unreachable position found

Example Walkthrough:

Input: [2, 3, 1, 1, 4]

i=0: target=0, i=0 <= 0, target = max(0, 0+2) = 2
i=1: target=2, i=1 <= 2, target = max(2, 1+3) = 4
i=2: target=4, i=2 <= 4, target = max(4, 2+1) = 4
i=3: target=4, i=3 <= 4, target = max(4, 3+1) = 4
i=4: target=4, i=4 <= 4, target = max(4, 4+4) = 8

target=8 >= 4 → return True

Comparison:

Backward approach: More intuitive for "can we reach goal" problems
Forward approach: More natural for "track progress" problems
Both are O(n) time and O(1) space
Forward approach allows early termination

3. Gas Station (LeetCode 134)

Problem: Find starting gas station index to complete circular route. Return -1 if impossible.

Approach: Greedy - if total gas >= total cost, solution exists. Track tank level, reset starting point when tank goes negative.

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        # Early termination: if total gas < total cost, impossible
        if sum(gas) < sum(cost):
            return -1

        index, tank = 0, 0

        for i in range(len(gas)):
            # Calculate net gas gain/loss at station i
            tank += (gas[i] - cost[i])

            # Greedy choice: if tank negative, can't start from any previous station
            # Reset starting point to next station
            if tank < 0:
                tank = 0
                index = i + 1

        return index

Time Complexity: O(n) - Single pass through stations

Space Complexity: O(1) - Only tracking index and tank

Key Concepts:

Total gas check: If sum(gas) < sum(cost), impossible to complete circuit
Net gas calculation: gas[i] - cost[i] represents net gain/loss
Greedy reset: When tank goes negative, previous starting points won't work
Why it works: If we can't reach station j from station i, we can't reach j from any station between i and j
Single pass: After checking total gas, one pass finds starting point

Example Walkthrough:

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]

Total check: sum(gas)=15, sum(cost)=15 → possible

i=0: tank = 0 + (1-3) = -2 < 0 → reset, index=1, tank=0
i=1: tank = 0 + (2-4) = -2 < 0 → reset, index=2, tank=0
i=2: tank = 0 + (3-5) = -2 < 0 → reset, index=3, tank=0
i=3: tank = 0 + (4-1) = 3, index=3
i=4: tank = 3 + (5-2) = 6, index=3

Return index=3

Why Greedy Reset Works:

If we can't reach station j from station i, starting from any station between i and j also fails
This is because we would have even less gas when reaching those intermediate stations
Therefore, we can safely skip all previous starting points and try from j+1

4. Jump Game II (LeetCode 45)

Problem: Find minimum number of jumps to reach last index. Guaranteed that you can reach the last index.

Approach: Greedy - track current jump's end boundary and farthest reachable position. Jump when reaching current boundary.

class Solution:
    def jump(self, nums: List[int]) -> int:
        # Edge case: already at last index
        if len(nums) == 1:
            return 0

        jump, end, target = 0, 0, 0

        # Process all positions except last (don't need to jump from last)
        for i in range(len(nums) - 1):
            # Update farthest position reachable from current position
            target = max(target, nums[i] + i)

            # When we reach end of current jump's range, make a jump
            if i == end:
                jump += 1
                end = target  # Update to farthest reachable position

        return jump

Time Complexity: O(n) - Single pass through array

Space Complexity: O(1) - Only tracking jump count and boundaries

Key Concepts:

Greedy choice: Always jump to farthest reachable position
Jump boundaries: end represents end of current jump's range
Target tracking: target tracks farthest position reachable with current jumps
Jump trigger: When i == end, we've exhausted current jump's range, must jump
Optimal substructure: Minimum jumps to position i + optimal jump from i = global optimum

Example Walkthrough:

Input: [2, 3, 1, 1, 4]

i=0: target = max(0, 0+2) = 2, i=0 == end=0 → jump=1, end=2
i=1: target = max(2, 1+3) = 4, i=1 != end=2
i=2: target = max(4, 2+1) = 4, i=2 == end=2 → jump=2, end=4
i=3: target = max(4, 3+1) = 4, i=3 != end=4
(loop ends, i < len(nums)-1)

Result: 2 jumps
Path: 0 → 1 → 4 (or 0 → 1 → 3 → 4)

Why Greedy Works:

At each position, jumping to farthest reachable position gives maximum flexibility
This greedy choice (maximize reach) minimizes number of jumps needed
If we can reach position j with k jumps, we can reach any position before j with ≤ k jumps
Therefore, greedy approach finds minimum jumps

Visualization:

nums = [2, 3, 1, 1, 4]
       0  1  2  3  4

Jump 1: Can reach positions 0-2
  - From 0: can reach up to 2
  - Choose position 1 (greedy: farthest reach from 1 is 4)

Jump 2: Can reach positions 1-4
  - From 1: can reach up to 4 (reached!)

Core Algorithm Patterns from Today's Problems

1. Kadane's Algorithm Pattern (Maximum Subarray)

When to use:

Finding maximum/minimum sum subarray
Problems involving contiguous sequences
Need to track running sum with reset condition

Examples: Maximum Subarray, Maximum Product Subarray

Key characteristics:

Track running sum/product
Reset when condition violated (e.g., negative sum)
Update global maximum/minimum
O(n) time, O(1) space

Template:

def kadane_algorithm(nums):
    curr_sum = 0
    max_sum = float('-inf')

    for num in nums:
        # Greedy reset condition
        if curr_sum < 0:  # or other condition
            curr_sum = 0

        curr_sum += num
        max_sum = max(max_sum, curr_sum)

    return max_sum

2. Reachability Tracking Pattern

When to use:

Jump problems
Can we reach a target?
Maximum reachable position problems

Examples: Jump Game, Jump Game II

Key characteristics:

Track maximum reachable position
Check if current position is reachable
Update reach based on current position's capability
Forward or backward iteration

Template (Forward):

def can_reach_forward(nums):
    max_reach = 0

    for i in range(len(nums)):
        if i > max_reach:
            return False
        max_reach = max(max_reach, i + nums[i])

    return max_reach >= len(nums) - 1

Template (Backward):

def can_reach_backward(nums):
    target = len(nums) - 1

    for i in range(len(nums) - 1, -1, -1):
        if i + nums[i] >= target:
            target = i

    return target == 0

3. Boundary-Based Jumping Pattern

When to use:

Minimum jumps problems
Problems with jump boundaries
Need to track jump ranges

Example: Jump Game II

Key characteristics:

Track current jump's end boundary
Track farthest reachable position
Jump when reaching boundary
Greedy: always maximize reach

Template:

def min_jumps(nums):
    if len(nums) == 1:
        return 0

    jumps = 0
    end = 0  # End of current jump's range
    farthest = 0  # Farthest position reachable

    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])

        if i == end:  # Reached boundary, must jump
            jumps += 1
            end = farthest

    return jumps

4. Circular Route Pattern

When to use:

Circular/cyclic problems
Problems with net gain/loss
Need to find starting point

Example: Gas Station

Key characteristics:

Check total feasibility first
Track running sum/tank
Reset starting point when sum goes negative
Single pass finds solution

Template:

def circular_route(gain, cost):
    # Check total feasibility
    if sum(gain) < sum(cost):
        return -1

    start = 0
    tank = 0

    for i in range(len(gain)):
        tank += (gain[i] - cost[i])

        if tank < 0:
            tank = 0
            start = i + 1

    return start

Performance Optimization Tips

1. Early Termination

# Jump Game: return False immediately when unreachable
def canJump(nums):
    max_reach = 0
    for i in range(len(nums)):
        if i > max_reach:
            return False  # Early exit
        max_reach = max(max_reach, i + nums[i])
    return True

Key insight: Stop processing as soon as answer is determined.

2. Total Feasibility Check

# Gas Station: check total before processing
def canCompleteCircuit(gas, cost):
    if sum(gas) < sum(cost):
        return -1  # Early exit, no solution possible

    # ... rest of logic

Key insight: Quick feasibility check can save unnecessary computation.

3. Reset Strategy in Kadane's

# Reset when negative, but consider edge case
def maxSubArray(nums):
    curr_sum = 0
    max_sum = float('-inf')  # Handle all negative numbers

    for num in nums:
        if curr_sum < 0:
            curr_sum = 0
        curr_sum += num
        max_sum = max(max_sum, curr_sum)

    return max_sum

Key insight: Initialize max_sum to negative infinity to handle edge cases.

4. Boundary Management

# Jump Game II: process up to len(nums)-1
def jump(nums):
    for i in range(len(nums) - 1):  # Don't process last index
        # ... logic

Key insight: Don't jump from last position, process only necessary indices.

Common Pitfalls and Solutions

1. Incorrect Reset Condition in Kadane's

# Wrong: Reset when sum equals 0
if curr_sum == 0:
    curr_sum = 0  # Redundant, and misses negative numbers

# Correct: Reset when sum is negative
if curr_sum < 0:
    curr_sum = 0  # Negative prefix hurts future sums

2. Off-by-One in Jump Problems

# Wrong: Check if we can reach last index incorrectly
return target >= len(nums)  # Off by one

# Correct: Last index is len(nums) - 1
return target >= len(nums) - 1

3. Missing Edge Cases

# Wrong: Assume array has at least 2 elements
def jump(nums):
    jump, end, target = 0, 0, 0
    # ... might fail for single element

# Correct: Handle edge case
def jump(nums):
    if len(nums) == 1:
        return 0
    # ... rest of logic

4. Incorrect Gas Station Logic

# Wrong: Don't check total feasibility
def canCompleteCircuit(gas, cost):
    index, tank = 0, 0
    for i in range(len(gas)):
        tank += (gas[i] - cost[i])
        if tank < 0:
            tank = 0
            index = i + 1
    return index  # Might return wrong answer if impossible

# Correct: Check total first
def canCompleteCircuit(gas, cost):
    if sum(gas) < sum(cost):
        return -1
    # ... rest of logic

5. Not Updating Maximum Correctly

# Wrong: Update before checking condition
def canJump(nums):
    max_reach = 0
    for i in range(len(nums)):
        max_reach = max(max_reach, i + nums[i])  # Update first
        if i > max_reach:  # Check after update
            return False

# Correct: Check before updating
def canJump(nums):
    max_reach = 0
    for i in range(len(nums)):
        if i > max_reach:  # Check first
            return False
        max_reach = max(max_reach, i + nums[i])  # Update after

Time Complexity Comparison

Problem Complexity Summary

Problem	Brute Force	Greedy	Space	Technique
Maximum Subarray	O(n²)	O(n)	O(1)	Kadane's Algorithm
Jump Game	O(2^n)	O(n)	O(1)	Reachability Tracking
Gas Station	O(n²)	O(n)	O(1)	Circular Route
Jump Game II	O(n²)	O(n)	O(1)	Boundary Jumping

Why Greedy is Efficient

Maximum Subarray:

Brute force: Check all subarrays → O(n²)
Greedy: Single pass with reset → O(n)
Savings: O(n²) → O(n)

Jump Problems:

Brute force: Try all paths → O(2^n) or O(n²)
Greedy: Track maximum reach → O(n)
Savings: Exponential/polynomial → O(n)

Gas Station:

Brute force: Try each starting point → O(n²)
Greedy: Single pass with reset → O(n)
Savings: O(n²) → O(n)

Conclusion

Greedy algorithms provide elegant and efficient solutions to many optimization problems by making locally optimal choices. Key takeaways:

Core Concepts Mastered:

Greedy Fundamentals:

Local optimal choices lead to global optimum when greedy choice property holds
No reconsideration - once a choice is made, it's final
Optimal substructure - optimal solution contains optimal subproblem solutions
When to use - problems with greedy choice property

Problem Types:

Maximum subarray: Kadane's algorithm with reset strategy
Jump problems: Reachability tracking and boundary management
Circular routes: Total feasibility + single pass with reset
Resource allocation: Greedy selection based on constraints

Essential Patterns Mastered Today:

Pattern 1: Kadane's Algorithm (Maximum Subarray)

Pattern 2: Reachability Tracking (Jump Game)

Pattern 3: Boundary-Based Jumping (Jump Game II)

Pattern 4: Circular Route (Gas Station)

Problem-Solving Strategies:

Identify greedy choice property - can local optimal lead to global optimal?
Track running state - sum, reach, tank, etc.
Reset when beneficial - negative prefixes, unreachable positions
Check feasibility first - total gas check, reachability validation
Update maximums/minimums - track best value seen so far
Handle edge cases - single element, all negative, impossible cases

Optimization Principles:

Make locally optimal choices - maximize/minimize at each step
Reset when condition violated - negative sums, unreachable positions
Track boundaries and limits - jump ranges, reachable positions
Early termination - stop when answer determined
Single pass when possible - O(n) solutions preferred

Greedy vs Dynamic Programming:

Use Greedy when:

Greedy choice property holds
Optimal substructure exists
Can make decision without considering all possibilities
Want O(n) or O(n log n) solution

Use DP when:

Need to consider all possibilities
Overlapping subproblems
Greedy choice doesn't guarantee optimal
Need to revisit decisions

Next Steps:

Building on greedy fundamentals, future topics will cover:

Interval Scheduling (greedy selection criteria)
Huffman Coding (greedy tree construction)
Activity Selection (greedy interval problems)
Fractional Knapsack (greedy with sorting)
Minimum Spanning Trees (Kruskal's, Prim's algorithms)

The problems covered here represent fundamental greedy patterns that appear across technical interviews and optimization problems. Master these concepts, and you'll recognize opportunities to apply greedy thinking to transform complex problems into elegant, efficient solutions.

Practice Problems for Mastery:

Basic Greedy Problems:

53. Maximum Subarray
55. Jump Game
45. Jump Game II
134. Gas Station
121. Best Time to Buy and Sell Stock
122. Best Time to Buy and Sell Stock II

Intermediate Greedy Problems:

135. Candy
55. Jump Game
376. Wiggle Subsequence
392. Is Subsequence
406. Queue Reconstruction by Height

Advanced Greedy Problems:

330. Patching Array
435. Non-overlapping Intervals
452. Minimum Number of Arrows to Burst Balloons
621. Task Scheduler
763. Partition Labels

References:

NeetCode - Algorithms
LeetCode Patterns
Greg Hogg DSA Algorithm YouTube Channel
Algorithm Design Manual by Steven Skiena
Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein
Grokking Algorithms by Aditya Bhargava

This comprehensive guide combines theoretical understanding with practical problem-solving, providing a solid foundation for mastering greedy algorithms and optimization strategies.

DSA Fundamentals: Arrays & Strings - From Theory to LeetCode Practice

jayk0001 — Sat, 15 Nov 2025 05:08:31 +0000

Data Structures and Algorithms form the foundation of efficient programming. Today, we'll dive deep into Arrays and Strings - two fundamental data structures that appear in virtually every coding interview and real-world application.

This comprehensive guide combines theoretical understanding with practical problem-solving, featuring solutions to essential LeetCode problems that demonstrate core concepts.

Understanding Arrays: Static vs Dynamic

Array Fundamentals

Arrays are mutable (changeable) collections that store elements in contiguous memory locations, providing efficient random access.

# Array mutability example
A = [1, 2, 3, 4, 5]
A[3] = 1  # Modify element at index 3
print(A)  # Output: [1, 2, 3, 1, 5]

Static Arrays vs Dynamic Arrays

Static Arrays:

Fixed size at creation time
To change size: copy all elements → create new array → paste elements
Memory allocated at compile time

Dynamic Arrays:

Size can grow/shrink during runtime
Programming language automatically handles expansion
Memory allocated at runtime (Python lists, JavaScript arrays)

Array Operations Time Complexity

Operation	Time Complexity	Notes
Random Access	O(1)	Direct index access
Search (`in` operator)	O(n)	Linear scan required
Append to end	O(1)*	*Amortized average
Pop from end	O(1)	Direct removal
Insert (not at end)	O(n)	Shift elements required
Delete (not at end)	O(n)	Shift elements required
Modify element	O(1)	Direct access and change

Understanding Strings: Immutability Matters

Strings are immutable - once created, they cannot be changed. Any "modification" creates a new string object.

String vs Array Operations Comparison

Operation	Array/List	String (Immutable)
Appending to end	O(1)* Amortized	O(n)
Popping from end	O(1)	O(n)
Insertion (not from end)	O(n)	O(n)
Deletion (not from end)	O(n)	O(n)
Modifying an element	O(1)	O(n)
Random Access	O(1)	O(1)
Searching	O(n)	O(n)

Key Insight: String immutability means every modification operation creates a new string, leading to O(n) complexity even for simple operations.

Essential LeetCode Problems & Solutions

Let's explore fundamental array and string problems that demonstrate core algorithmic patterns.

1. Valid Sudoku (LeetCode 36)

Problem: Determine if a 9x9 Sudoku board is valid.

Approach: Use hash sets to track seen numbers in rows, columns, and 3x3 boxes.

def isValidSudoku(board):
    # Create sets for rows, columns, and 3x3 boxes
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]

    for row in range(9):
        for col in range(9):
            current_val = board[row][col]

            # Skip empty cells
            if current_val == '.':
                continue

            # Calculate box index: (row//3) * 3 + (col//3)
            box_index = (row // 3) * 3 + (col // 3)

            # Check if number already exists
            if (current_val in rows[row] or 
                current_val in cols[col] or 
                current_val in boxes[box_index]):
                return False

            # Add to respective sets
            rows[row].add(current_val)
            cols[col].add(current_val)
            boxes[box_index].add(current_val)

    return True

Time Complexity: O(1) - Fixed 9x9 grid = 81 operations
Space Complexity: O(1) - Fixed number of sets

Key Concepts:

Hash Set Usage: Efficient O(1) lookup for duplicates
Box Index Calculation: (row//3) * 3 + (col//3) maps 2D coordinates to box number
Early Termination: Return False immediately when duplicate found

2. Longest Consecutive Sequence (LeetCode 128)

Problem: Find the length of the longest consecutive elements sequence in O(n) time.

Approach: Use hash set to identify sequence starts and extend sequences.

def longestConsecutive(nums):
    if not nums:
        return 0

    # Convert to set for O(1) lookup and remove duplicates
    num_set = set(nums)
    longest = 0

    for num in num_set:
        # Check if this can be a sequence start
        if num - 1 not in num_set:
            current_num = num
            current_length = 1

            # Extend the sequence
            while current_num + 1 in num_set:
                current_num += 1
                current_length += 1

            # Update longest sequence found
            longest = max(longest, current_length)

    return longest

Time Complexity: O(n) - Each number visited at most twice
Space Complexity: O(n) - Hash set storage

Key Concepts:

Sequence Start Identification: Only start counting when num - 1 not in set
Hash Set Optimization: O(1) lookup prevents nested loops
Duplicate Handling: Set automatically removes duplicates

3. Product of Array Except Self (LeetCode 238)

Problem: Return array where each element is the product of all elements except itself (no division allowed).

Approach: Two-pass algorithm - left products, then right products.

def productExceptSelf(nums):
    n = len(nums)
    result = [1] * n

    # First pass: accumulate products to the left
    for i in range(1, n):
        result[i] = result[i-1] * nums[i-1]

    # Second pass: multiply by products to the right
    right_product = 1
    for i in range(n-1, -1, -1):
        result[i] *= right_product
        right_product *= nums[i]

    return result

# Example walkthrough:
# nums = [1, 2, 3, 4]
# After first pass:  [1, 1, 2, 6]  (left products)
# After second pass: [24, 12, 8, 6] (left * right products)

Time Complexity: O(n) - Two passes through array
Space Complexity: O(1) - Only using result array (required output)

Key Concepts:

Two-Pass Strategy: Separate left and right product calculations
Space Optimization: Use result array to store intermediate values
No Division Constraint: Handles edge cases like zeros naturally

4. Top K Frequent Elements (LeetCode 347)

Problem: Return k most frequent elements from an array.

Approach 1: Counter + Sorting

from collections import Counter

def topKFrequent(nums, k):
    # Count frequencies
    counter = Counter(nums)

    # Sort by frequency (descending)
    sorted_items = sorted(counter.items(), key=lambda x: x[1], reverse=True)

    # Extract first k elements
    result = []
    for i in range(k):
        result.append(sorted_items[i][0])

    return result

Time Complexity: O(n log n) - Sorting dominates
Space Complexity: O(n) - Counter storage

Approach 2: Counter + Bucket Sort (Optimal)

from collections import Counter

def topKFrequent(nums, k):
    counter = Counter(nums)
    n = len(nums)

    # Create buckets for each possible frequency (0 to n)
    buckets = [[] for _ in range(n + 1)]

    # Place numbers in buckets based on frequency
    for num, freq in counter.items():
        buckets[freq].append(num)

    # Collect k most frequent elements (iterate backwards)
    result = []
    for freq in range(n, -1, -1):
        for num in buckets[freq]:
            result.append(num)
            if len(result) == k:
                return result

    return result

Time Complexity: O(n) - Linear bucket sort
Space Complexity: O(n) - Bucket array

Key Concepts:

Bucket Sort Application: Frequency as bucket index
Trade-off Analysis: Sorting vs bucket sort based on constraints
Early Termination: Stop when k elements found

5. Group Anagrams (LeetCode 49)

Problem: Group strings that are anagrams of each other.

Approach 1: Sorting as Key

from collections import defaultdict

def groupAnagrams(strs):
    groups = defaultdict(list)

    for s in strs:
        # Use sorted string as key
        key = ''.join(sorted(s))
        groups[key].append(s)

    return list(groups.values())

Time Complexity: O(n * m log m) where n = number of strings, m = average string length
Space Complexity: O(n * m) - Storage for groups

Approach 2: Character Count as Key (Optimal)

from collections import defaultdict

def groupAnagrams(strs):
    groups = defaultdict(list)

    for s in strs:
        # Create character count array
        char_count = [0] * 26
        for char in s:
            char_count[ord(char) - ord('a')] += 1

        # Use tuple of counts as key (arrays aren't hashable)
        key = tuple(char_count)
        groups[key].append(s)

    return list(groups.values())

Time Complexity: O(n * m) - Linear in string length
Space Complexity: O(n * m) - Storage for groups

Key Concepts:

Anagram Property: Same character frequencies
Key Generation: Sorted string vs character count
Hashable Keys: Tuple conversion for dictionary keys

6. Two Sum (LeetCode 1)

Problem: Find two numbers that add up to target.

Approach: Hash map for complement lookup.

def twoSum(nums, target):
    seen = {}  # value -> index mapping

    for i, num in enumerate(nums):
        complement = target - num

        if complement in seen:
            return [seen[complement], i]

        seen[num] = i

    return []  # No solution found

Time Complexity: O(n) - Single pass
Space Complexity: O(n) - Hash map storage

Key Concepts:

Complement Strategy: target - current = needed value
Hash Map Optimization: O(1) lookup vs O(n) nested loops
Index Tracking: Store positions for result

7. Valid Anagram (LeetCode 242)

Problem: Determine if two strings are anagrams.

Approach 1: Sorting

def isAnagram(s, t):
    return sorted(s) == sorted(t)

Time Complexity: O(n log n) - Sorting
Space Complexity: O(1) - Ignoring sort space

Approach 2: Character Frequency (Optimal)

from collections import Counter

def isAnagram(s, t):
    return Counter(s) == Counter(t)

# Or manual counting:
def isAnagram(s, t):
    if len(s) != len(t):
        return False

    char_count = {}

    # Count characters in s
    for char in s:
        char_count[char] = char_count.get(char, 0) + 1

    # Subtract characters in t
    for char in t:
        if char not in char_count:
            return False
        char_count[char] -= 1
        if char_count[char] == 0:
            del char_count[char]

    return len(char_count) == 0

Time Complexity: O(n) - Linear scan
Space Complexity: O(k) where k = unique characters

8. Contains Duplicate (LeetCode 217)

Problem: Check if array contains any duplicates.

Approach 1: Hash Set

def containsDuplicate(nums):
    seen = set()

    for num in nums:
        if num in seen:
            return True
        seen.add(num)

    return False

Approach 2: Set Length Comparison

def containsDuplicate(nums):
    return len(set(nums)) != len(nums)

Time Complexity: O(n) - Single pass or set creation
Space Complexity: O(n) - Hash set storage

Key Concepts:

Early Termination: Return immediately when duplicate found
Set Properties: Automatic duplicate removal
Length Comparison: Elegant one-liner solution

Core Algorithm Patterns from Today's Problems

1. Hash-Based Solutions (Primary Pattern)

When to use: Fast lookups, duplicate detection, complement finding
Examples: Two Sum, Valid Sudoku, Contains Duplicate, Longest Consecutive Sequence
Key insight: Trade O(n) space for O(1) lookup time
Implementation: Hash Sets for membership, Hash Maps for key-value pairs

2. Frequency Analysis (Primary Pattern)

When to use: Anagrams, character counting, top-k problems
Examples: Group Anagrams, Valid Anagram, Top K Frequent Elements
Tools: Counter, hash maps, bucket sort
Optimization: Linear time frequency-based solutions instead of sorting

3. Multi-Pass Array Processing

When to use: Complex calculations requiring multiple scans
Example: Product of Array Except Self (left pass + right pass)
Benefit: Maintain O(n) time while avoiding division or complex logic
Pattern: Accumulate information in one direction, then process in reverse

4. Set Operations for Uniqueness

When to use: Removing duplicates, finding unique elements
Examples: Longest Consecutive Sequence (duplicate removal), Contains Duplicate
Advantage: Automatic duplicate handling with O(1) operations
Common trick: Compare len(set(array)) vs len(array) for duplicate detection

Performance Optimization Tips

1. Choose Right Data Structure

# Slow: List membership testing
if item in my_list:  # O(n)

# Fast: Set membership testing  
if item in my_set:   # O(1)

2. Minimize String Operations

# Slow: String concatenation in loop
result = ""
for char in chars:
    result += char  # O(n) each iteration

# Fast: Join operation
result = ''.join(chars)  # O(n) total

3. Early Termination

# Stop as soon as condition is met
for item in items:
    if condition(item):
        return True  # Don't continue unnecessary iterations
return False

4. Space-Time Trade-offs

# Time-optimized (more space)
seen = set(nums)  # O(n) space
return len(seen) != len(nums)  # O(n) time

# Space-optimized (more time)  
nums.sort()  # O(1) space (in-place)
for i in range(1, len(nums)):  # O(n log n) time
    if nums[i] == nums[i-1]:
        return True

Common Pitfalls and Solutions

1. Index Out of Bounds

# Dangerous
for i in range(len(arr)):
    if arr[i+1] > arr[i]:  # Error when i = len(arr)-1

# Safe
for i in range(len(arr) - 1):
    if arr[i+1] > arr[i]:

2. Modifying List While Iterating

# Dangerous
for item in my_list:
    if condition(item):
        my_list.remove(item)  # Changes list size during iteration

# Safe
my_list = [item for item in my_list if not condition(item)]

3. String Immutability Oversight

# Inefficient for large strings
def reverse_string(s):
    result = ""
    for char in reversed(s):
        result += char  # O(n²) due to string immutability
    return result

# Efficient
def reverse_string(s):
    return s[::-1]  # O(n) built-in operation

Conclusion

Arrays and strings form the foundation of algorithmic problem-solving. Key takeaways:

Core Concepts Mastered:

Array mutability vs string immutability and their performance implications
Static vs dynamic arrays and when to use each
Time complexity analysis for common operations
Hash-based optimizations for O(1) lookups

Essential Patterns Mastered Today:

Hash-based lookups (Two Sum, Valid Sudoku, Contains Duplicate)
Frequency analysis (anagrams, Top K problems)
Multi-pass processing (Product Except Self)
Set operations (duplicate detection, uniqueness)

Problem-Solving Strategies:

Choose appropriate data structures based on operation requirements
Consider space-time trade-offs for optimization
Use early termination when possible
Leverage built-in functions for common operations

Next Steps:

Building on this foundation, future topics will cover:

Linked Lists and Pointers
Stack and Queue Applications
Tree and Graph Traversals
Dynamic Programming Patterns

The problems covered here represent fundamental patterns that appear across technical interviews and real-world applications. Master these concepts, and you'll have a solid foundation for tackling more complex algorithmic challenges.

References:

Greg Hogg DSA Algorithm YouTube Channel
Algorithm Design Manual by Steven Skiena
Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein
Grokking Algorithms by Aditya Bhargava

This comprehensive guide combines theoretical understanding with practical problem-solving, providing a solid foundation for data structures and algorithms mastery.

DSA Fundamentals: Binary Trees - Mastering Tree Traversal and Recursion

jayk0001 — Wed, 12 Nov 2025 23:39:59 +0000

Binary Trees are hierarchical data structures that form the foundation of many advanced algorithms and real-world applications. Unlike linear structures (arrays, linked lists), trees represent non-linear relationships, making them ideal for representing hierarchies, organizing data efficiently, and solving complex algorithmic problems.

This comprehensive guide explores binary tree theory, traversal techniques, and demonstrates essential patterns through 15+ LeetCode problems.

Understanding Binary Trees: Core Concepts

What is a Binary Tree?

A Binary Tree is a non-linear data structure where each node has at most two children, referred to as the left child and right child. Trees are a subcategory of directed graphs, with edges pointing from parent to child.

# Binary Tree Node Definition
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Essential Tree Terminology

Basic Terms:

Node: Individual element containing a value
Root: Topmost node (no parent)
Parent: Node with children
Child: Node descended from another node
Leaf: Node with no children
Branch: Edge connecting parent to child
Subtree: Tree formed by a node and its descendants

Tree Properties:

Height (Depth): Longest path from root to leaf
Width (Breadth): Maximum number of nodes at any level
Level: Distance from root (root is level 0)

Types of Binary Trees

Complete Binary Tree:

All levels fully filled except possibly the last
Last level filled from left to right
Efficient for heap implementations

Full Binary Tree:

Every node has either 0 or 2 children
No node has only one child

Perfect Binary Tree:

All internal nodes have two children
All leaves at same level
Total nodes = 2^(h+1) - 1

LeetCode Representation:
Binary trees in LeetCode often appear as arrays with null values representing missing nodes:

[3, 9, 20, null, null, 15, 7]
     3
   /   \
  9    20
       /  \
      15   7

Tree Traversal: DFS vs BFS

Understanding traversal is crucial for solving tree problems. Two main approaches exist: Depth-First Search (DFS) and Breadth-First Search (BFS).

DFS Traversal (Stack/Recursion)

DFS explores as deep as possible before backtracking. Three ordering patterns exist:

1. Preorder (Node → Left → Right)

Process root first
Use case: Copying tree, creating prefix expressions

2. Inorder (Left → Node → Right)

Process left subtree, then root, then right
Special property: Returns sorted order for BST

3. Postorder (Left → Right → Node)

Process children before parent
Use case: Deleting tree, calculating tree properties

Time Complexity: O(n) - visit each node once

Space Complexity: O(h) - recursion stack, worst case O(n)

BFS Traversal (Queue)

BFS explores level by level (also called Level Order Traversal).

Characteristics:

Uses queue data structure
Processes nodes level by level
Great for finding shortest path, min depth

Time Complexity: O(n)

Space Complexity: O(w) - queue size, worst case O(n)

Essential Binary Tree Patterns

Pattern 1: Invert Binary Tree

Problem: Given the root of a binary tree, invert the tree and return its root (mirror image).

Approach: Recursively swap left and right children for every node.

Time: O(n) | Space: O(h)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        # Base case: empty tree
        if not root:
            return root

        # Swap children
        root.left, root.right = root.right, root.left

        # Recursively invert subtrees
        self.invertTree(root.left)
        self.invertTree(root.right)

        return root

Key Insight: Classic recursion problem. Each node performs the same operation: swap children and recurse.

Pattern 2: Merge Two Binary Trees

Problem: Merge two binary trees by summing overlapping nodes.

Approach: Recursively merge trees. If both nodes exist, sum values. Otherwise, use the existing node.

Time: O(min(n, m)) | Space: O(h)

class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        # If one tree is empty, return the other
        if not root1:
            return root2
        if not root2:
            return root1

        # Both exist: sum values
        root1.val += root2.val

        # Recursively merge subtrees
        root1.left = self.mergeTrees(root1.left, root2.left)
        root1.right = self.mergeTrees(root1.right, root2.right)

        return root1

Key Insight: Handle base cases first (null nodes), then perform operation and recurse.

Pattern 3: Maximum Depth of Binary Tree

Problem: Find the maximum depth (height) of a binary tree.

Approach: Recursively calculate depth of left and right subtrees, return max + 1.

Time: O(n) | Space: O(h)

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        # Get height of subtrees
        l_height = self.maxDepth(root.left)
        r_height = self.maxDepth(root.right)

        # Current height = 1 + max of subtrees
        return 1 + max(l_height, r_height)

Key Insight: Tree height problems naturally fit recursive solutions. Think in terms of subtree properties.

Pattern 4: Minimum Depth (BFS Approach)

Problem: Find the minimum depth (shortest path to a leaf).

Approach: Use BFS to find the first leaf node encountered.

Why BFS? BFS finishes early when finding the first leaf, while DFS must explore all paths.

Time: O(n) | Space: O(w)

from collections import deque

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        # Queue stores (node, depth) pairs
        q = deque([(root, 1)])

        while q:
            node, depth = q.popleft()

            # Found leaf node - return immediately
            if not node.left and not node.right:
                return depth

            # Add children with incremented depth
            if node.left:
                q.append((node.left, depth + 1))
            if node.right:
                q.append((node.right, depth + 1))

Key Insight: Choose BFS for "minimum/shortest" problems where early termination is beneficial.

Pattern 5: Same Tree (BFS)

Problem: Check if two binary trees are structurally identical with same values.

Approach: Use BFS to compare nodes level by level.

Time: O(n) | Space: O(w)

from collections import deque

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        # Both empty = same
        if not p and not q:
            return True

        # Queue stores pairs of nodes to compare
        dq = deque([(p, q)])

        while dq:
            p_node, q_node = dq.popleft()

            # Both null = continue
            if not p_node and not q_node:
                continue

            # One null or values differ = not same
            if not p_node or not q_node or p_node.val != q_node.val:
                return False

            # Add children pairs
            dq.append((p_node.left, q_node.left))
            dq.append((p_node.right, q_node.right))

        return True

Key Insight: Process pairs of nodes simultaneously using a queue.

Pattern 6: Symmetric Tree (DFS & BFS)

Problem: Check if a binary tree is a mirror of itself (symmetric around center).

Approach: Compare left and right subtrees as mirror images.

DFS Solution:

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True

        def dfs(left, right):
            # Both null = symmetric
            if not left and not right:
                return True
            # One null = not symmetric
            if not left or not right:
                return False

            # Check: values equal AND subtrees mirror each other
            return (left.val == right.val and
                    dfs(left.left, right.right) and  # Outside pair
                    dfs(left.right, right.left))     # Inside pair

        return dfs(root.left, root.right)

BFS Solution:

from collections import deque

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True

        q = deque([(root.left, root.right)])

        while q:
            left, right = q.popleft()

            if not left and not right:
                continue
            if not left or not right or left.val != right.val:
                return False

            # Mirror pairs: outside and inside
            q.append((left.left, right.right))
            q.append((left.right, right.left))

        return True

Key Insight: Symmetry requires comparing mirror positions: left.left ↔ right.right, left.right ↔ right.left.

Pattern 7: Balanced Binary Tree

Problem: Check if a binary tree is height-balanced (left and right subtree heights differ by at most 1 for every node).

Approach: Calculate heights while checking balance condition. Use flag to short-circuit.

Time: O(n) | Space: O(h)

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True

        # Flag to track balance status
        res = [True]

        def dfs(r):
            if not r:
                return 0

            # Get left height
            l_height = dfs(r.left)

            # Short-circuit if already unbalanced
            if not res[0]:
                return 0

            # Get right height
            r_height = dfs(r.right)

            # Check balance condition
            if abs(l_height - r_height) > 1:
                res[0] = False
                return 0

            return 1 + max(l_height, r_height)

        dfs(root)
        return res[0]

Key Insight: Use mutable container (list) to maintain state across recursive calls.

Pattern 8: Binary Tree Paths

Problem: Return all root-to-leaf paths.

Approach: DFS with path tracking. Backtrack after exploring each path.

DFS Solution:

class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        res = []

        def dfs(root, path):
            if not root:
                return

            # Add current node to path
            path.append(str(root.val))

            # Leaf node: save path
            if not root.left and not root.right:
                res.append("->".join(path))
            else:
                # Explore children
                dfs(root.left, path)
                dfs(root.right, path)

            # Backtrack: remove current node
            path.pop()

        dfs(root, [])
        return res

BFS Solution:

from collections import deque

class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        res = []
        q = deque([(root, str(root.val))])

        while q:
            node, path = q.popleft()

            # Leaf node: save path
            if not node.left and not node.right:
                res.append(path)

            # Add children with updated paths
            if node.left:
                q.append((node.left, path + "->" + str(node.left.val)))
            if node.right:
                q.append((node.right, path + "->" + str(node.right.val)))

        return res

Key Insight: DFS with backtracking vs BFS with path strings—both valid, choose based on space/time tradeoffs.

Pattern 9: Diameter of Binary Tree

Problem: Find the length of the longest path between any two nodes (path may not pass through root).

Approach: At each node, calculate diameter passing through that node (left_height + right_height). Track maximum.

Time: O(n) | Space: O(h)

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        longest_diameter = [0]

        def dfs(root):
            if not root:
                return 0

            # Get subtree heights
            l_height = dfs(root.left)
            r_height = dfs(root.right)

            # Diameter through this node
            diameter = l_height + r_height
            longest_diameter[0] = max(longest_diameter[0], diameter)

            # Return height for parent
            return 1 + max(l_height, r_height)

        dfs(root)
        return longest_diameter[0]

Key Insight: Diameter at a node = sum of left and right subtree heights. Return height, track diameter separately.

Pattern 10: Path Sum

Problem: Check if the tree has a root-to-leaf path that sums to targetSum.

Approach: Subtract current value from target, recurse. Leaf node should have target = 0.

Time: O(n) | Space: O(h)

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False

        # Leaf node: check if target reached
        if not root.left and not root.right:
            return targetSum - root.val == 0

        # Subtract current value and recurse
        targetSum -= root.val
        return (self.hasPathSum(root.left, targetSum) or 
                self.hasPathSum(root.right, targetSum))

Key Insight: Pass remaining sum down the tree. Leaf nodes check for exact match.

Pattern 11: Path Sum II (All Paths)

Problem: Find all root-to-leaf paths that sum to targetSum.

Approach: DFS with path tracking and backtracking.

Time: O(n) | Space: O(h)

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        if not root:
            return []

        res = []

        def dfs(root, path):
            if not root:
                return

            path.append(root.val)

            # Leaf node: check sum
            if not root.left and not root.right and sum(path) == targetSum:
                res.append(path[:])  # Copy path
            else:
                dfs(root.left, path)
                dfs(root.right, path)

            # Backtrack
            path.pop()

        dfs(root, [])
        return res

Key Insight: Use path[:] to create a copy when saving results. Backtracking reuses the same list.

Pattern 12: Count Good Nodes

Problem: Count nodes that are greater than or equal to all nodes in the path from root.

Approach: Track maximum value seen so far in the path. Increment count if current >= max.

Time: O(n) | Space: O(h)

class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        def dfs(root, max_so_far):
            if not root:
                return 0

            # Check if current node is "good"
            good = 1 if root.val >= max_so_far else 0

            # Update max for children
            max_so_far = max(root.val, max_so_far)

            # Count good nodes in subtrees
            left = dfs(root.left, max_so_far)
            right = dfs(root.right, max_so_far)

            return good + left + right

        return dfs(root, root.val)

Key Insight: Pass down state (max value) and accumulate results (count) upward.

Binary Search Tree (BST) Patterns

BST Properties

Definition: For every node:

All nodes in left subtree < node value
All nodes in right subtree > node value

Key Property: Inorder traversal of BST produces sorted sequence

Time Complexity (Balanced): O(log n) for search, insert, delete

Pattern 13: Validate BST

Problem: Check if a binary tree is a valid BST.

Approach: Track valid range (min, max) for each node. Left child must be in (min, node.val), right child in (node.val, max).

Time: O(n) | Space: O(h)

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def isValid(root, minn, maxx):
            if not root:
                return True

            # Check range violation
            if root.val <= minn or root.val >= maxx:
                return False

            # Left: (minn, root.val), Right: (root.val, maxx)
            return (isValid(root.left, minn, root.val) and
                    isValid(root.right, root.val, maxx))

        return isValid(root, float('-inf'), float('inf'))

Key Insight: Use range bounds, not just parent value. A node must satisfy constraints from all ancestors.

Pattern 14: Kth Smallest Element in BST

Problem: Find the kth smallest element in a BST.

Approach: Inorder traversal produces sorted order. Stop at kth element.

Time: O(k) best, O(n) worst | Space: O(h)

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        count = [k]
        res = [0]

        def dfs(root):
            if not root:
                return

            # Inorder: left, node, right
            dfs(root.left)

            # Process current node
            if count[0] == 1:
                res[0] = root.val
            count[0] -= 1

            # Only continue if not found yet
            if count[0] > 0:
                dfs(root.right)

        dfs(root)
        return res[0]

Key Insight: Inorder traversal of BST visits nodes in sorted order. Count down to find kth.

Pattern 15: Lowest Common Ancestor in BST

Problem: Find the lowest common ancestor of two nodes in a BST.

Approach: Use BST property to navigate. If both nodes < current, go left. If both > current, go right. Otherwise, current is LCA.

Time: O(h) | Space: O(h)

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        lca = [root]

        def dfs(root):
            if not root:
                return

            lca[0] = root

            # Found one of the nodes
            if root == p or root == q:
                return

            # Both in left subtree
            if root.val > p.val and root.val > q.val:
                dfs(root.left)
            # Both in right subtree
            elif root.val < p.val and root.val < q.val:
                dfs(root.right)
            # Split: current node is LCA
            else:
                return

        dfs(root)
        return lca[0]

Key Insight: LCA is the first node where paths to p and q diverge. Use BST property for efficient navigation.

Pattern 16: Subtree of Another Tree

Problem: Check if subRoot is a subtree of root.

Approach: For each node in root, check if subtree matches subRoot.

Time: O(n × m) | Space: O(h)

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        def isSameTree(s, t):
            if not s and not t:
                return True
            if not s or not t or s.val != t.val:
                return False
            return isSameTree(s.left, t.left) and isSameTree(s.right, t.right)

        if not subRoot:
            return True
        if not root:
            return False

        # Check current node or recurse
        if isSameTree(root, subRoot):
            return True

        return (self.isSubtree(root.left, subRoot) or 
                self.isSubtree(root.right, subRoot))

Key Insight: Combine two patterns: tree comparison and tree traversal.

Common Tree Techniques & Patterns

1. Recursion Pattern

Base case: null node
Recursive case: process node, recurse on children
Return: aggregated result from subtrees

2. DFS with State

Pass down: max/min values, path, depth
Accumulate up: count, sum, height
Use mutable containers for flags

3. BFS Level Order

Use queue with (node, metadata)
Process entire level before next
Great for "minimum" problems

4. Backtracking

Add to path → Explore → Remove from path
Essential for path enumeration
Use path[:] for copying

5. BST Navigation

Use BST property for directed search
O(log n) for balanced trees
Inorder traversal = sorted order

Time & Space Complexity Summary

Operation	Time	Space
DFS Traversal	O(n)	O(h) recursion stack
BFS Traversal	O(n)	O(w) queue size
Height Calculation	O(n)	O(h)
Path Finding	O(n)	O(h)
BST Search (balanced)	O(log n)	O(h)
BST Search (worst)	O(n)	O(n)

Note:

h = height (best: log n, worst: n)
w = width (worst: n/2 for perfect tree)
n = number of nodes

Practice Strategy

Foundation (Easy)

Invert Binary Tree
Max Depth
Same Tree
Merge Trees
Path Sum

Core Patterns (Easy-Medium)

Symmetric Tree
Min Depth
Balanced Tree
Binary Tree Paths
Diameter

Advanced (Medium)

Path Sum II
Lowest Common Ancestor
Validate BST
Kth Smallest in BST
Count Good Nodes
Subtree

Tips

Draw trees: Visualize recursion flow
Master base cases: null nodes, leaf nodes
Choose traversal wisely: DFS for paths, BFS for levels
BST advantage: Use ordering property
Practice both: Iterative and recursive solutions

Key Takeaways

Trees are recursive - Each subtree is itself a tree
Master DFS & BFS - Choose based on problem requirements
Inorder BST = Sorted - Powerful property for BST problems
Pass state down, aggregate up - Common recursion pattern
Backtracking for paths - Add, explore, remove
Height vs Depth - Height measured from bottom, depth from top
Space complexity - O(h) for DFS, O(w) for BFS

Binary trees are fundamental to computer science, appearing in databases (B-trees), compilers (syntax trees), file systems, and countless algorithms. Mastering tree traversal and recursion opens doors to solving complex hierarchical problems efficiently.

Continue building your DSA foundation. Trees connect many concepts: recursion, graphs, dynamic programming. Practice regularly and patterns will become intuitive.

Why 0.1 + 0.2 != 0.3: Building a Precise Calculator with Go's Decimal Package

jayk0001 — Wed, 12 Nov 2025 05:43:02 +0000

If you've spent any time programming, you've likely encountered this mind-bending phenomenon:

0.1 + 0.2 === 0.3  // false (!?)
0.1 + 0.2          // 0.30000000000000004

Wait... what? How can basic arithmetic be wrong? This isn't a bug—it's a fundamental limitation of how computers represent decimal numbers. After stumbling upon this issue in a financial calculation project, I decided to dive deep and build a solution: a precise arithmetic calculator in Go using the decimal package.

Project Repository: go-decimal on GitHub

The Problem: Floating-Point Representation

Why Computers Struggle with 0.1

Computers operate in binary (base-2), not decimal (base-10). While integers have exact binary representations, many decimal fractions do not translate cleanly to binary.

Analogy: Just as 1/3 in decimal is a repeating decimal (0.333...), 0.1 in binary is a repeating binary fraction:

0.1 (decimal) = 0.0001100110011001100110011... (binary, repeating)

Since computers have finite memory, they can't store infinite repeating fractions. Instead, they store the closest possible approximation within the allocated bits (typically 32 or 64 bits for floating-point numbers).

The Accumulation of Tiny Errors

When you perform arithmetic operations like 0.1 + 0.2, the computer is actually adding two slightly inaccurate binary approximations:

  0.1 (stored) ≈ 0.1000000000000000055511151231257827...
+ 0.2 (stored) ≈ 0.2000000000000000111022302462515654...
= 0.3000000000000000444089209850062616... ≠ 0.3

These tiny inaccuracies compound, leading to results that are very close to, but not exactly equal to, the expected value.

Real-World Implications

1. Financial Calculations:
Imagine calculating interest on a bank account:

balance := 100.10
interest := 0.20
newBalance := balance + interest  // 100.30000000000001 (?!)

In financial systems, even a fraction of a cent matters. Errors accumulate over millions of transactions.

2. Equality Comparisons:

a := 0.1 + 0.2
b := 0.3
if a == b {  // This will be false!
    fmt.Println("Equal")
}

Direct equality comparison of floats is unreliable. Instead, use epsilon tolerance:

epsilon := 0.00001
if math.Abs(a - b) < epsilon {
    fmt.Println("Approximately equal")
}

3. Scientific Computing:
Long-running simulations can accumulate errors, leading to significant deviations from expected results.

The Solution: Go's Decimal Package

To tackle this problem, I built a simple but precise arithmetic calculator using the shopspring/decimal package for Go. This package provides arbitrary-precision fixed-point decimal numbers, eliminating floating-point errors.

Project Overview

What it does:

Accepts two decimal numbers from user input
Performs basic arithmetic operations (+, -, *, /)
Returns exactly precise results (no floating-point errors)

Key Features:

Handles any decimal numbers (not limited to float64)
Uses arbitrary-precision arithmetic
Simple CLI interface

How It Works

Step 1: Read User Input

reader := bufio.NewReader(os.Stdin)

fmt.Print("Enter the first number: ")
input1, _ := reader.ReadString('\n')
input1 = strings.TrimSpace(input1)

Create a reader for standard input and read until a newline character is encountered.

Step 2: Convert String to Decimal

num1, err := decimal.NewFromString(input1)
if err != nil {
    fmt.Println("Invalid number:", err)
    return
}

The decimal.NewFromString() method parses the user's string input and creates a precise decimal representation. This is the magic that avoids floating-point approximations.

Step 3: Get Second Number

fmt.Print("Enter the second number: ")
input2, _ := reader.ReadString('\n')
input2 = strings.TrimSpace(input2)

num2, err := decimal.NewFromString(input2)
if err != nil {
    fmt.Println("Invalid number:", err)
    return
}

Repeat the process for the second number.

Step 4: Perform Operation

fmt.Print("Enter the operation (+, -, *, /): ")
operation, _ := reader.ReadString('\n')
operation = strings.TrimSpace(operation)

var result decimal.Decimal

switch operation {
case "+":
    result = num1.Add(num2)
case "-":
    result = num1.Sub(num2)
case "*":
    result = num1.Mul(num2)
case "/":
    if num2.IsZero() {
        fmt.Println("Error: Division by zero")
        return
    }
    result = num1.Div(num2)
default:
    fmt.Println("Invalid operation")
    return
}

fmt.Println("RESULT:", result)

Use the built-in arithmetic methods (Add, Sub, Mul, Div) provided by the decimal type. These methods perform exact decimal arithmetic.

Example Usage

$ go run main.go

Enter the first number: 0.1
Enter the second number: 0.2
Enter the operation (+, -, *, /): +
RESULT: 0.3  ✅ Exactly 0.3, not 0.30000000000000004!

More Examples:

# Multiplication with precision
Enter the first number: 0.1
Enter the second number: 0.3
Enter the operation (+, -, *, /): *
RESULT: 0.03

# Division with precision
Enter the first number: 1
Enter the second number: 3
Enter the operation (+, -, *, /): /
RESULT: 0.3333333333333333333333333333  # Configurable precision

How to Run the Project

Installation:

git clone https://github.com/jayk0001/go-decimal.git
cd go-decimal

Run:

go run main.go

The program will prompt you for:

First number
Second number
Operation (+, -, *, /)

Then display the precise result.

Under the Hood: How Decimal Works

The decimal package represents numbers as a combination of:

Coefficient (integer): The significant digits
Exponent (integer): The power of 10

For example:

0.1 = 1 × 10^(-1)
  coefficient = 1
  exponent = -1

This representation avoids binary fractions entirely, storing numbers in a way that naturally aligns with decimal arithmetic—just like we do by hand.

Advantages of Decimal Package

1. Exact Precision:

d1 := decimal.NewFromFloat(0.1)
d2 := decimal.NewFromFloat(0.2)
result := d1.Add(d2)
// result.String() == "0.3" ✅

2. Configurable Precision:

result := decimal.NewFromInt(1).Div(decimal.NewFromInt(3))
fmt.Println(result.StringFixed(2))  // "0.33"
fmt.Println(result.StringFixed(10)) // "0.3333333333"

3. Financial Calculations:

price := decimal.NewFromString("19.99")
taxRate := decimal.NewFromString("0.08")
tax := price.Mul(taxRate).Round(2)  // Rounds to 2 decimal places
total := price.Add(tax)

4. Safe Comparisons:

a := decimal.NewFromFloat(0.1).Add(decimal.NewFromFloat(0.2))
b := decimal.NewFromFloat(0.3)
if a.Equal(b) {  // This works correctly!
    fmt.Println("Equal")
}

Trade-offs

Performance:

decimal is slower than native float64 operations
For most applications (especially financial), accuracy > speed

Memory:

Uses more memory than fixed-size floats
Acceptable trade-off for precision-critical applications

When to Use:

✅ Financial calculations (money, interest, taxes)
✅ Precise decimal arithmetic requirements
✅ Comparisons requiring exactness
❌ Heavy scientific computing (where approximation is acceptable)
❌ Graphics/game programming (speed is critical)

Key Learnings

1. Floating-Point Arithmetic is Approximate

Floats are designed for speed and range, not precision. Understanding this limitation prevents bugs in critical applications.

2. Choose the Right Tool

float64: General-purpose calculations, scientific computing
decimal: Financial, accounting, precise decimal arithmetic
big.Float: Arbitrary precision with floating-point semantics
big.Rat: Exact rational number arithmetic

3. IEEE 754 Standard

The floating-point behavior is standardized (IEEE 754). This means:

The "bug" exists in all languages (JavaScript, Python, Java, C++, Go, etc.)
It's not a flaw—it's a trade-off for efficiency
Understanding it makes you a better programmer

4. Testing Floating-Point Code

Never use == for float comparisons in tests:

// ❌ Bad
if result == 0.3 {
    t.Error("Test failed")
}

// ✅ Good (for floats)
epsilon := 0.00001
if math.Abs(result - 0.3) > epsilon {
    t.Error("Test failed")
}

// ✅ Best (for decimal)
expected := decimal.NewFromFloat(0.3)
if !result.Equal(expected) {
    t.Error("Test failed")
}

Practical Applications

1. E-commerce Pricing

type Product struct {
    Name  string
    Price decimal.Decimal
}

func CalculateTotal(items []Product, taxRate decimal.Decimal) decimal.Decimal {
    subtotal := decimal.Zero
    for _, item := range items {
        subtotal = subtotal.Add(item.Price)
    }
    tax := subtotal.Mul(taxRate).Round(2)
    return subtotal.Add(tax)
}

2. Currency Conversion

func ConvertCurrency(amount decimal.Decimal, exchangeRate decimal.Decimal) decimal.Decimal {
    return amount.Mul(exchangeRate).Round(2)
}

// Example
usd := decimal.NewFromString("100.00")
rate := decimal.NewFromString("1.18")  // USD to EUR
eur := ConvertCurrency(usd, rate)
fmt.Println(eur)  // Exactly 118.00

3. Interest Calculations

func CalculateCompoundInterest(principal, rate decimal.Decimal, years int) decimal.Decimal {
    one := decimal.NewFromInt(1)
    multiplier := one.Add(rate)

    result := principal
    for i := 0; i < years; i++ {
        result = result.Mul(multiplier)
    }
    return result.Round(2)
}

Beyond Go: Solutions in Other Languages

Python:

from decimal import Decimal

a = Decimal('0.1')
b = Decimal('0.2')
result = a + b  # Decimal('0.3')

JavaScript:

// Use libraries like decimal.js or big.js
const Decimal = require('decimal.js');
const a = new Decimal(0.1);
const b = new Decimal(0.2);
const result = a.plus(b);  // 0.3

Java:

import java.math.BigDecimal;

BigDecimal a = new BigDecimal("0.1");
BigDecimal b = new BigDecimal("0.2");
BigDecimal result = a.add(b);  // 0.3

Conclusion

The 0.1 + 0.2 != 0.3 phenomenon isn't a programming bug—it's a fundamental limitation of binary floating-point representation. While this quirk can cause headaches, understanding why it happens and knowing the tools to address it makes you a more effective engineer.

Building this simple calculator taught me:

The importance of choosing the right data type for the job
How computers represent numbers at a fundamental level
Why financial applications require special handling
The value of hands-on experimentation in understanding CS concepts

For applications where precision matters (finance, accounting, scientific measurements), always reach for decimal arithmetic libraries. Your users—and your QA team—will thank you.

Resources:

Have you encountered floating-point precision issues in your projects? How did you solve them? Let's discuss!

DSA Fundamentals: Binary Search - From Theory to LeetCode Practice

jayk0001 — Thu, 06 Nov 2025 22:55:42 +0000

DSA Fundamentals: Binary Search - From Theory to LeetCode Practice

Binary Search is one of the most efficient searching algorithms, achieving O(log n) time complexity by repeatedly dividing the search space in half. Understanding binary search is essential for optimizing search operations and solving a wide variety of algorithmic problems beyond simple array searching.

This comprehensive guide combines theoretical understanding with practical problem-solving, featuring solutions to essential LeetCode problems that demonstrate core binary search patterns.

Understanding Binary Search

Binary Search Fundamentals

Binary Search is an efficient algorithm for finding a target value within a sorted array. It works by repeatedly dividing the search interval in half, eliminating half of the remaining elements in each iteration.

Core Principle: Divide and Conquer

Instead of checking every element linearly (O(n)), binary search leverages the sorted property to make intelligent decisions:

Start with the entire array
Check the middle element
If target equals middle, found!
If target is less than middle, search left half
If target is greater than middle, search right half
Repeat until found or search space is empty

Why Binary Search is Fast

Comparison with Linear Search:

Array Size	Linear Search	Binary Search	Improvement
10	10 comparisons	4 comparisons	2.5× faster
100	100 comparisons	7 comparisons	14× faster
1,000	1,000 comparisons	10 comparisons	100× faster
1,000,000	1,000,000 comparisons	20 comparisons	50,000× faster

Mathematical Proof:

Each iteration cuts search space in half
After k iterations: n / 2^k elements remain
When 1 element left: n / 2^k = 1 → k = log₂(n)
Time Complexity: O(log n)

Prerequisites for Binary Search

Required:

Sorted data structure (or conceptually sorted search space)
Random access to elements (array, not linked list)
Clear comparison criteria (way to determine which half to search)

Binary Search Implementation Patterns

Pattern 1: Traditional Binary Search

Use case: Finding exact match in sorted array

Template:

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        # Calculate middle (prevents integer overflow)
        mid = left + (right - left) // 2

        if arr[mid] == target:
            return mid  # Found target
        elif arr[mid] < target:
            left = mid + 1  # Search right half
        else:
            right = mid - 1  # Search left half

    return -1  # Target not found

Key Points:

Middle calculation: left + (right - left) // 2 prevents integer overflow
- Alternative: (left + right) // 2 works in Python but can overflow in other languages
Loop condition: left <= right (inclusive)
Pointer update: mid + 1 or mid - 1 (exclude mid from next search)

Pattern 2: Conditional Binary Search

Use case: Finding minimum/maximum value satisfying a condition

Template:

def conditional_binary_search(arr):
    left = 0
    right = len(arr) - 1
    result = -1  # Track best answer found

    while left <= right:
        mid = left + (right - left) // 2

        if condition_satisfied(arr[mid]):
            result = arr[mid]  # Update result
            # Continue searching for better answer
            # (left or right depending on problem)
            right = mid - 1  # or left = mid + 1
        else:
            left = mid + 1  # or right = mid - 1

    return result

Key Points:

Track best answer found so far
Continue searching even after finding valid answer
Used for optimization problems (min/max)

Time and Space Complexity

Operation	Time Complexity	Space Complexity	Notes
Binary Search (iterative)	O(log n)	O(1)	Most common
Binary Search (recursive)	O(log n)	O(log n)	Recursion stack
Search in 2D matrix	O(log(m×n))	O(1)	Treat as 1D array
Rotated array search	O(log n)	O(1)	Modified binary search

Essential LeetCode Problems & Solutions

1. Binary Search (LeetCode 704)

Problem: Given a sorted array and target value, return the index of target if found, otherwise return -1.

Example:

Input: nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4 (nums[4] = 9)

Input: nums = [-1, 0, 3, 5, 9, 12], target = 2
Output: -1 (not found)

Approach: Classic binary search implementation. Compare middle element with target and eliminate half of search space each iteration.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1

        while left <= right:
            # Calculate middle index (prevents overflow)
            mid = left + (right - left) // 2

            # Found target
            if nums[mid] == target:
                return mid

            # Target in right half
            if nums[mid] < target:
                left = mid + 1
            # Target in left half
            else:
                right = mid - 1

        # Target not found
        return -1

Time Complexity: O(log n) - Halve search space each iteration

Space Complexity: O(1) - Only using pointers

Key Concepts:

Sorted array requirement: Essential for binary search
Middle calculation: left + (right - left) // 2 prevents overflow
Search space reduction: Eliminate half each iteration
Loop invariant: Target must be in [left, right] if it exists

Visualization:

nums = [-1, 0, 3, 5, 9, 12], target = 9

Iteration 1: left=0, right=5, mid=2
  [-1, 0, 3, 5, 9, 12]
         ^
  nums[2]=3 < 9 → search right half

Iteration 2: left=3, right=5, mid=4
  [-1, 0, 3, 5, 9, 12]
               ^
  nums[4]=9 == 9 → Found! Return 4

2. Find Minimum in Rotated Sorted Array (LeetCode 153)

Problem: A sorted array has been rotated at an unknown pivot. Find the minimum element.

Example:

Input: nums = [3, 4, 5, 1, 2]
Output: 1

Input: nums = [4, 5, 6, 7, 0, 1, 2]
Output: 0

Input: nums = [11, 13, 15, 17]
Output: 11 (no rotation)

Approach: Use binary search with custom logic. The minimum is where the rotation occurred. Compare middle with right to determine which half contains the minimum.

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left = 0
        right = len(nums) - 1
        min_val = float('inf')

        while left <= right:
            mid = left + (right - left) // 2

            # If mid > right, rotation point is in right half
            if nums[mid] > nums[right]:
                left = mid + 1
            else:
                # Mid could be minimum, update and search left
                min_val = min(min_val, nums[mid])
                right = mid - 1

        return min_val

Time Complexity: O(log n) - Binary search on rotated array

Space Complexity: O(1) - Only tracking minimum value

Key Concepts:

Rotation detection: Compare nums[mid] with nums[right]
Two sorted subarrays: Rotation creates two sorted segments
Minimum location: At the rotation point (smallest element)
Decision logic:
- If nums[mid] > nums[right]: minimum in right half (array rotated)
- Otherwise: minimum in left half or at mid

Visualization:

nums = [4, 5, 6, 7, 0, 1, 2]
        sorted →    ↑ rotation point (minimum)

Iteration 1: left=0, right=6, mid=3
  [4, 5, 6, 7, 0, 1, 2]
           ^        ^
  nums[3]=7 > nums[6]=2 → minimum in right half

Iteration 2: left=4, right=6, mid=5
  [4, 5, 6, 7, 0, 1, 2]
                 ^  ^
  nums[5]=1 < nums[6]=2 → update min=1, search left

Result: min_val = 0

Alternative Approach (Cleaner):

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left = 0
        right = len(nums) - 1

        while left < right:
            mid = left + (right - left) // 2

            if nums[mid] > nums[right]:
                left = mid + 1  # Minimum in right half
            else:
                right = mid  # Mid could be minimum

        return nums[left]  # Left points to minimum

3. Search in Rotated Sorted Array (LeetCode 33)

Problem: Search for a target value in a rotated sorted array. Return its index or -1 if not found.

Example:

Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Output: 4

Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 3
Output: -1

Approach: Modified binary search. Determine which half is sorted, then check if target is in that sorted half.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1

        while left <= right:
            mid = left + (right - left) // 2

            # Found target
            if nums[mid] == target:
                return mid

            # Determine which half is sorted
            if nums[left] <= nums[mid]:
                # Left half is sorted
                if nums[left] <= target <= nums[mid]:
                    # Target in sorted left half
                    right = mid - 1
                else:
                    # Target in right half
                    left = mid + 1
            else:
                # Right half is sorted
                if nums[mid] <= target <= nums[right]:
                    # Target in sorted right half
                    left = mid + 1
                else:
                    # Target in left half
                    right = mid - 1

        return -1

Time Complexity: O(log n) - Modified binary search

Space Complexity: O(1) - Only using pointers

Key Concepts:

Identify sorted half: At least one half is always sorted
Range check: If target in sorted half's range, search it
Two cases: Left sorted vs right sorted
Decision tree:
1. Find which half is sorted (compare nums[left] with nums[mid])
2. Check if target is in sorted half's range
3. Search appropriate half

Visualization:

nums = [4, 5, 6, 7, 0, 1, 2], target = 0

Iteration 1: left=0, right=6, mid=3
  [4, 5, 6, 7, 0, 1, 2]
   L        M        R
  nums[0]=4 <= nums[3]=7 → left half sorted
  4 <= 0 <= 7? NO → search right half

Iteration 2: left=4, right=6, mid=5
  [4, 5, 6, 7, 0, 1, 2]
               L  M  R
  nums[4]=0 <= nums[5]=1 → left half sorted? NO
  → right half sorted
  0 <= 0 <= 2? YES → search right half

Iteration 3: left=4, right=4, mid=4
  [4, 5, 6, 7, 0, 1, 2]
               ^
  nums[4]=0 == 0 → Found! Return 4

4. Search a 2D Matrix (LeetCode 74)

Problem: Search for a target value in an m×n matrix with properties:

Integers in each row are sorted left to right
First integer of each row is greater than last integer of previous row

Example:

Input: matrix = [[1, 3, 5, 7],
                 [10, 11, 16, 20],
                 [23, 30, 34, 60]], target = 3
Output: true

Input: matrix = [[1, 3, 5, 7],
                 [10, 11, 16, 20],
                 [23, 30, 34, 60]], target = 13
Output: false

Approach: Treat 2D matrix as flattened 1D sorted array. Convert 1D index to 2D coordinates using division and modulo.

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        rows = len(matrix)
        cols = len(matrix[0])

        # Binary search on flattened array
        left = 0
        right = (rows * cols) - 1

        while left <= right:
            mid = left + (right - left) // 2

            # Convert 1D index to 2D coordinates
            row = mid // cols
            col = mid % cols
            mid_value = matrix[row][col]

            if mid_value == target:
                return True
            elif mid_value < target:
                left = mid + 1
            else:
                right = mid - 1

        return False

Time Complexity: O(log(m × n)) - Binary search on total elements

Space Complexity: O(1) - Only using pointers

Key Concepts:

1D to 2D conversion:
- row = index // cols (which row)
- col = index % cols (position in row)
Flattened view: Matrix is conceptually a sorted 1D array
Index mapping: Binary search on virtual 1D array

Visualization:

Matrix (2D):          Flattened (1D):
[ 1,  3,  5,  7]      [1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60]
[10, 11, 16, 20]       0  1  2  3   4   5   6   7   8   9  10  11
[23, 30, 34, 60]

For index 5 (value 11):
  row = 5 // 4 = 1
  col = 5 % 4 = 1
  matrix[1][1] = 11 ✓

Binary search target=3:
  left=0, right=11, mid=5
  matrix[5//4][5%4] = matrix[1][1] = 11 > 3
  → search left half

  left=0, right=4, mid=2
  matrix[2//4][2%4] = matrix[0][2] = 5 > 3
  → search left half

  left=0, right=1, mid=0
  matrix[0//4][0%4] = matrix[0][0] = 1 < 3
  → search right half

  left=1, right=1, mid=1
  matrix[1//4][1%4] = matrix[0][1] = 3 == 3
  → Found!

5. Koko Eating Bananas (LeetCode 875)

Problem: Koko loves bananas. There are n piles with different amounts. She can eat at most k bananas per hour. Find the minimum k such that she can eat all bananas within h hours.

Example:

Input: piles = [3, 6, 7, 11], h = 8
Output: 4

Explanation:
- k=4: 1 + 2 + 2 + 3 = 8 hours ✓
- k=3: 1 + 2 + 3 + 4 = 10 hours ✗ (too slow)

Approach: Binary search on eating speed. Search space is [1, max(piles)]. For each speed, calculate if Koko can finish in h hours.

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        # Search space: minimum speed 1, maximum speed max(piles)
        left = 1
        right = max(piles)
        result = right

        while left <= right:
            k = (left + right) // 2

            # Calculate total hours needed at speed k
            total_hours = sum(math.ceil(pile / k) for pile in piles)

            # Can finish in time?
            if total_hours <= h:
                # This speed works, try slower (minimize k)
                result = min(k, result)
                right = k - 1
            else:
                # Too slow, need faster speed
                left = k + 1

        return result

Time Complexity: O(n × log m) where n = number of piles, m = max(piles)

Space Complexity: O(1) - Only tracking result and pointers

Key Concepts:

Non-traditional search space: Searching for speed, not array index
Condition check: Can Koko finish with speed k?
Minimization: Find minimum k that satisfies condition
Ceiling division: math.ceil(pile / k) for partial hours
Binary search on answer: Search the solution space directly

Why Binary Search Works:

Monotonic property: If speed k works, all speeds > k also work
Search space: [1, max(piles)] - clear boundaries
Condition: Can finish in h hours (yes/no)

Detailed Example:

piles = [3, 6, 7, 11], h = 8

Search space: [1, 11]

Iteration 1: k=6
  Hours: ceil(3/6) + ceil(6/6) + ceil(7/6) + ceil(11/6)
       = 1 + 1 + 2 + 2 = 6 ≤ 8 ✓
  Update result=6, try slower: right=5

Iteration 2: k=3
  Hours: ceil(3/3) + ceil(6/3) + ceil(7/3) + ceil(11/3)
       = 1 + 2 + 3 + 4 = 10 > 8 ✗
  Too slow, need faster: left=4

Iteration 3: k=4
  Hours: ceil(3/4) + ceil(6/4) + ceil(7/4) + ceil(11/4)
       = 1 + 2 + 2 + 3 = 8 ≤ 8 ✓
  Update result=4, try slower: right=3

Iteration 4: left=4, right=3 → left > right, stop
Result: 4

6. Time Based Key-Value Store (LeetCode 981)

Problem: Design a time-based key-value store that:

Stores multiple values for same key at different timestamps
Retrieves value at given timestamp (or closest previous timestamp)

Operations:

set(key, value, timestamp): Store value at timestamp
get(key, timestamp): Get value at or before timestamp

Example:

["TimeMap", "set", "get", "get", "set", "get", "get"]
[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]

Output: [null, null, "bar", "bar", null, "bar2", "bar2"]

Explanation:
- set("foo", "bar", 1)
- get("foo", 1) → "bar" (exact match)
- get("foo", 3) → "bar" (timestamp 1 is closest ≤ 3)
- set("foo", "bar2", 4)
- get("foo", 4) → "bar2" (exact match)
- get("foo", 5) → "bar2" (timestamp 4 is closest ≤ 5)

Approach: Use hash map where each key stores list of [value, timestamp] pairs. Timestamps are strictly increasing (per problem), so use binary search to find value at or before given timestamp.

class TimeMap:
    def __init__(self):
        # key -> list of [value, timestamp] pairs
        self.store = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        # Initialize list if key doesn't exist
        if key not in self.store:
            self.store[key] = []

        # Append [value, timestamp] pair
        self.store[key].append([value, timestamp])

    def get(self, key: str, timestamp: int) -> str:
        result = ""

        # Get all values for this key
        values = self.store.get(key, [])

        # Key doesn't exist
        if not values:
            return result

        # Binary search for largest timestamp <= given timestamp
        left = 0
        right = len(values) - 1

        while left <= right:
            mid = left + (right - left) // 2

            # values[mid] = [value, timestamp]
            if values[mid][1] <= timestamp:
                # This timestamp works, save it and search for later one
                result = values[mid][0]
                left = mid + 1
            else:
                # Timestamp too large, search left
                right = mid - 1

        return result

Time Complexity:

set: O(1) - Append to list
get: O(log n) - Binary search on timestamps list

Space Complexity: O(n) - Store all key-value-timestamp entries

Key Concepts:

Hash map + sorted lists: Each key has chronologically sorted values
Binary search on timestamps: Find largest timestamp ≤ query
Closest previous value: Not exact match required
Monotonic timestamps: Guarantees sorted order in each list

Visualization:

After: set("foo", "bar", 1), set("foo", "bar2", 4), set("foo", "bar3", 7)

store = {
  "foo": [
    ["bar", 1],
    ["bar2", 4],
    ["bar3", 7]
  ]
}

get("foo", 5):
  Binary search for timestamp ≤ 5

  left=0, right=2, mid=1
  values[1][1] = 4 ≤ 5 ✓
  result = "bar2", search right for potentially larger
  left = 2

  left=2, right=2, mid=2
  values[2][1] = 7 > 5 ✗
  Search left
  right = 1

  left=2, right=1 → stop
  result = "bar2"

Core Binary Search Patterns

Pattern 1: Traditional Binary Search (Exact Match)

When to use:

Searching for exact value in sorted array
Need index of target element
Clear match condition

Template:

def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Examples: Binary Search (704), Search Insert Position

Pattern 2: Finding Boundary (First/Last Occurrence)

When to use:

Finding first or last occurrence
Finding insertion point
Range queries

Template:

def find_first_occurrence(arr, target):
    left, right = 0, len(arr) - 1
    result = -1

    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            result = mid
            right = mid - 1  # Continue searching left for first
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return result

Pattern 3: Binary Search on Answer Space

When to use:

Minimizing/maximizing a value
Search space is not an array but a range
Monotonic condition (if x works, x+1 also works or vice versa)

Template:

def binary_search_on_answer(min_val, max_val):
    left, right = min_val, max_val
    result = max_val

    while left <= right:
        mid = left + (right - left) // 2
        if condition_satisfied(mid):
            result = mid
            right = mid - 1  # Try to minimize
        else:
            left = mid + 1
    return result

Examples: Koko Eating Bananas, Capacity To Ship Packages, Split Array Largest Sum

Pattern 4: Rotated/Modified Sorted Array

When to use:

Array is sorted but rotated
Modified sorted properties
Need to identify which part is sorted

Template:

def search_rotated(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid

        # Identify which half is sorted
        if arr[left] <= arr[mid]:  # Left half sorted
            if arr[left] <= target < arr[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:  # Right half sorted
            if arr[mid] < target <= arr[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

Examples: Search in Rotated Sorted Array, Find Minimum in Rotated Sorted Array

Pattern 5: 2D Binary Search

When to use:

2D matrix with sorted properties
Can treat as flattened 1D array
Row-wise or column-wise sorting

Template:

def search_2d_matrix(matrix, target):
    if not matrix:
        return False

    rows, cols = len(matrix), len(matrix[0])
    left, right = 0, rows * cols - 1

    while left <= right:
        mid = left + (right - left) // 2
        row, col = mid // cols, mid % cols

        if matrix[row][col] == target:
            return True
        elif matrix[row][col] < target:
            left = mid + 1
        else:
            right = mid - 1
    return False

Examples: Search a 2D Matrix, Search a 2D Matrix II

Performance Optimization Tips

1. Prevent Integer Overflow

# Potentially unsafe in languages with fixed integer size
mid = (left + right) // 2  # Could overflow if left + right > MAX_INT

# Safe: prevents overflow
mid = left + (right - left) // 2  # Always safe

# Alternative in Python (no overflow issues)
mid = (left + right) // 2  # Fine in Python (arbitrary precision)

Key insight: Python has arbitrary precision integers, but use safe version for language portability.

2. Choose Correct Loop Condition

# Use <= when you need to check left == right case
while left <= right:
    mid = left + (right - left) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        left = mid + 1
    else:
        right = mid - 1

# Use < when mid could be answer (find minimum/boundary)
while left < right:
    mid = left + (right - left) // 2
    if condition(arr[mid]):
        right = mid  # Mid could be answer
    else:
        left = mid + 1

return left  # or right (they're equal)

3. Early Termination for Edge Cases

# Check impossible cases first
def binary_search(arr, target):
    if not arr:
        return -1
    if target < arr[0] or target > arr[-1]:
        return -1  # Target outside array range

    # ... regular binary search

4. Use Built-in Functions When Appropriate

import bisect

# bisect_left: leftmost insertion point
index = bisect.bisect_left(arr, target)

# bisect_right: rightmost insertion point
index = bisect.bisect_right(arr, target)

# But implement manually for interviews!

Common Pitfalls and Solutions

1. Infinite Loop with Wrong Pointer Updates

# Wrong: May cause infinite loop
while left < right:
    mid = (left + right) // 2
    if condition(arr[mid]):
        right = mid  # OK
    else:
        left = mid  # ❌ When left = mid, infinite loop!

# Correct: Always make progress
while left < right:
    mid = (left + right) // 2
    if condition(arr[mid]):
        right = mid
    else:
        left = mid + 1  # ✓ Always moves forward

2. Off-by-One Errors in Boundary Conditions

# Common mistake: wrong initial right boundary
right = len(arr)  # ❌ Out of bounds!
right = len(arr) - 1  # ✓ Correct

# In 2D matrix
right = rows * cols  # ❌ Should be cols - 1
right = (rows * cols) - 1  # ✓ Correct

3. Forgetting to Update Result in Conditional Search

# Wrong: Not saving best answer found
while left <= right:
    mid = left + (right - left) // 2
    if condition(mid):
        right = mid - 1  # ❌ Lost this valid answer!
    else:
        left = mid + 1

# Correct: Save result before continuing
result = -1
while left <= right:
    mid = left + (right - left) // 2
    if condition(mid):
        result = mid  # ✓ Save this answer
        right = mid - 1
    else:
        left = mid + 1
return result

4. Wrong Comparison in Rotated Array

# Wrong: Comparing with wrong boundary
if nums[mid] > nums[left]:  # ❌ Doesn't always identify sorted half

# Correct: Use <= for left comparison
if nums[left] <= nums[mid]:  # ✓ Handles duplicates correctly

5. Incorrect Ceiling Division

# Wrong: Integer division truncates
hours = sum(pile / k for pile in piles)  # Float result

# Correct: Use ceiling division
import math
hours = sum(math.ceil(pile / k) for pile in piles)

# Alternative: Integer arithmetic
hours = sum((pile + k - 1) // k for pile in piles)

Binary Search Time Complexity Analysis

Comparison with Other Search Algorithms

Algorithm	Worst Case	Average Case	Best Case	Space	Prerequisite
Linear Search	O(n)	O(n)	O(1)	O(1)	None
Binary Search	O(log n)	O(log n)	O(1)	O(1)	Sorted array
Jump Search	O(√n)	O(√n)	O(1)	O(1)	Sorted array
Interpolation	O(n)	O(log log n)	O(1)	O(1)	Uniformly distributed

Binary search is optimal for sorted arrays: Can't do better than O(log n) for comparison-based search.

When NOT to Use Binary Search

Unsorted data: Sorting costs O(n log n), not worth it for single search
Linked lists: No O(1) random access (need O(n) to reach middle)
Small arrays: Linear search might be faster due to simplicity
Frequent insertions/deletions: Maintaining sorted order is expensive

Problem Complexity Summary

Problem	Type	Time Complexity	Space Complexity	Key Pattern
Binary Search (704)	Traditional	O(log n)	O(1)	Exact match
Find Min Rotated (153)	Rotated Array	O(log n)	O(1)	Conditional search
Search Rotated (33)	Rotated Array	O(log n)	O(1)	Identify sorted half
Search 2D Matrix (74)	2D Search	O(log(m×n))	O(1)	Flatten to 1D
Koko Bananas (875)	Answer Space	O(n × log m)	O(1)	Binary search on k
TimeMap (981)	Data Structure	O(log n) get	O(n)	Binary search on time

Conclusion

Binary Search is one of the most elegant and efficient algorithms in computer science, achieving O(log n) performance through divide-and-conquer strategy. Key takeaways:

Core Concepts Mastered:

Binary Search Fundamentals:

O(log n) time complexity: Fastest search algorithm for sorted data
Divide and conquer: Eliminate half of search space each iteration
Requirements: Sorted array, random access, clear comparison criteria
Loop invariants: Maintain left <= right and target in search space

Essential Patterns Mastered:

Pattern 1: Traditional binary search (exact match finding)

Pattern 2: Conditional binary search (optimization problems)

Pattern 3: Rotated array search (identify sorted portions)

Pattern 4: 2D binary search (flatten and search)

Pattern 5: Binary search on answer space (non-traditional search spaces)

Problem-Solving Strategies:

Identify sorted property: Essential for binary search
Choose loop condition: <= for exact match, < for boundary finding
Save best answer: In optimization problems, track result before continuing
Calculate middle safely: Use left + (right - left) // 2
Update pointers correctly: mid + 1 or mid - 1 to avoid infinite loops

Key Optimization Principles:

Prevent overflow in middle calculation (though not issue in Python)
Early termination for edge cases (empty array, out of range)
Choose right pattern based on problem type
Store indices when you need to calculate distances
Verify loop termination to avoid infinite loops

When to Use Binary Search:

Searching in sorted array
Finding boundaries (first/last occurrence)
Optimization problems with monotonic property
Search space has ordered property
Need O(log n) performance

Advanced Applications:

Finding peak element in mountain array
Allocating minimum pages/packages
Finding k-th smallest element
Median of two sorted arrays
Square root calculation

Next Steps:

Building on binary search foundations, future topics will cover:

Binary Search Trees (BST operations and traversals)
Advanced Binary Search (finding k-th element, median)
Trie and Prefix Trees (efficient string search)
Graph Search Algorithms (DFS, BFS with optimization)

The problems covered here represent fundamental binary search patterns that appear across technical interviews and competitive programming. Master these patterns, and you'll recognize binary search opportunities in optimization and search problems.

Practice Problems for Mastery:

Basic Binary Search:

704. Binary Search
35. Search Insert Position
374. Guess Number Higher or Lower
278. First Bad Version
69. Sqrt(x)

Finding Boundaries:

34. Find First and Last Position of Element in Sorted Array
744. Find Smallest Letter Greater Than Target
162. Find Peak Element

Rotated Arrays:

33. Search in Rotated Sorted Array
81. Search in Rotated Sorted Array II (with duplicates)
153. Find Minimum in Rotated Sorted Array
154. Find Minimum in Rotated Sorted Array II

2D Search:

74. Search a 2D Matrix
240. Search a 2D Matrix II
378. Kth Smallest Element in a Sorted Matrix

Binary Search on Answer:

875. Koko Eating Bananas
1011. Capacity To Ship Packages Within D Days
410. Split Array Largest Sum
1482. Minimum Number of Days to Make m Bouquets
1283. Find the Smallest Divisor Given a Threshold

Advanced:

4. Median of Two Sorted Arrays
981. Time Based Key-Value Store
1201. Ugly Number III
1268. Search Suggestions System

References:

NeetCode - Algorithms
Binary Search Tutorial - TopCoder
LeetCode Patterns
Introduction to Algorithms by Cormen et al.
Algorithm Design Manual by Steven Skiena

This comprehensive guide provides a solid foundation for mastering binary search algorithm and recognizing binary search patterns in algorithmic problem-solving.

DSA Fundamentals: Stack - From Theory to LeetCode Practice

jayk0001 — Mon, 03 Nov 2025 23:14:21 +0000

DSA Fundamentals: Stack - From Theory to LeetCode Practice

The Stack is one of the most fundamental data structures in computer science, following the Last In, First Out (LIFO) principle. Understanding stacks is essential for solving problems involving balanced expressions, undo operations, function call management, and many other algorithmic challenges.

This comprehensive guide combines theoretical understanding with practical problem-solving, featuring solutions to essential LeetCode problems that demonstrate core stack patterns.

Understanding Stack: LIFO Principle

Stack Fundamentals

Stack is a linear data structure that follows the LIFO (Last In, First Out) principle - the last element added is the first one to be removed. Think of it like a stack of trays at a restaurant: you add new trays on top and remove from the top.

Real-World Analogies

Stack of plates: Add and remove from the top
Browser history: Back button (most recent pages first)
Undo functionality: Reverse most recent actions
Function call stack: Most recent function call executes first

Stack Operations

Core Operations:

Operation	Description	Time Complexity	Python Implementation
`push(x)`	Add element to top	O(1)	`stack.append(x)`
`pop()`	Remove and return top element	O(1)	`stack.pop()`
`peek()` / `top()`	View top element without removing	O(1)	`stack[-1]`
`isEmpty()`	Check if stack is empty	O(1)	`not stack` or `len(stack) == 0`
`size()`	Get number of elements	O(1)	`len(stack)`

Python Stack Implementation

Using List (Array):

# Initialize empty stack
stack = []

# Push operations - O(1)
stack.append(1)
stack.append(2)
stack.append(3)
# Stack: [1, 2, 3] (3 is at top)

# Peek operation - O(1)
top_element = stack[-1]  # Returns 3

# Pop operation - O(1)
removed = stack.pop()  # Returns 3
# Stack: [1, 2]

# Check if empty - O(1)
is_empty = not stack  # Returns False
is_empty = len(stack) == 0  # Returns False

# Size operation - O(1)
size = len(stack)  # Returns 2

Using collections.deque (Recommended for complex scenarios):

from collections import deque

# Initialize
stack = deque()

# Operations (same interface)
stack.append(1)      # Push
top = stack[-1]      # Peek
removed = stack.pop() # Pop

Stack vs Array vs Queue

Feature	Stack (LIFO)	Queue (FIFO)	Array
Access Pattern	Last In, First Out	First In, First Out	Random Access
Primary Operations	push, pop (from end)	enqueue, dequeue (from both ends)	Access by index
Access Time	O(1) for top	O(1) for front/rear	O(1) for any index
Use Cases	Undo, recursion, parsing	Task scheduling, BFS	General storage, random access
Python Implementation	`list` with append/pop	`deque` with append/popleft	`list`

Essential LeetCode Problems & Solutions

Let's explore fundamental stack problems that demonstrate core algorithmic patterns.

1. Valid Parentheses (LeetCode 20)

Problem: Determine if a string containing brackets (), {}, [] is valid. Valid means:

Open brackets must be closed by the same type
Open brackets must be closed in correct order
Every close bracket has corresponding open bracket

Examples:

"()" → True
"()[]{}" → True
"(]" → False
"([)]" → False (wrong order)

Approach: Use stack to track open brackets. When encountering close bracket, check if it matches most recent open bracket.

class Solution:
    def isValid(self, s: str) -> bool:
        # Map closing brackets to their opening counterparts
        bracket_map = {"}": "{", "]": "[", ")": "("}
        stack = []

        for char in s:
            # If it's an opening bracket
            if char not in bracket_map:
                stack.append(char)
            else:
                # It's a closing bracket
                # Check if stack is empty (no matching open bracket)
                if not stack:
                    return False

                # Pop most recent opening bracket
                popped = stack.pop()

                # Check if it matches the closing bracket
                if popped != bracket_map[char]:
                    return False

        # Valid if all brackets matched (stack empty)
        return not stack

Time Complexity: O(n) - Single pass through string

Space Complexity: O(n) - Stack can hold all opening brackets in worst case

Key Concepts:

LIFO nature: Most recent opening bracket should match current closing bracket
Hash map for pairing: Quick lookup of bracket pairs
Empty stack check: Closing bracket without opening bracket
Final stack check: All brackets must be matched (empty stack)

Edge Cases:

Empty string: Valid (return True)
Only opening brackets: Invalid (stack not empty)
Only closing brackets: Invalid (stack empty when checking)
Mismatched types: "([)]" - caught by matching check

2. Min Stack (LeetCode 155)

Problem: Design a stack that supports push, pop, top, and retrieving minimum element in constant time.

Operations Required:

push(val): Push element onto stack
pop(): Remove element from top
top(): Get top element
getMin(): Retrieve minimum element (O(1))

Approach: Use two stacks - one for data, one for tracking minimum values at each level.

class MinStack:
    def __init__(self):
        # Main stack for data
        self.data_stack = []
        # Stack to track minimum at each level
        self.min_stack = []

    def push(self, val: int) -> None:
        # Always push to data stack
        self.data_stack.append(val)

        # Push to min stack
        if not self.min_stack:
            # First element is the minimum
            self.min_stack.append(val)
        else:
            # Current minimum is min of new value and previous minimum
            current_min = self.min_stack[-1]
            self.min_stack.append(min(current_min, val))

    def pop(self) -> None:
        # Pop from both stacks to maintain sync
        self.data_stack.pop()
        self.min_stack.pop()

    def top(self) -> int:
        # Return top of data stack
        return self.data_stack[-1]

    def getMin(self) -> int:
        # Return top of min stack (current minimum)
        return self.min_stack[-1]


# Usage example:
# obj = MinStack()
# obj.push(-2)    # data: [-2],     min: [-2]
# obj.push(0)     # data: [-2, 0],  min: [-2, -2]
# obj.push(-3)    # data: [-2, 0, -3], min: [-2, -2, -3]
# obj.getMin()    # Returns -3
# obj.pop()       # data: [-2, 0],  min: [-2, -2]
# obj.top()       # Returns 0
# obj.getMin()    # Returns -2

Time Complexity: O(1) for all operations

Space Complexity: O(n) - Two stacks, each storing n elements

Key Concepts:

Auxiliary stack pattern: Track additional information alongside main data
Sync maintenance: Both stacks must stay synchronized
Min tracking: Store minimum value at each stack level
Trade-off: Space (extra stack) for time (O(1) min retrieval)

Why Two Stacks?

Without min_stack: Finding minimum requires O(n) scan through data_stack
With min_stack: Minimum always available at top in O(1)
Space cost: O(n) extra space for guaranteed O(1) retrieval

Alternative Approach (Space Optimization):

# Store (value, current_min) tuples in single stack
class MinStack:
    def __init__(self):
        self.stack = []  # Store (value, min_at_this_level)

    def push(self, val: int) -> None:
        if not self.stack:
            self.stack.append((val, val))
        else:
            current_min = self.stack[-1][1]
            self.stack.append((val, min(val, current_min)))

    def pop(self) -> None:
        self.stack.pop()

    def top(self) -> int:
        return self.stack[-1][0]

    def getMin(self) -> int:
        return self.stack[-1][1]

3. Daily Temperatures (LeetCode 739)

Problem: Given array of daily temperatures, return array where answer[i] is the number of days until a warmer temperature. If no warmer day, use 0.

Example:

Input: temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
Output:               [ 1,  1,  4,  2,  1,  1,  0,  0]

Explanation:
- Day 0 (73°): Next warmer is day 1 (74°) → 1 day wait
- Day 1 (74°): Next warmer is day 2 (75°) → 1 day wait
- Day 2 (75°): Next warmer is day 6 (76°) → 4 days wait
- Day 6 (76°): No warmer day → 0

Approach: Use monotonic decreasing stack to track indices of temperatures waiting for warmer day.

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        # Initialize result array with zeros
        result = [0] * len(temperatures)

        # Stack stores indices of temperatures waiting for warmer day
        stack = []

        for i, temp in enumerate(temperatures):
            # While current temp is warmer than temperatures in stack
            while stack and temperatures[stack[-1]] < temp:
                # Pop previous index
                prev_index = stack.pop()
                # Calculate days to wait
                result[prev_index] = i - prev_index

            # Add current index to stack
            stack.append(i)

        return result

Time Complexity: O(n) - Each element pushed and popped at most once

Space Complexity: O(n) - Stack can hold all indices in worst case

Key Concepts:

Monotonic stack: Maintains decreasing temperature order
Index storage: Store indices, not values, to calculate distance
Next greater element pattern: Finding next element that satisfies condition
Efficient lookup: O(1) amortized for finding next warmer day

Visualization:

temperatures = [73, 74, 75, 71, 69, 72, 76, 73]

i=0, temp=73: stack=[] → push 0 → stack=[0]
i=1, temp=74: 74>73 → pop 0, result[0]=1 → push 1 → stack=[1]
i=2, temp=75: 75>74 → pop 1, result[1]=1 → push 2 → stack=[2]
i=3, temp=71: 71<75 → push 3 → stack=[2,3]
i=4, temp=69: 69<71 → push 4 → stack=[2,3,4]
i=5, temp=72: 72>69 → pop 4, result[4]=1
              72>71 → pop 3, result[3]=2
              72<75 → push 5 → stack=[2,5]
i=6, temp=76: 76>72 → pop 5, result[5]=1
              76>75 → pop 2, result[2]=4
              push 6 → stack=[6]
i=7, temp=73: 73<76 → push 7 → stack=[6,7]

Remaining in stack get 0 (no warmer day found)

Why Monotonic Stack?

Maintains order: Stack always has decreasing temperatures
Efficient processing: When warmer temp found, resolve all colder temps in stack
Single pass: Each element processed exactly once

4. Evaluate Reverse Polish Notation (LeetCode 150)

Problem: Evaluate arithmetic expression in Reverse Polish Notation (RPN). Valid operators: +, -, *, /.

Reverse Polish Notation:

Operators come after operands
No parentheses needed
Left-to-right evaluation

Examples:

["2", "1", "+", "3", "*"] → ((2 + 1) * 3) = 9
["4", "13", "5", "/", "+"] → (4 + (13 / 5)) = 6
["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
→ 22

Approach: Use stack to store operands. When encountering operator, pop two operands, apply operation, push result.

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        operators = {"+", "-", "*", "/"}

        for token in tokens:
            if token not in operators:
                # It's a number, push to stack
                stack.append(int(token))
            else:
                # It's an operator, pop two operands
                # Note: LIFO order matters!
                second = stack.pop()  # Right operand
                first = stack.pop()   # Left operand

                # Perform operation
                if token == "+":
                    result = first + second
                elif token == "-":
                    result = first - second
                elif token == "*":
                    result = first * second
                elif token == "/":
                    # Integer division (truncate toward zero)
                    result = int(first / second)

                # Push result back to stack
                stack.append(result)

        # Final result is the only element in stack
        return stack[-1]

Time Complexity: O(n) - Single pass through tokens

Space Complexity: O(n) - Stack holds operands

Key Concepts:

RPN evaluation: Natural fit for stack data structure
Operand order: LIFO means second pop is first operand
Intermediate results: Push back to stack for future operations
Division truncation: Python's int() truncates toward zero

Important: Operand Order Matters!

# For subtraction: 5 - 3
stack = [5, 3]
second = stack.pop()  # 3
first = stack.pop()   # 5
result = first - second  # 5 - 3 = 2 ✓

# Wrong order would give: 3 - 5 = -2 ✗

Division Edge Case:

# Python division behavior
# Standard division: -3 / 2 = -1.5
# int() truncation: int(-1.5) = -1 (toward zero)
# Floor division: -3 // 2 = -2 (toward -infinity)

# For RPN, use int(a / b) for truncation toward zero

Step-by-step Example:

tokens = ["2", "1", "+", "3", "*"]

Step 1: "2" → stack = [2]
Step 2: "1" → stack = [2, 1]
Step 3: "+" → pop 1, pop 2 → 2+1=3 → stack = [3]
Step 4: "3" → stack = [3, 3]
Step 5: "*" → pop 3, pop 3 → 3*3=9 → stack = [9]
Result: 9

Core Stack Patterns

1. Balanced Expression Validation Pattern

When to use:

Matching pairs (brackets, tags, quotes)
Nested structures
Balanced sequences

Examples: Valid Parentheses, Valid HTML Tags, Remove Invalid Parentheses

Template:

def validate_balanced(expression):
    stack = []
    pairs = {')': '(', '}': '{', ']': '['}  # closing -> opening

    for char in expression:
        if char not in pairs:  # Opening bracket
            stack.append(char)
        else:  # Closing bracket
            if not stack or stack.pop() != pairs[char]:
                return False

    return not stack  # All matched if empty

Key characteristics:

Use hash map for pair matching
Stack stores opening elements
Check stack emptiness at end

2. Monotonic Stack Pattern

When to use:

Next greater/smaller element problems
Finding spans or ranges
Temperature, stock price problems

Examples: Daily Temperatures, Next Greater Element, Stock Span Problem

Monotonic Increasing Stack Template:

def next_greater_elements(arr):
    result = [-1] * len(arr)
    stack = []  # Stores indices

    for i in range(len(arr)):
        # Maintain increasing order
        while stack and arr[stack[-1]] < arr[i]:
            prev_index = stack.pop()
            result[prev_index] = arr[i]
        stack.append(i)

    return result

Monotonic Decreasing Stack Template:

def next_smaller_elements(arr):
    result = [-1] * len(arr)
    stack = []  # Stores indices

    for i in range(len(arr)):
        # Maintain decreasing order
        while stack and arr[stack[-1]] > arr[i]:
            prev_index = stack.pop()
            result[prev_index] = arr[i]
        stack.append(i)

    return result

Key characteristics:

Store indices, not values (to calculate distances)
Maintain increasing or decreasing order
O(n) time - each element pushed/popped once

3. Expression Evaluation Pattern

When to use:

Calculator problems
Postfix/prefix notation
Expression parsing

Examples: Evaluate RPN, Basic Calculator, Expression Parsing

Template:

def evaluate_postfix(tokens):
    stack = []
    operators = {'+', '-', '*', '/'}

    for token in tokens:
        if token not in operators:
            stack.append(int(token))
        else:
            b = stack.pop()  # Right operand
            a = stack.pop()  # Left operand
            result = apply_operation(a, b, token)
            stack.append(result)

    return stack[-1]

Key characteristics:

Stack stores operands/intermediate results
Operators trigger pop and computation
Order matters for non-commutative operations

4. Auxiliary Stack Pattern (Min/Max Tracking)

When to use:

Need to track additional property (min, max, etc.)
O(1) retrieval of special element required
Stack modifications affect tracked property

Examples: Min Stack, Max Stack, Stack with getMin()

Template:

class SpecialStack:
    def __init__(self):
        self.data_stack = []
        self.special_stack = []  # Tracks min/max/etc

    def push(self, val):
        self.data_stack.append(val)
        if not self.special_stack:
            self.special_stack.append(val)
        else:
            # Update special property
            current_special = self.special_stack[-1]
            new_special = combine(current_special, val)
            self.special_stack.append(new_special)

    def pop(self):
        self.data_stack.pop()
        self.special_stack.pop()

    def get_special(self):
        return self.special_stack[-1]

Key characteristics:

Two synchronized stacks
Trade space for O(1) retrieval
Both stacks must stay in sync

Performance Optimization Tips

1. Choose Right Container

# For simple stack operations: Use list
stack = []
stack.append(1)  # O(1)
stack.pop()      # O(1)

# For deque operations (both ends): Use collections.deque
from collections import deque
stack = deque()
stack.append(1)      # O(1)
stack.pop()          # O(1)
stack.appendleft(1)  # O(1) - bonus operation

Key insight: Python list is optimized for stack operations. Use deque only if you need operations on both ends.

2. Store Indices vs Values in Monotonic Stack

# Store indices (more flexible)
def next_greater_with_distance(arr):
    result = [-1] * len(arr)
    stack = []  # Store indices

    for i in range(len(arr)):
        while stack and arr[stack[-1]] < arr[i]:
            prev_idx = stack.pop()
            result[prev_idx] = i - prev_idx  # Can calculate distance
        stack.append(i)
    return result

# Store values (only if distance not needed)
def next_greater_simple(arr):
    stack = []  # Store values
    result = []

    for num in reversed(arr):
        while stack and stack[-1] <= num:
            stack.pop()
        result.append(stack[-1] if stack else -1)
        stack.append(num)

    return result[::-1]

Key insight: Store indices when you need to calculate distances or positions.

3. Avoid Unnecessary Operations

# Inefficient: Check same condition multiple times
for token in tokens:
    if token == "+":
        result = a + b
    elif token == "-":
        result = a - b
    elif token == "*":
        result = a * b
    elif token == "/":
        result = a / b
    stack.append(result)

# Efficient: Use dictionary for operator dispatch
operators = {
    '+': lambda a, b: a + b,
    '-': lambda a, b: a - b,
    '*': lambda a, b: a * b,
    '/': lambda a, b: int(a / b)
}

for token in tokens:
    if token in operators:
        b, a = stack.pop(), stack.pop()
        stack.append(operators[token](a, b))
    else:
        stack.append(int(token))

4. Early Termination in Validation

# Optimized: Return False immediately
def is_valid(s):
    stack = []
    for char in s:
        if char == '(':
            stack.append(char)
        else:
            if not stack:  # Early termination
                return False
            stack.pop()
    return not stack

# Also check impossible cases early
def is_valid(s):
    if len(s) % 2 != 0:  # Odd length can't be balanced
        return False
    # ... rest of logic

Common Pitfalls and Solutions

1. Forgetting to Check Empty Stack

# Wrong: Potential error on empty stack
def process_stack(stack):
    top = stack.pop()  # Error if stack empty!

# Correct: Always check before pop
def process_stack(stack):
    if not stack:
        return None
    top = stack.pop()
    return top

# Or use try-except
def process_stack(stack):
    try:
        return stack.pop()
    except IndexError:
        return None

2. Wrong Operand Order in RPN

# Wrong: Reversed operands
second = stack.pop()
first = stack.pop()
result = second - first  # Wrong! Should be first - second

# Correct: Remember LIFO order
second = stack.pop()  # Popped second, was pushed second
first = stack.pop()   # Popped first, was pushed first
result = first - second  # Correct order for subtraction

3. Not Handling Final Stack State

# Wrong: Assume stack has exactly one element
def evaluate(tokens):
    stack = []
    # ... process tokens ...
    return stack[-1]  # What if stack is empty or has multiple elements?

# Correct: Validate final state
def evaluate(tokens):
    stack = []
    # ... process tokens ...
    if len(stack) != 1:
        raise ValueError("Invalid expression")
    return stack[0]

4. Confusing Peek vs Pop

# Wrong: Pop when you just want to look
def check_top(stack):
    top = stack.pop()  # Modifies stack!
    return top == target

# Correct: Peek without modifying
def check_top(stack):
    if not stack:
        return False
    return stack[-1] == target  # Just look, don't pop

5. Integer Division in Python

# Wrong: Floor division for RPN
result = first // second  # -3 // 2 = -2 (wrong for RPN)

# Correct: Truncate toward zero
result = int(first / second)  # int(-3 / 2) = int(-1.5) = -1

# Explanation:
# Floor division (//): Always rounds toward -infinity
# int() truncation: Rounds toward zero
# RPN expects truncation toward zero

Stack Time Complexity Summary

Problem	Approach	Time Complexity	Space Complexity
Valid Parentheses	Stack matching	O(n)	O(n)
Min Stack	Auxiliary stack	O(1) per operation	O(n)
Daily Temperatures	Monotonic stack	O(n)	O(n)
Evaluate RPN	Stack evaluation	O(n)	O(n)
Next Greater Element	Monotonic stack	O(n)	O(n)
Basic Calculator	Stack with operators	O(n)	O(n)

Key Insights:

Push/Pop: Always O(1)
Full processing: O(n) - each element touched constant times
Monotonic stack: O(n) - each element pushed/popped at most once
Space: Usually O(n) worst case for stack storage

Queue Quick Overview

Queue follows FIFO (First In, First Out) - like a line at a store. The first person to arrive is the first to be served.

Queue Operations

Operation	Description	Time Complexity	Python Implementation
`enqueue(x)`	Add element to rear	O(1)	`queue.append(x)`
`dequeue()`	Remove element from front	O(1)	`queue.popleft()`
`front()`	View front element	O(1)	`queue[0]`
`isEmpty()`	Check if empty	O(1)	`not queue`

Python Queue Implementation

from collections import deque

# Initialize queue
queue = deque()

# Enqueue (add to rear)
queue.append(1)
queue.append(2)
queue.append(3)
# Queue: [1, 2, 3] (1 is front, 3 is rear)

# Dequeue (remove from front)
front = queue.popleft()  # Returns 1
# Queue: [2, 3]

# Peek front
front_element = queue[0]  # Returns 2

# Check empty
is_empty = len(queue) == 0  # Returns False

Note: We'll explore Queue in depth when covering Tree traversal (BFS) and other graph algorithms where Queue is the primary data structure.

Conclusion

Stack is a fundamental data structure with elegant solutions to many algorithmic problems. Key takeaways:

Core Concepts Mastered:

Stack Fundamentals:

LIFO principle: Last In, First Out access pattern
O(1) operations: Push, pop, peek all constant time
Python implementation: List with append/pop
Use cases: Parsing, expression evaluation, backtracking

Essential Patterns Mastered:

Pattern 1: Balanced expression validation (Valid Parentheses)

Pattern 2: Monotonic stack for next greater/smaller (Daily Temperatures)

Pattern 3: Expression evaluation (Evaluate RPN)

Pattern 4: Auxiliary stack for tracking properties (Min Stack)

Problem-Solving Strategies:

Matching pairs: Use stack with hash map for pair validation
Next greater/smaller: Use monotonic stack pattern
Expression evaluation: Natural fit for stack (RPN, calculators)
Track min/max: Auxiliary stack maintains property in O(1)
Nested structures: Stack handles arbitrary nesting depth

Key Optimization Principles:

Store indices in monotonic stacks for distance calculations
Check empty before pop to avoid errors
Remember operand order in non-commutative operations
Synchronize auxiliary stacks for property tracking
Use early termination in validation problems

When to Use Stack:

Need to reverse order or process in LIFO manner
Matching/balancing problems (parentheses, tags)
Next greater/smaller element problems
Expression parsing and evaluation
Backtracking and undo operations
Function call simulation

Next Steps:

Building on stack foundations, future topics will cover:

Queue and BFS (Tree level-order traversal)
Binary Trees and Traversals (using stack for DFS)
Graph Algorithms (DFS with stack, BFS with queue)
Backtracking (stack-based state management)

The problems covered here represent fundamental stack patterns that appear across technical interviews and competitive programming. Master these patterns, and you'll recognize stack opportunities in complex problems.

Practice Problems for Mastery:

Stack Fundamentals:

20. Valid Parentheses
155. Min Stack
232. Implement Queue using Stacks
225. Implement Stack using Queues
1047. Remove All Adjacent Duplicates in String

Monotonic Stack:

739. Daily Temperatures
496. Next Greater Element I
503. Next Greater Element II
84. Largest Rectangle in Histogram
42. Trapping Rain Water

Expression Evaluation:

150. Evaluate Reverse Polish Notation
224. Basic Calculator
227. Basic Calculator II
772. Basic Calculator III

Advanced Stack:

394. Decode String
716. Max Stack
895. Maximum Frequency Stack
946. Validate Stack Sequences

References:

NeetCode - Algorithms
LeetCode Patterns
Greg Hogg DSA Algorithm YouTube Channel
Algorithm Design Manual by Steven Skiena
Introduction to Algorithms by Cormen et al.

This comprehensive guide provides a solid foundation for mastering stack data structures and recognizing stack patterns in algorithmic problem-solving.