Arrays & Strings

Core Concepts

Arrays and strings share many algorithmic techniques because strings are essentially character arrays. The most common patterns to master are:

• Two Pointers: Moving two pointers towards each other or in the same direction.
• Sliding Window: Maintaining a subset of items (a "window") to find optimal sub-arrays.
• Prefix Sum: Precomputing cumulative sums for O(1) range queries.

Cheatsheet Formulas

• Two Pointers (Opposite Ends): left = 0, right = n - 1 while left < right. Best for sorted arrays or reversing.
• Sliding Window: Expand right pointer. If window invalid, shrink left pointer until valid. Track max/min.
• Prefix Sum: prefix[i] = prefix[i-1] + nums[i]. Range sum [i, j] is prefix[j] - prefix[i-1].

Classic Problem: Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_map = {}
        for i, num in enumerate(nums):
            complement = target - num
            if complement in num_map:
                return [num_map[complement], i]
            num_map[num] = i
        return []

Classic Problem: Reverse String (Two Pointers)

Write a function that reverses a string. The input string is given as an array of characters s. Do this in-place with O(1) extra memory.

class Solution {
    public void reverseString(char[] s) {
        int left = 0;
        int right = s.length - 1;
        while (left < right) {
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left++;
            right--;
        }
    }
}

class Solution:
    def reverseString(self, s: List[str]) -> None:
        left, right = 0, len(s) - 1
        while left < right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1