Arrays and strings are the foundation of coding interviews — you’ll encounter them in nearly every problem set. This page provides battle-tested Java templates for the most important patterns: sliding window, two pointers, binary search on answer, prefix sum, hash maps, and string algorithms like KMP and Manacher. Master these and you’ll have the tools to solve a huge fraction of Medium-level problems.

This template covers the fundamental patterns for array and string problems. Sliding window, two pointers, and prefix sum together solve a huge fraction of Medium problems.

  • Beginner’s Guide: LeetCode Beginner’s Guide

    Summary

    | Pattern | Signal Phrases | Time | |—|—|—| | Sliding Window | “substring”, “subarray”, “at most k” | O(n) | | Two Pointers | “sorted”, “pair”, “container” | O(n) | | Binary Search on Answer | “minimize max”, “feasibility” | O(n log range) | | Prefix Sum | “range sum”, “subarray sum” | O(n) build, O(1) query | | Hash Map | “frequency”, “group”, “two sum” | O(n) | | KMP | “pattern in string” | O(n + m) |

Contents

Sliding Window (fixed/variable)

When to use: “longest substring”, “shortest subarray”, “at most k distinct”, or any problem asking for a contiguous subrange that satisfies a constraint.

Sliding Window — Longest Substring Without Repeating 0123 4567 #1 a b c a b c b b expand → window "abc", len = 3 seen: {a, b, c} #2 a b c a b c b b expand → "abca" — 'a' repeats! shrink left to remove duplicate #3 a b c a b c b b shrink → "bca", len = 3 no duplicates, continue expanding #4 a b c a b c b b expand → "abc", len = 3 max length = 3
ID Title Link Solution
3 Longest Substring Without Repeating Characters Link Solution
76 Minimum Window Substring Link -
392 Is Subsequence Link Solution
424 Longest Repeating Character Replacement Link -
616 Add Bold Tag in String Link Solution
681 Next Closest Time Link Solution
713 Subarray Product Less Than K Link Solution
2461 Maximum Sum of Distinct Subarrays With Length K Link Solution 
// Variable-size window (e.g., longest substring without repeating)
static int longestNoRepeat(String s){
    int[] cnt = new int[256];
    int dup = 0, best = 0;
    for (int l = 0, r = 0; r < (int)s.size(); ++r){
        dup += (++cnt[(int char)s.charAt(r)] == 2);
        while (dup > 0){
            dup -= (--cnt[(int char)s[l++]] == 1);
        }
        best = Math.max(best, r - l + 1);
    }
    return best;
}
ID Title Link Solution
3 Longest Substring Without Repeating Characters Link Solution
76 Minimum Window Substring Link -
392 Is Subsequence Link Solution
424 Longest Repeating Character Replacement Link -
616 Add Bold Tag in String Link Solution
681 Next Closest Time Link Solution
713 Subarray Product Less Than K Link Solution
2461 Maximum Sum of Distinct Subarrays With Length K Link Solution

Two Pointers (sorted arrays/strings)

When to use: “pair with target sum in sorted array”, “container with most water”, “valid palindrome”, or when the array is sorted and you can shrink the search space from both ends.

Two Pointers — Find Pair with Target Sum = 9 1 0 2 1 3 2 4 3 5 4 6 5 7 6 left right move → Step 1: left=0, right=6 → 1 + 7 = 8 < 9 → move left Step 2: left=1, right=6 → 2 + 7 = 9 = target ✓
ID Title Link Solution
15 3Sum Link -
11 Container With Most Water Link -
125 Valid Palindrome Link -
1768 Merge Strings Alternately Link Solution 
static boolean twoSumSorted(int[] a, int target){
    int l = 0, r = (int)a.size() - 1;
    while (l < r){
        long sum = (long)a[l] + a[r];
        if (sum == target) return true;
        if (sum < target) ++l; else --r;
    }
    return false;
}
ID Title Link Solution
15 3Sum Link -
11 Container With Most Water Link -
125 Valid Palindrome Link -
1768 Merge Strings Alternately Link Solution

Binary Search on Answer (monotonic predicate)

When to use: “minimize the maximum”, “feasibility check”, “minimum speed/capacity”, or when the answer has a monotonic property (if x works, then x+1 also works).

ID Title Link Solution
33 Search in Rotated Sorted Array Link Solution
34 Find First and Last Position of Element in Sorted Array Link -
162 Find Peak Element Link -
875 Koko Eating Bananas Link -
1870 Minimum Speed to Arrive on Time Link Solution 
static long binsearch(long lo, long hi){ // [lo, hi]
    var good = [&](long x){ /* check feasibility */ return true; }
    while (lo < hi){
        long mid = (lo + hi) >> 1;
        if (good(mid)) hi = mid; else lo = mid + 1;
    }
    return lo;
}
ID Title Link Solution
33 Search in Rotated Sorted Array Link Solution
34 Find First and Last Position of Element in Sorted Array Link -
162 Find Peak Element Link -
875 Koko Eating Bananas Link -
1870 Minimum Speed to Arrive on Time Link Solution

Prefix Sum / Difference Array

When to use: “range sum query”, “subarray sum equals k”, “number of subarrays with sum”, or when you need O(1) range queries after O(n) preprocessing.

ID Title Link Solution
303 Range Sum Query - Immutable Link Solution
523 Continuous Subarray Sum Link Solution
560 Subarray Sum Equals K Link -
238 Product of Array Except Self Link -
525 Contiguous Array Link Solution
1177 Can Make Palindrome from Substring Link Solution
370 Range Addition Link -
134 Gas Station Link Solution
2270 Number of Ways to Split Array Link Solution 
int[]prefix(int[] a){
    int[]ps(a.size()+1);
    for (int i = 0; i < (int)a.size(); ++i) ps[i+1] = ps[i] + a[i];
    return ps;
}
ID Title Link Solution
303 Range Sum Query - Immutable Link Solution
523 Continuous Subarray Sum Link Solution
560 Subarray Sum Equals K Link -
238 Product of Array Except Self Link -
525 Contiguous Array Link Solution
1177 Can Make Palindrome from Substring Link Solution
370 Range Addition Link -
134 Gas Station Link Solution
2270 Number of Ways to Split Array Link Solution

Hash Map Frequencies

When to use: “two sum”, “group anagrams”, “frequency count”, “contains duplicate”, or any problem where you need O(1) lookups by value.

ID Title Link Solution
1 Two Sum Link -
49 Group Anagrams Link -
242 Valid Anagram Link Solution
217 Contains Duplicate Link Solution
219 Contains Duplicate II Link Solution
383 Ransom Note Link Solution
981 Time Based Key-Value Store Link -
359 Logger Rate Limiter Link -
2365 Task Scheduler II Link Solution
2342 Max Sum of a Pair With Equal Sum of Digits Link Solution 
// import java.util.*;
HashMap<Integer, Integer> freq = new HashMap<Integer, Integer>();
for (int x: nums) ++freq[x];
ID Title Link Solution
1 Two Sum Link -
49 Group Anagrams Link -
242 Valid Anagram Link Solution
217 Contains Duplicate Link Solution
219 Contains Duplicate II Link Solution
383 Ransom Note Link Solution
981 Time Based Key-Value Store Link -
359 Logger Rate Limiter Link -
2365 Task Scheduler II Link Solution
2342 Max Sum of a Pair With Equal Sum of Digits Link Solution

When to use: “find pattern in string”, “shortest palindrome by prepending”, “repeated string match”, or when you need O(n + m) exact pattern matching.

KMP is a pattern matching algorithm that finds occurrences of a pattern string P within a text string T efficiently — without re-checking characters that are already known to match.

While a naive substring search checks character-by-character and backtracks when a mismatch occurs (worst case O(n * m)), KMP preprocesses the pattern to know how far it can safely skip ahead when mismatches happen.

It does this using a “prefix function” (also called LPS — longest prefix which is also suffix).

Steps

Preprocess the pattern to build the lps[] array.

  • lps[i] = the length of the longest proper prefix of the substring P[0..i] which is also a suffix of this substring.

  • Proper prefix = prefix ≠ the string itself.

Use the LPS array during the search

  • When mismatch occurs, instead of resetting j = 0, we move j back to lps[j-1].
ID Title Link Solution
28 Find the Index of the First Occurrence in a String Link -
214 Shortest Palindrome Link -
686 Repeated String Match Link Solution 
int[]kmpPi(String s) {
    int n = s.size();
    int[] pi = new int[n];
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];
        while (j > 0 && s.charAt(i) != s.charAt(j)) j = pi[j - 1];
        if (s.charAt(i) == s.charAt(j)) j++;
        pi[i] = j;
    }
    return pi;
}
ID Title Link Solution
28 Find the Index of the First Occurrence in a String Link -
214 Shortest Palindrome Link -
686 Repeated String Match Link Solution

Manacher (Longest Palindromic Substring, O(n))

When to use: “longest palindromic substring” when O(n) time is required, or counting all palindromic substrings efficiently.

ID Title Link Solution
5 Longest Palindromic Substring Link - 
static String manacher(String s) {
    String t = "|";
    for (char c : s.toCharArray()) { t.add(c); t.add('|'); }
    int n = t.size();
    int[] p = new int[n];
    int c = 0, r = 0, best = 0, center = 0;
    for (int i = 0; i < n; i++) {
        int mir = 2 c - i;
        if (i < r) p[i] = Math.min(r - i, p[mir]);
        while (i - 1 - p[i] >= 0 && i + 1 + p[i] < n && t[i - 1 - p[i]] == t[i + 1 + p[i]]) p.put(i, p.getOrDefault(i, 0) + 1);
        if (i + p[i] > r) { c = i; r = i + p[i]; }
        if (p[i] > best) { best = p[i]; center = i; }
    }
    int start = (center - best) / 2;
    return s.substring(start, best);
}
ID Title Link Solution
5 Longest Palindromic Substring Link -

Z-Algorithm (Pattern occurrences)

When to use: “find all pattern occurrences”, “longest happy prefix”, or as an alternative to KMP for pattern matching.

ID Title Link Solution
1392 Longest Happy Prefix Link - 
int[]zfunc(String s) {
    int n = s.size();
    int[] z = new int[n];
    int l = 0, r = 0;
    for (int i = 1; i < n; i++) {
        if (i <= r) z[i] = Math.min(r - i + 1, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z.put(i, z.getOrDefault(i, 0) + 1);
        if (i + z[i] - 1 > r) { l = i; r = i + z[i] - 1; }
    }
    return z;
}
ID Title Link Solution
1392 Longest Happy Prefix Link -

String Rolling Hash (Rabin–Karp)

When to use: “repeated DNA sequences”, “longest duplicate substring”, or when you need to compare many substrings in O(1) each after O(n) preprocessing.

ID Title Link Solution
187 Repeated DNA Sequences Link -
686 Repeated String Match Link Solution
1044 Longest Duplicate Substring Link - 
class RH {
    public static long B = 911382323, M = 972663749;
    long[]p, h;
    RH(String s) {
        int n = s.size();
        p.assign(n + 1, 1);
        h.assign(n + 1, 0);
        for (int i = 0; i < n; i++) {
            p[i + 1] = p[i] * B % M;
            h[i + 1] = (h[i] * B + s.charAt(i)) % M;
        }
    }
    long get(int l, int r) {  // [l, r)
        return (h[r] - h[l] * p[r - l] % M + M) % M;
    }
}
ID Title Link Solution
187 Repeated DNA Sequences Link -
686 Repeated String Match Link Solution
1044 Longest Duplicate Substring Link -

More templates