BigN Primer

🔄 Palindrome Check

“racecar” - Use 2 pointers from start and end, compare towards the middle. Or start from middle and expand outwards (check odd/even length first).

boolean isPalindrome(String s) {
    // Two pointers: start and end, compare towards middle
    for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
        if (s.charAt(i) != s.charAt(j)) {
            return false;
        }
    }
    return true;
}

🔀 Anagram Detection

“cat”, “tac” - Same letters, different order. Two approaches with different tradeoffs:

boolean isAnagram(String s, String t) {
    // Simple approach: sort both strings and compare
    char[] sChars = s.toCharArray();
    char[] tChars = t.toCharArray();
    Arrays.sort(sChars);
    Arrays.sort(tChars);
    return String.valueOf(sChars).equals(String.valueOf(tChars));
    // Time: O(s log s) + O(t log t), Space: O(max(s, t))
}

boolean isAnagram(String s, String t) {
    // Optimized: character frequency counting
    if (s.length() != t.length()) return false;

    Map<Character, Integer> map = new HashMap<>();

    // Count characters in s
    for (char c : s.toCharArray()) {
        map.put(c, map.getOrDefault(c, 0) + 1);
    }

    // Decrement for characters in t
    for (char c : t.toCharArray()) {
        if (!map.containsKey(c)) return false;
        map.put(c, map.get(c) - 1);
        if (map.get(c) == 0) map.remove(c);
    }

    return map.isEmpty();
    // Time: O(max(s, t)) ~ O(n), Space: O(1) for lowercase ASCII
}

🎯 Core Use Cases

🔍 Classic Pattern: Two Sum

The quintessential HashMap problem - store what you need, lookup what you have.

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();

    for (int i = 0; i < nums.length; i++) {
        if (map.containsKey(nums[i])) {
            return new int[]{map.get(nums[i]), i};
        }
        map.put(target - nums[i], i);
    }
    return new int[]{-1, -1}; // not found
}

📊 Frequency Counting Pattern

Essential for anagrams, character analysis, and finding duplicates.

// Character frequency counting pattern
Map<Character, Integer> freq = new HashMap<>();
for (char c : s.toCharArray()) {
    freq.put(c, freq.getOrDefault(c, 0) + 1);
}

🔄 Map Iteration

// Iterating over a map - the right way
for (Map.Entry<K, V> entry : map.entrySet()) {
    System.out.println(entry.getKey());
    System.out.println(entry.getValue());
}

📚 Stack (LIFO)

Last In, First Out - like a stack of plates

// Use Deque instead of Stack (better practice)
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);    // add to top
stack.push(2);
stack.peek();     // returns 2 (top element)
stack.pop();      // removes and returns 2

🚶 Queue (FIFO)

First In, First Out - like a line of people

// Use Deque instead of Queue interface
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1);   // add to back
queue.offer(2);
queue.peek();     // returns 1 (front element)
queue.poll();     // removes and returns 1

🔍 Classic Stack Problem

Valid Parentheses - the quintessential stack problem every engineer should know.

// Classic stack problem: Valid Parentheses
public boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();

    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } else {
            if (stack.isEmpty()) return false;
            char top = stack.pop();
            if (c == ')' && top != '(') return false;
            if (c == ']' && top != '[') return false;
            if (c == '}' && top != '{') return false;
        }
    }
    return stack.isEmpty();
}

📊 Graph Representations

🎯 Adjacency List (Recommended)

Always use this version - works with any node type, no compilation issues.

// Adjacency List - ALWAYS use this version
Map<Integer, List<Integer>> adjList = new HashMap<>() {
    {
        put(0, Arrays.asList(1));
        put(1, Arrays.asList(0, 2, 3));
        put(2, Arrays.asList(1, 3));
        put(3, Arrays.asList(1, 2));
    }
};

⚖️ Weighted Graphs

For problems involving costs, distances, or weights (e.g., currency exchange).

// Weighted Graph with Double weights
Map<String, Map<String, Double>> adjList = new HashMap<>();
Map<String, Double> edges = new HashMap<>();
edges.put("USD", 990.0);
edges.put("EUR", 1150.0);
adjList.put("BTC", edges);
// BTC -> USD has weight 990.0

🔍 BFS Template

The bread and butter of graph problems - memorize this pattern.

// BFS Template for graph problems
Queue<Integer> queue = new ArrayDeque<>();
Set<Integer> visited = new HashSet<>();

queue.offer(startNode);
visited.add(startNode);

while (!queue.isEmpty()) {
    int node = queue.poll();

    for (int neighbor : adjList.get(node)) {
        if (!visited.contains(neighbor)) {
            visited.add(neighbor);
            queue.offer(neighbor);
        }
    }
}

🔢 Basic Heap Types

// MinHeap - default ordering (ascending)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(5);
minHeap.offer(1); 
minHeap.offer(3);
// poll() returns: 1, 3, 5

// MaxHeap - reverse ordering (descending)  
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
maxHeap.offer(5);
maxHeap.offer(1);
maxHeap.offer(3);
// poll() returns: 5, 3, 1

🎯 Custom Comparator

For complex objects like points, entries, or custom sorting logic.

// Custom comparator for complex objects
PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
    public int compare(int[] p1, int[] p2) {
        // Compare by distance for K-closest points problem
        double d1 = Math.sqrt(p1[0] * p1[0] + p1[1] * p1[1]);
        double d2 = Math.sqrt(p2[0] * p2[0] + p2[1] * p2[1]);
        return Double.compare(d1, d2); // min-heap by distance
    }
});

🏆 Top K Pattern (Most Important!)

Counter-intuitive but crucial: Use the OPPOSITE heap type!

// Top K Pattern - use OPPOSITE heap!
// For Top K smallest → use MAX heap (size K)
// For Top K largest → use MIN heap (size K)

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
for (int num : nums) {
    maxHeap.offer(num);
    if (maxHeap.size() > k) {
        maxHeap.poll(); // remove largest element
    }
}
// Heap now contains K smallest elements
// Runtime: O(N log K) instead of O(N log N)

📊 Sorting Algorithm Comparison

🔢 Counting Sort Implementation

Perfect for small integer ranges. Stable, O(n + k) time complexity.

// Counting Sort - O(n + k) time, stable algorithm
int[] A = {1, 4, 1, 2, 7, 5, 2};

// Step 1: Count frequencies
int[] counts = new int[A.length + 1];
for (int i : A) {
    counts[i]++;
}

// Step 2: Transform to starting indices
for (int i = 1; i < counts.length; i++) {
    counts[i] = counts[i] + counts[i - 1];
}

// Step 3: Make it stable (work backwards)
for (int i = counts.length - 1; i >= 0; i--) {
    if (i == 0) {
        counts[i] = 0;
    } else {
        counts[i] = counts[i - 1];
    }
}

// Step 4: Build sorted array
int[] sorted = new int[A.length];
for (int i = 0; i < A.length; i++) {
    int num = A[i];
    int index = counts[num];
    sorted[index] = num;
    counts[num]++; // increment for next occurrence
}

🏳️ Dutch National Flag (Sort Colors)

Classic 3-way partitioning problem - sort 0s, 1s, 2s in one pass.

// Sort Colors - Dutch National Flag Problem
public void sortColors(int[] nums) {
    int zeroIndex = 0;      // boundary for 0s
    int twoIndex = nums.length - 1; // boundary for 2s
    int i = 0;

    // Process all elements before twoIndex
    while (i <= twoIndex) {
        if (nums[i] == 0) {
            swap(nums, i, zeroIndex);
            zeroIndex++;
            i++; // safe to advance after placing 0
        } else if (nums[i] == 2) {
            swap(nums, i, twoIndex);
            twoIndex--;
            // Don't advance i - need to check swapped element
        } else {
            i++; // nums[i] == 1, already in correct region
        }
    }
}