Chapter 1: Arrays & Strings

1. Two Pointers Technique

Algorithm Explanation

The two pointers technique uses two pointers (indices) that traverse the array from different positions, typically:

• Opposite ends: One pointer starts at the beginning, another at the end
• Same direction: Both pointers move in the same direction at different speeds
• Key insight: By moving pointers based on conditions, we can solve problems in O(n) time instead of O(n²)

Example: Two Sum in Sorted Array

Problem: Given a sorted array and a target, find two numbers that add up to the target.

def two_sum_sorted(nums, target):
    """
    Find two numbers in sorted array that sum to target.
    
    Args:
        nums: List of integers (sorted in ascending order)
        target: Target sum
    
    Returns:
        List of two indices [i, j] where nums[i] + nums[j] == target
        Returns [-1, -1] if no such pair exists
    """
    # Step 1: Initialize two pointers
    # left starts at the beginning (smallest values)
    # right starts at the end (largest values)
    left = 0
    right = len(nums) - 1
    
    # Step 2: Continue until pointers meet
    while left < right:
        # Step 3: Calculate current sum
        current_sum = nums[left] + nums[right]
        
        # Step 4: Compare with target
        if current_sum == target:
            # Found the pair!
            return [left, right]
        elif current_sum < target:
            # Sum is too small, move left pointer right
            # Why? Because array is sorted, moving left right increases sum
            left += 1
        else:
            # Sum is too large, move right pointer left
            # Why? Moving right left decreases sum
            right -= 1
    
    # Step 5: No pair found
    return [-1, -1]

Time Complexity:

O(n) - Each element is visited at most once

Space Complexity:

O(1) - Only using a constant amount of extra space

2. Sliding Window Technique

Algorithm Explanation

The sliding window technique maintains a "window" of elements in the array/string. Instead of recalculating everything, we:

• Expand: Add elements to the window
• Shrink: Remove elements from the window
• Update: Maintain the current state (sum, count, etc.) incrementally

Example: Maximum Sum Subarray of Size K

Problem: Find the maximum sum of any contiguous subarray of size k.

def max_sum_subarray_k(nums, k):
    """
    Find maximum sum of subarray of size k using sliding window.
    
    Args:
        nums: List of integers
        k: Size of subarray
    
    Returns:
        Maximum sum of any subarray of size k
    """
    # Step 1: Handle edge case
    if len(nums) < k:
        return 0
    
    # Step 2: Calculate sum of first window
    # We start by computing the sum of the first k elements
    window_sum = sum(nums[:k])
    max_sum = window_sum
    
    # Step 3: Slide the window
    # Start from index k (after the first window)
    for i in range(k, len(nums)):
        # Step 3a: Remove leftmost element from window
        # Subtract the element that's leaving the window
        window_sum -= nums[i - k]
        
        # Step 3b: Add new element to window
        # Add the element that's entering the window
        window_sum += nums[i]
        
        # Step 3c: Update maximum sum
        # Compare current window sum with maximum seen so far
        max_sum = max(max_sum, window_sum)
    
    return max_sum

Visualization Example:

Array: [1, 4, 2, 10, 23, 3, 1, 0, 20], k = 4

• Window 1: [1, 4, 2, 10] → sum = 17
• Window 2: [4, 2, 10, 23] → sum = 17 - 1 + 23 = 39
• Window 3: [2, 10, 23, 3] → sum = 39 - 4 + 3 = 38
• ... and so on

Time Complexity:

O(n) - Each element is visited exactly once

Space Complexity:

O(1) - Only using constant extra space

3. Hash Maps and Hash Sets

Algorithm Explanation

Hash maps (dictionaries) and hash sets provide:

• O(1) average: Insert, lookup, and delete operations
• Key-value storage: Maps store key-value pairs
• Set operations: Sets store unique elements
• Trade-off: Uses extra space for speed

Example: Two Sum (Unsorted Array)

Problem: Find two numbers in an unsorted array that sum to target.

def two_sum_unsorted(nums, target):
    """
    Find two numbers that sum to target using hash map.
    
    Args:
        nums: List of integers (unsorted)
        target: Target sum
    
    Returns:
        List of two indices [i, j] where nums[i] + nums[j] == target
    """
    # Step 1: Create hash map to store number -> index mapping
    # Key: number value, Value: its index in array
    num_map = {}
    
    # Step 2: Iterate through array
    for i, num in enumerate(nums):
        # Step 3: Calculate complement
        # If nums[i] + complement == target, then complement = target - nums[i]
        complement = target - num
        
        # Step 4: Check if complement exists in map
        if complement in num_map:
            # Found! Return indices
            # num_map[complement] is the index where we saw the complement
            return [num_map[complement], i]
        
        # Step 5: Store current number and its index
        # We store it after checking to avoid using same element twice
        num_map[num] = i
    
    # Step 6: No pair found
    return [-1, -1]

Example Trace:

nums = [2, 7, 11, 15], target = 9

• i=0, num=2: complement=7, not in map → store {2: 0}
• i=1, num=7: complement=2, found in map! → return [0, 1]

Time Complexity:

O(n) - Single pass through array

Space Complexity:

O(n) - Hash map can store up to n elements

4. Kadane's Algorithm (Maximum Subarray Sum)

Algorithm Explanation

Kadane's algorithm uses dynamic programming thinking:

• Key insight: At each position, decide whether to extend the previous subarray or start fresh
• Decision rule: If current element makes the sum negative, start fresh (negative sum can't help future sums)
• Optimal substructure: Maximum sum ending at position i depends on maximum sum ending at position i-1

Example: Maximum Subarray Sum

Problem: Find the contiguous subarray with the largest sum.

def max_subarray_sum(nums):
    """
    Find maximum sum of contiguous subarray using Kadane's algorithm.
    
    Args:
        nums: List of integers (can contain negative numbers)
    
    Returns:
        Maximum sum of any contiguous subarray
    """
    # Step 1: Initialize
    # max_ending_here: maximum sum of subarray ending at current position
    # max_so_far: maximum sum seen so far (our answer)
    max_ending_here = nums[0]
    max_so_far = nums[0]
    
    # Step 2: Process each element
    for i in range(1, len(nums)):
        # Step 3: Decision: extend or start fresh?
        # Option 1: Extend previous subarray: max_ending_here + nums[i]
        # Option 2: Start fresh: nums[i]
        # Choose the maximum (greedy choice)
        max_ending_here = max(max_ending_here + nums[i], nums[i])
        
        # Step 4: Update global maximum
        # Track the best sum we've seen across all positions
        max_so_far = max(max_so_far, max_ending_here)
    
    return max_so_far

Example Trace:

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

• i=0: max_ending_here=-2, max_so_far=-2
• i=1: max_ending_here=max(-2+1, 1)=1, max_so_far=max(-2, 1)=1
• i=2: max_ending_here=max(1-3, -3)=-2, max_so_far=1
• i=3: max_ending_here=max(-2+4, 4)=4, max_so_far=4
• i=4: max_ending_here=max(4-1, -1)=3, max_so_far=4
• i=5: max_ending_here=max(3+2, 2)=5, max_so_far=5
• i=6: max_ending_here=max(5+1, 1)=6, max_so_far=6
• ... final answer: 6 (subarray [4, -1, 2, 1])

Time Complexity:

O(n) - Single pass through array

Space Complexity:

O(1) - Only using constant extra space

5. String Manipulation Techniques

Example: Valid Palindrome

Problem: Check if a string is a palindrome (ignoring case and non-alphanumeric characters).

def is_palindrome(s):
    """
    Check if string is palindrome using two pointers.
    
    Args:
        s: Input string (may contain spaces, punctuation)
    
    Returns:
        True if palindrome, False otherwise
    """
    # Step 1: Initialize two pointers
    left = 0
    right = len(s) - 1
    
    # Step 2: Continue until pointers meet
    while left < right:
        # Step 3: Skip non-alphanumeric characters
        # Move left pointer until we find alphanumeric
        while left < right and not s[left].isalnum():
            left += 1
        
        # Move right pointer until we find alphanumeric
        while left < right and not s[right].isalnum():
            right -= 1
        
        # Step 4: Compare characters (case-insensitive)
        if s[left].lower() != s[right].lower():
            return False
        
        # Step 5: Move pointers inward
        left += 1
        right -= 1
    
    # Step 6: All characters matched
    return True

Time Complexity:

O(n) - Each character visited at most once

Space Complexity:

O(1) - Only using constant extra space

📚 Chapter Summary

• Two Pointers: Use for sorted arrays, palindrome checking, in-place modifications
• Sliding Window: Use for subarray/substring problems with fixed or variable size
• Hash Maps: Use when you need O(1) lookups, frequency counting, or complement finding
• Kadane's Algorithm: Use for maximum subarray sum problems
• String Manipulation: Combine two pointers with string-specific operations

Key Takeaway: These techniques often reduce time complexity from O(n²) to O(n) by avoiding nested loops and using smart pointer movement or hash-based lookups.