Mixed Patterns

This guide covers 18 Blind 75 problems that don't belong to a single dedicated pattern guide — they use array scanning, HashMap grouping, prefix/suffix arrays, palindromic expansion, matrix manipulation, HashSet sequential scan, and bit manipulation.

• All 18 problems here are Blind 75 — every one is interview-essential by definition
• Patterns are simpler than the main guides but these problems appear constantly as warm-ups, early-round screens, or standalone problems
• Prioritize if short on time: Max Subarray, Group Anagrams, Longest Palindromic Substring, Product Except Self

Quick Revision - Must Do Problems

Every problem in this guide is Blind 75 — all are must-do.

Practice Tips

How to Identify Each Pattern

• Kadane's: "max/min subarray sum/product" — running state that either extends or restarts
• HashMap / HashSet: "find pair with sum", "detect duplicate", "count frequencies" — O(1) lookup replaces O(n) scan
• Prefix/Suffix: "product/sum of everything except self" — two passes, each direction builds one half
• Palindrome Expand: "longest/count palindromic substrings" — try every center (2n-1 centers)
• Matrix: "set to zero", "spiral order", "rotate in-place" — boundary pointers or flag arrays
• Bit Manipulation: "without arithmetic operators", "count set bits", "XOR to find unique" — bit tricks

Interview Approach

1. For array problems: ask yourself if a running variable (min so far, max so far, current sum) solves it before reaching for sorting or extra space
2. For matrix in-place problems: identify if you can reuse the first row/column as storage, or if transpose + reverse achieves the rotation
3. For bit problems: know the three core tricks — n & (n-1) clears lowest bit, XOR cancels pairs, AND + left shift simulates carry

6 Main Patterns

Pattern 1: One-Pass Array (Kadane's Family)

Copy// Track a running state that resets when continuing would be worse than starting fresh
int curr = nums[0], best = nums[0];
for (int i = 1; i < nums.length; i++) {
    curr = Math.max(nums[i], curr + nums[i]);  // extend or restart
    best = Math.max(best, curr);
}

Pattern 2: HashMap / HashSet Lookup

Copy// O(1) lookup replaces O(n) search — store what you've seen as you go
Map<Integer, Integer> map = new HashMap<>();        // value → index
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);
}

Pattern 3: Prefix / Suffix Pass

Copy// Pass 1: build prefix into result[]; Pass 2: apply suffix in one variable
int[] result = new int[n];
result[0] = 1;
for (int i = 1; i < n; i++) {
    result[i] = result[i-1] * nums[i-1];  // prefix
}
int suffix = 1;
for (int i = n-1; i >= 0; i--) { result[i] *= suffix; suffix *= nums[i]; } // suffix

Pattern 4: Palindrome Expand Around Center

Copy// 2n-1 possible centers: each character (odd) and each gap (even)
private int expand(String s, int left, int right) {
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--; right++;
    }
    return right - left - 1; // palindrome length
}
// Call: expand(s, i, i) for odd, expand(s, i, i+1) for even

Pattern 5: Matrix In-Place

Copy// Rotate 90° clockwise = transpose + reverse each row
// Transpose: swap matrix[i][j] with matrix[j][i] for j > i
// Reverse rows: standard two-pointer swap within each row

Pattern 6: Bit Manipulation

Copyn & (n - 1)          // clear lowest set bit (count set bits, check power of 2)
a ^ b                // XOR: same bits cancel, different bits survive
a & b                // AND: 1 only where both are 1 (carry in bit addition)
(a & b) << 1         // carry bits in bit addition
n >> 1               // right shift = divide by 2 (used in Counting Bits: dp[n>>1])

General Templates

Bit Addition Template (Sum of Two Integers)

Copywhile (b != 0) {
    int carry = (a & b) << 1;
    a = a ^ b;      // sum without carry
    b = carry;      // carry becomes next b
}
return a;

Problem 1: Best Time to Buy and Sell Stock ⭐ MUST DO [B75-121]

Choose a day to buy and a later day to sell. Return the maximum profit. Return 0 if no profit is possible.

Example:

CopyInput:  [7,1,5,3,6,4]  →  5   (buy at 1, sell at 6)
Input:  [7,6,4,3,1]    →  0   (prices only fall)

Solution:

Copypublic int maxProfit(int[] prices) {
    int minPrice = Integer.MAX_VALUE, maxProfit = 0;
    for (int price : prices) {
        minPrice   = Math.min(minPrice, price);
        maxProfit  = Math.max(maxProfit, price - minPrice);
    }
    return maxProfit;
}

Complexity:

LC 122 — Unlimited transactions: Greedy: capture every upward step. Sell-before-buy is implicit — consecutive up-days (2-1)+(3-2) equal one holding (3-1), and you never hold through a down day.

Copypublic int maxProfitII(int[] prices) {
    int profit = 0;
    for (int i = 1; i < prices.length; i++) {
        if (prices[i] > prices[i-1]) {
            profit += prices[i] - prices[i-1];  // take every upward step
        }
    }
    return profit;
}

LC 714 — Unlimited with transaction fee: Same greedy but subtract fee on each sell. Two states: held (holding), cash (not holding).

Copypublic int maxProfitFee(int[] prices, int fee) {
    int held = -prices[0];   // profit while holding (paid to buy)
    int cash = 0;            // profit while not holding
    for (int i = 1; i < prices.length; i++) {
        held = Math.max(held, cash - prices[i]);         // keep holding or buy
        cash = Math.max(cash, held + prices[i] - fee);  // keep not holding or sell
    }
    return cash;
}

LC 309 — Unlimited with cooldown (must skip 1 day after selling): Three states: held (holding), sold (just sold — cooldown next), rest (not holding, free to buy).

Copypublic int maxProfitCooldown(int[] prices) {
    int held = Integer.MIN_VALUE;  // profit while holding a stock
    int sold = 0;                  // profit on day we just sold (next day is forced rest)
    int rest = 0;                  // profit while resting (can buy next day)
    for (int price : prices) {
        int prevHeld = held;
        int prevSold = sold;
        int prevRest = rest;
        held = Math.max(prevHeld, prevRest - price);  // keep holding, or buy (only from rest)
        sold = prevHeld + price;                       // sell what we held
        rest = Math.max(prevRest, prevSold);           // keep resting, or cooldown just elapsed
    }
    return Math.max(sold, rest);
}

LC 123 — At most 2 transactions: Four states cascade in one pass: buy1 → sell1 → buy2 → sell2. Each state funds the next.

Copypublic int maxProfitTwo(int[] prices) {
    int buy1  = Integer.MIN_VALUE, sell1 = 0;
    int buy2  = Integer.MIN_VALUE, sell2 = 0;
    for (int price : prices) {
        buy1  = Math.max(buy1,  -price);          // best profit after 1st buy
        sell1 = Math.max(sell1, buy1  + price);   // best profit after 1st sell
        buy2  = Math.max(buy2,  sell1 - price);   // 2nd buy funded by sell1
        sell2 = Math.max(sell2, buy2  + price);   // best profit after 2nd sell
    }
    return sell2;
}

LC 188 — At most k transactions: Generalises LC 123 to k buy/sell pairs. Short-circuits to greedy when k >= n/2 (more allowed trades than profitable days).

Copypublic int maxProfitK(int k, int[] prices) {
    int n = prices.length;
    if (k >= n / 2) {
        // effectively unlimited — use greedy
        int profit = 0;
        for (int i = 1; i < n; i++) {
            if (prices[i] > prices[i-1]) {
                profit += prices[i] - prices[i-1];
            }
        }
        return profit;
    }
    int[] buy  = new int[k + 1];
    int[] sell = new int[k + 1];
    Arrays.fill(buy, Integer.MIN_VALUE);
    for (int price : prices) {
        for (int j = 1; j <= k; j++) {
            buy[j]  = Math.max(buy[j],  sell[j-1] - price);  // buy on j-th transaction
            sell[j] = Math.max(sell[j], buy[j]    + price);  // sell on j-th transaction
        }
    }
    return sell[k];
}

How the variants relate:

Real World: Algorithmic trading systems compute the maximum profit window over historical price data before deploying a strategy. The same one-pass pattern applies to any "cheapest buy, best sell" optimisation: cloud spot-instance pricing (buy compute cheapest, release at peak), commodity procurement, or ad-bid optimisation.

Variations:

1. Maximum profit with cooldown (LC 309) — after selling you must wait one day; DP with three states: hold, sold, rest.
2. Maximum profit with transaction fee (LC 714) — pay a fixed fee per sell; same greedy but subtract fee each time you capture an upward step.

Interview Disguises:

• "Given hourly cloud spot-instance prices, find the cheapest time to start a batch job and the best time to stop it to minimise total cost." — max profit; cost replaces price, minimise replaces maximise.
• "Given an array of sensor readings, find the maximum increase from any earlier reading to any later reading." — same structure; the answer is the maximum difference where the larger comes after the smaller.

Problem 2: Contains Duplicate ⭐ MUST DO [B75-217]

Return true if any value appears at least twice in the array.

Example:

CopyInput:  [1,2,3,1]  →  true
Input:  [1,2,3,4]  →  false

Solution:

Copypublic boolean containsDuplicate(int[] nums) {
    Set<Integer> seen = new HashSet<>();
    for (int num : nums) {
        if (!seen.add(num)) {
            return true;    // add() returns false if already present
        }
    }
    return false;
}

Complexity:

Real World: Data deduplication pipelines check for repeated records before inserting into a database. Fraud detection systems flag the same transaction ID appearing more than once. Log aggregators deduplicate identical error messages within a time window before alerting.

Variations:

1. Contains duplicate within k distance (LC 219) — use a sliding HashSet of size k; add new element, remove element that fell out of window.
2. Contains duplicate within value range t (LC 220) — use a TreeSet to find the nearest element in O(log k) and check if the value difference is within t.

Interview Disguises:

• "A payment processor receives transaction IDs; flag any ID that has been submitted more than once in the same batch." — contains duplicate; transaction IDs are the values.
• "Verify that a list of generated UUIDs has no collisions." — same HashSet check; false means all unique, true means collision detected.

Problem 3: Valid Anagram ⭐ MUST DO [B75-242]

Return true if t is an anagram of s (same characters, same counts).

Example:

CopyInput:  s = "anagram",  t = "nagaram"  →  true
Input:  s = "rat",      t = "car"      →  false

Solution:

Copypublic boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }
    int[] count = new int[26];
    for (int i = 0; i < s.length(); i++) {
        count[s.charAt(i) - 'a']++;
        count[t.charAt(i) - 'a']--;
    }
    for (int c : count) {
        if (c != 0) return false;
    }
    return true;
}

Complexity:

Real World: Search engines normalise query terms before indexing — "listen" and "silent" map to the same canonical form. Spell checkers and autocomplete systems detect that a mistyped word is an anagram of a real word. Plagiarism detectors flag sentences whose words are rearranged.

Variations:

1. Unicode strings — replace int[26] with a HashMap<Character, Integer>; handles any character set.
2. Anagram of any substring (LC 438) — sliding window with a frequency array; find all start indices where a window of length p.length() is an anagram of p.

Interview Disguises:

• "Two configuration files list the same set of feature flags in different order — verify they are identical." — valid anagram where feature flag names are characters.
• "A shuffled deck of cards is claimed to be a full standard deck — verify without sorting." — frequency count both sequences and compare.

Problem 4: Number of 1 Bits ⭐ MUST DO [B75-191]

Return the number of set bits (1s) in the binary representation of n.

Example:

CopyInput:  n = 11  (binary: 1011)    →  3
Input:  n = 128 (binary: 10000000)  →  1

Key Insight:

• n & (n-1) clears the lowest set bit. Count how many times you can do this before n becomes 0.

Solution:

Copypublic int hammingWeight(int n) {
    int count = 0;
    while (n != 0) {
        n &= (n - 1);   // clear lowest set bit
        count++;
    }
    return count;
}

Complexity:

Real World: Network packet headers encode feature flags as bitmasks — counting set bits tells you how many features are active. CPU instruction sets include a dedicated POPCNT instruction for this; software implementations use n &= (n-1) for the same reason. Compression algorithms use bit counts to compute Hamming distances between codewords.

Variations:

1. Hamming distance (LC 461) — XOR the two numbers then count set bits; XOR isolates the bits that differ.
2. Power of two check — n > 0 && (n & (n-1)) == 0; a power of two has exactly one set bit so clearing it yields zero.

Interview Disguises:

• "Given a permission bitmask, return how many individual permissions are granted." — count set bits; each bit is a permission flag.
• "Two users have feature-flag bitmasks — how many features does each have enabled?" — popcount on each mask.

Problem 5: Counting Bits ⭐ MUST DO [B75-338]

Return an array where result[i] is the number of 1 bits in i, for all i from 0 to n.

Example:

CopyInput:  n = 5  →  [0,1,1,2,1,2]

Key Insight:

• dp[i] = dp[i >> 1] + (i & 1). Shifting right divides by 2 (drops the last bit); i & 1 adds 1 if that dropped bit was a 1. So every number's bit count is its half's count plus whether it's odd.

Solution:

Copypublic int[] countBits(int n) {
    int[] dp = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        dp[i] = dp[i >> 1] + (i & 1);  // dp[i/2] + is_i_odd
    }
    return dp;
}

Complexity:

Real World: Pre-computing a popcount lookup table is a standard optimisation in database engines and hash functions — build it once using this DP, then use O(1) lookups. Compiler backends use bit-count tables when generating SIMD instructions for population count.

Variations:

1. Sum of all bits from 0 to n — sum the output array; useful for computing total bit complexity across a range.
2. Numbers with exactly k set bits — filter the output array or generate them directly using bitmask enumeration.

Interview Disguises:

• "Pre-compute a table of how many 1-bits each byte value (0–255) contains, to be used as a lookup in a network packet parser." — counting bits for n=255; the DP approach fills the table in O(n).
• "For each integer from 0 to n, compute the number of on-pixels if that integer were displayed on a binary display grid." — identical; on-pixels = set bits.

Problem 6: Missing Number ⭐ MUST DO [B75-268]

Given an array containing n distinct numbers in range [0, n], return the one missing number.

Example:

CopyInput:  [3,0,1]              →  2
Input:  [9,6,4,2,3,5,7,0,1]  →  8

Key Insight:

• XOR every index (0 to n) and every value in the array. Each number that's present cancels itself (a ^ a = 0). The unpaired index — the missing number — survives.

Solution:

Copypublic int missingNumber(int[] nums) {
    int xor = nums.length;                      // start with n
    for (int i = 0; i < nums.length; i++) {
        xor ^= i ^ nums[i];                    // cancel each present pair
    }
    return xor;
}

Complexity:

Real World: Detecting gaps in sequential IDs is a common data quality check — order numbers, invoice IDs, and event sequence numbers should be contiguous. A missing ID means a record was dropped or skipped. The same XOR trick is used in distributed systems to verify that a replica received exactly the expected set of messages.

Variations:

1. Find the duplicate instead of missing — if one number is duplicated instead of missing, the same XOR of indices and values isolates it because the duplicate cancels twice while the missing one cancels once.
2. First missing positive (LC 41) — harder variant; values are not bounded by n, so XOR doesn't apply; use index-as-hash instead.

Interview Disguises:

• "A conveyor belt assigns sequential ticket numbers 1 to n. One ticket was lost — which number is missing from the scanned list?" — missing number; ticket numbers are the values.
• "Verify that a distributed job queue processed every task ID from 0 to n exactly once; report the missing task." — same XOR approach.

Problem 7: Reverse Bits ⭐ MUST DO [B75-190]

Reverse the bits of a 32-bit unsigned integer.

Example:

CopyInput:  00000010100101000001111010011100  →  00111001011110000010100101000000
        (43261596)                          (964176192)

Solution:

Copypublic int reverseBits(int n) {
    int result = 0;
    for (int i = 0; i < 32; i++) {
        result = (result << 1) | (n & 1);  // shift result left, append LSB of n
        n >>>= 1;                           // unsigned right shift to expose next bit
    }
    return result;
}

Complexity:

Real World: Network protocols transmit data in big-endian (most significant byte first) or little-endian order. Reversing bits corrects byte-order mismatches between hardware architectures. CRC checksum calculations and cryptographic hash functions use bit reversal as a building block.

Variations:

1. Reverse only k bits — mask off the top (32-k) bits, reverse the bottom k, then OR them back.
2. Palindrome in binary — reverse the bits and compare to the original; equal means palindrome.

Interview Disguises:

• "A legacy sensor encodes its reading with the least significant bit first. Convert it to standard big-endian format." — reverse bits; the sensor output is the input integer.
• "A hardware protocol sends 32-bit addresses in mirrored bit order — decode an incoming address." — same reversal; address bits are the input.

Problem 8: Maximum Subarray ⭐ MUST DO [B75-53]

Find the contiguous subarray with the largest sum.

Example:

CopyInput:  [-2,1,-3,4,-1,2,1,-5,4]  →  6   ([4,-1,2,1])
Input:  [1]                        →  1

Key Insight:

• At each element, decide: start a new subarray here, or extend the running subarray? If the running sum is negative, starting fresh is better. Update the global max at each step. This is Kadane's algorithm.

Solution:

Copypublic int maxSubArray(int[] nums) {
    int curr = nums[0], max = nums[0];
    for (int i = 1; i < nums.length; i++) {
        curr = Math.max(nums[i], curr + nums[i]);  // restart or extend
        max  = Math.max(max, curr);
    }
    return max;
}

Complexity:

Real World: Financial time-series analysis — find the best contiguous trading period by profit, revenue, or return. Signal processing — find the peak signal window within a noisy stream. A/B test analysis — find the contiguous cohort window with the highest conversion lift.

Variations:

1. Maximum circular subarray (LC 918) — total sum minus the minimum subarray gives the circular maximum; handle all-negative edge case separately.
2. Return the actual subarray — track start index when curr resets and update answer indices when a new max is found.

Interview Disguises:

• "Given daily net revenue changes, find the contiguous period with the highest total net revenue." — maximum subarray; daily changes are the array values.
• "A/B test logs show daily conversion deltas. Find the window of consecutive days with the highest cumulative lift." — Kadane's; deltas are the values.

Problem 9: Group Anagrams ⭐ MUST DO [B75-49]

Group strings that are anagrams of each other.

Example:

CopyInput:  ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Key Insight:

• Two strings are anagrams if and only if their sorted characters are identical. Use the sorted string as the HashMap key. All anagrams in the input map to the same key and get grouped together.

Solution:

Copypublic List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> map = new HashMap<>();
    for (String s : strs) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        String key = new String(chars);
        if (!map.containsKey(key)) {
            map.put(key, new ArrayList<>());
        }
        map.get(key).add(s);
    }
    return new ArrayList<>(map.values());
}

Complexity:

Real World: Search engines group query variants so "listen", "silent", and "enlist" all return the same results. Log aggregation systems cluster error messages that use the same words in a different order. Spam filters flag messages whose word bags match a known spam template.

Variations:

1. Frequency count key (O(nk) instead of O(nk log k)) — use a int[26] frequency array converted to a string as the key; avoids sorting each word.
2. Count groups of size exactly k — filter map.values() after building the group map.

Interview Disguises:

• "Cluster API endpoint paths that are permutations of each other so they can share a rate-limit bucket." — group anagrams where paths are the strings.
• "A chat moderation system needs to group messages that contain the same words in any order." — anagram grouping on word-sorted message tokens.

Problem 10: Product of Array Except Self ⭐ MUST DO [B75-238]

Return an array where result[i] is the product of all elements except nums[i]. Must run in O(n) without division.

Example:

CopyInput:  [1,2,3,4]      →  [24,12,8,6]
Input:  [-1,1,0,-3,3]  →  [0,0,9,0,0]

Key Insight:

• result[i] = (product of all elements left of i) × (product of all elements right of i). First pass fills result[] with prefix products left-to-right. Second pass multiplies in suffix products right-to-left using a single running variable — no extra array needed.

Solution:

Copypublic int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    result[0] = 1;
    for (int i = 1; i < n; i++) {
        result[i] = result[i-1] * nums[i-1];       // prefix product
    }

    int suffix = 1;
    for (int i = n-1; i >= 0; i--) {
        result[i] *= suffix;                        // apply suffix
        suffix *= nums[i];                          // grow suffix
    }
    return result;
}

Complexity:

Real World: Computing leave-one-out scores: each data point's score is the product (or sum) of all other points — used in cross-validation, anomaly detection, and influence analysis. Division is avoided because one zero would corrupt the entire result; the prefix/suffix approach handles zeros naturally.

Variations:

1. With division (handle zeros separately) — compute total product; divide for non-zero elements; for zeros, count zeros and handle specially. Simpler but fragile.
2. Sum version (trivial) — prefix sum array; result[i] = totalSum - nums[i]. The product version is harder and more commonly asked.

Interview Disguises:

• "Each team member's performance score should reflect the combined output of all other members — compute these scores without using division." — product except self; team members are array elements.
• "Given sensor calibration weights, compute each sensor's normalisation factor as the product of all other weights." — same structure; weights are the array values.

Problem 11: Maximum Product Subarray ⭐ MUST DO [B75-152]

Find the contiguous subarray with the largest product.

Example:

CopyInput:  [2,3,-2,4]   →  6   ([2,3])
Input:  [-2,0,-1]    →  0

Key Insight:

• Unlike max subarray sum, a large negative product can become the best if multiplied by another negative. Track both the current maximum and minimum product. At each element, new max = max(nums[i], prev_max × nums[i], prev_min × nums[i]) — and similarly for min.

Solution:

Copypublic int maxProduct(int[] nums) {
    int max = nums[0], min = nums[0], result = nums[0];
    for (int i = 1; i < nums.length; i++) {
        int tmp = max;
        max    = Math.max(nums[i], Math.max(max * nums[i], min * nums[i]));
        min    = Math.min(nums[i], Math.min(tmp * nums[i], min * nums[i]));
        result = Math.max(result, max);
    }
    return result;
}

Complexity:

Real World: Signal gain optimisation where amplifier stages can invert the signal — a negative multiplier flips the sign but a pair of negatives restores it. Financial risk: a sequence of loss ratios (values < 1) multiplied together compounds, but a second negative period can produce an unexpected gain. Finding the maximum product window identifies the best compound-growth period.

Variations:

1. Maximum product of exactly k elements — sliding window of fixed size k; maintain running product, divide out the leaving element (handle zeros separately).
2. Maximum product after removing one element — try removing each element; the answer is max(product of left prefix × product of right suffix) for each index.

Interview Disguises:

• "A manufacturing pipeline has stages with efficiency multipliers; some stages degrade quality (multiplier < 1). Find the contiguous run of stages with the highest combined multiplier." — max product subarray; efficiency multipliers are the values.
• "Given a sequence of investment return ratios (e.g. 0.9 for -10%, 1.2 for +20%), find the best consecutive holding period by total return." — max product; ratios are the values.

Problem 12: Longest Palindromic Substring ⭐ MUST DO [B75-5]

Return the longest palindromic substring.

Example:

CopyInput:  "babad"  →  "bab"  (or "aba")
Input:  "cbbd"   →  "bb"

Key Insight:

• Every palindrome has a center. Try all 2n-1 possible centers (n single characters for odd-length, n-1 gaps between characters for even-length). Expand outward while characters match. Track the longest found.

Solution:

Copypublic String longestPalindrome(String s) {
    int start = 0, maxLen = 1;
    for (int i = 0; i < s.length(); i++) {
        int len = Math.max(expand(s, i, i), expand(s, i, i + 1));
        if (len > maxLen) {
            maxLen = len;
            start  = i - (len - 1) / 2;
        }
    }
    return s.substring(start, start + maxLen);
}

private int expand(String s, int left, int right) {
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--; right++;
    }
    return right - left - 1;
}

Complexity:

Real World: DNA sequence analysis — palindromic sequences are recognition sites for restriction enzymes (the sequence reads the same on both strands in 5'→3' direction). Finding the longest palindromic region helps locate cut sites. String compression algorithms also look for palindromic substrings as redundancy candidates.

Variations:

1. Manacher's algorithm O(n) — uses previously computed palindrome radii to skip redundant expansions; rarely asked to implement from scratch but worth knowing exists.
2. Longest palindromic subsequence (LC 516) — characters don't need to be contiguous; DP solution, different from this problem.

Interview Disguises:

• "Find the longest mirrored segment in a user-entered password — it may indicate a weak pattern." — longest palindromic substring; the password is the input string.
• "A genomics tool needs to locate the longest restriction enzyme recognition site in a DNA strand." — same expansion logic; the strand is the string.

Problem 13: Palindromic Substrings ⭐ MUST DO [B75-647]

Count the number of palindromic substrings in s.

Example:

CopyInput:  "abc"  →  3   ("a","b","c")
Input:  "aaa"  →  6   ("a","a","a","aa","aa","aaa")

Key Insight:

• Same expand-around-center as Longest Palindromic Substring, but instead of tracking the longest, count every palindrome found during each expansion (each successful expansion step = one palindrome).

Solution:

Copypublic int countSubstrings(String s) {
    int count = 0;
    for (int i = 0; i < s.length(); i++) {
        count += expand(s, i, i);       // odd-length palindromes
        count += expand(s, i, i + 1);  // even-length palindromes
    }
    return count;
}

private int expand(String s, int left, int right) {
    int count = 0;
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--; right++; count++;
    }
    return count;
}

Complexity:

Real World: Same DNA palindrome analysis — counting all restriction sites rather than just the longest. Quality control in transmitted strings: count all substrings that read the same in both directions to identify redundancy or error patterns.

Variations:

1. Count palindromes of length ≥ k — same expansion, skip counting if right - left - 1 < k.
2. Minimum cuts for palindrome partitioning (LC 132) — harder DP follow-up; uses the same expansion table as a subroutine.

Interview Disguises:

• "Count how many substrings of a barcode scan identically forwards and backwards — a high count may indicate a corrupted scan." — palindromic substrings count.
• "In a protein sequence, count all segments that are their own reverse complement — these are potential hairpin structures." — same expansion logic on a biological string.

Problem 14: Set Matrix Zeroes ⭐ MUST DO [B75-73]

If an element is 0, set its entire row and column to 0. Do it in-place.

Example:

CopyInput:  [[1,1,1],[1,0,1],[1,1,1]]  →  [[1,0,1],[0,0,0],[1,0,1]]

Key Insight:

• Use the first row and first column as flag arrays — if matrix[i][j] == 0, mark matrix[i][0] = 0 and matrix[0][j] = 0. But since the first row and column are themselves used as flags, record separately whether they need to be zeroed before using them as markers.

Solution:

Copypublic void setZeroes(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    boolean firstRowZero = false, firstColZero = false;

    for (int j = 0; j < n; j++) {
        if (matrix[0][j] == 0) firstRowZero = true;
    }
    for (int i = 0; i < m; i++) {
        if (matrix[i][0] == 0) firstColZero = true;
    }

    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (matrix[i][j] == 0) {
                matrix[i][0] = 0;   // mark row
                matrix[0][j] = 0;   // mark col
            }
        }
    }

    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                matrix[i][j] = 0;
            }
        }
    }

    if (firstRowZero) {
        Arrays.fill(matrix[0], 0);
    }
    if (firstColZero) {
        for (int i = 0; i < m; i++) matrix[i][0] = 0;
    }
}

Complexity:

Real World: Spreadsheet software propagates "null" or "unknown" values — if any cell in a row or column is unknown, the whole row and column should be marked unknown. Database NULL propagation rules follow the same logic: a NULL in any operand of a multiplication zeroes the result row and column in a cross-product.

Variations:

1. Mark with -1 instead of 0 — same algorithm; just replace the zero sentinel with -1 and use a different flag value.
2. Sparse matrix — if very few cells are zero, store the zero positions in a small list instead of using the first row/col as flags; avoids the tricky first-row/col bookkeeping.

Interview Disguises:

• "A table of sensor readings: if any sensor reports an invalid reading (0), mark all readings in its row and column as invalid." — set matrix zeroes; invalid readings are the zeros.
• "In a user-permission matrix, if any cell indicates a blocked permission, propagate the block to all permissions in that row and column." — same in-place flag propagation.

Problem 15: Spiral Matrix ⭐ MUST DO [B75-54]

Return all elements of the matrix in spiral order.

Example:

CopyInput:  [[1,2,3],[4,5,6],[7,8,9]]  →  [1,2,3,6,9,8,7,4,5]

Key Insight:

• Maintain four boundaries (top, bottom, left, right). Each iteration: traverse top row left→right, advance top; right column top→bottom, advance right; bottom row right→left (if top ≤ bottom), advance bottom; left column bottom→top (if left ≤ right), advance left. Check bounds before each inner direction to handle non-square matrices.

Solution:

Copypublic List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> result = new ArrayList<>();
    int top = 0, bottom = matrix.length - 1;
    int left = 0, right = matrix[0].length - 1;

    while (top <= bottom && left <= right) {
        for (int j = left; j <= right; j++) {
            result.add(matrix[top][j]);
        }
        top++;
        for (int i = top; i <= bottom; i++) {
            result.add(matrix[i][right]);
        }
        right--;
        if (top <= bottom) {
            for (int j = right; j >= left; j--) {
                result.add(matrix[bottom][j]);
            }
            bottom--;
        }
        if (left <= right) {
            for (int i = bottom; i >= top; i--) {
                result.add(matrix[i][left]);
            }
            left++;
        }
    }
    return result;
}

Complexity:

Real World: Image processing reads pixels in spiral order for certain compression codecs (e.g. JPEG block scanning). Cache-oblivious matrix algorithms access memory in spiral patterns to improve locality. Robotic path planning visits a bounded grid from the outside in to ensure full coverage.

Variations:

1. Spiral Matrix II — fill instead of read (LC 59) — same boundary-shrink logic but write values 1..n² into the matrix instead of reading them out.
2. Diagonal traversal (LC 498) — alternating diagonal directions; different traversal pattern but same boundary-tracking idea.

Interview Disguises:

• "A robot must clean a rectangular room by vacuuming the perimeter first, then spiralling inward. Return the order of cells visited." — spiral matrix; cells are matrix elements.
• "Print the layers of a 2D grid representing a building floor plan from outermost to innermost." — spiral order traversal.

Problem 16: Rotate Image ⭐ MUST DO [B75-48]

Rotate an n×n matrix 90° clockwise in-place.

Example:

CopyInput:  [[1,2,3],[4,5,6],[7,8,9]]  →  [[7,4,1],[8,5,2],[9,6,3]]

Key Insight:

• Rotating 90° clockwise = transpose (flip along the main diagonal) + reverse each row. Transpose swaps matrix[i][j] with matrix[j][i] for j > i only (to avoid double-swapping). Both operations are done in-place with no extra space.

Solution:

Copypublic void rotate(int[][] matrix) {
    int n = matrix.length;
    // Transpose
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int tmp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = tmp;
        }
    }
    // Reverse each row
    for (int i = 0; i < n; i++) {
        int l = 0, r = n - 1;
        while (l < r) {
            int tmp = matrix[i][l];
            matrix[i][l] = matrix[i][r];
            l++;
            matrix[i][r] = tmp;
            r--;
        }
    }
}

Complexity:

Real World: Game engines rotate sprite tiles and map grids 90° when the player changes orientation — done in-place to avoid allocating a new frame buffer. Image processing pipelines (EXIF orientation correction) apply the same transpose-then-reverse sequence on pixel arrays.

Variations:

1. 90° counter-clockwise — transpose then reverse each column (or reverse each row then transpose).
2. 180° rotation — reverse the entire matrix row-by-row then reverse each row, or apply two 90° clockwise rotations.

Interview Disguises:

• "A map tile engine needs to rotate a terrain grid 90° clockwise when the user rotates the device — do it without allocating a new grid." — rotate image; terrain values are matrix elements.
• "Rotate a Sudoku board 90° clockwise as part of a puzzle generation step." — same in-place rotation; Sudoku grid is the matrix.

Problem 17: Sum of Two Integers ⭐ MUST DO [B75-371]

Calculate the sum of two integers without using + or -.

Example:

CopyInput:  a = 1, b = 2  →  3
Input:  a = 2, b = 3  →  5

Key Insight:

• XOR of two numbers gives the sum bits without any carry. AND of two numbers shifted left by 1 gives the carry bits. Repeat — add the carry into the sum — until no carry remains.

Solution:

Copypublic int getSum(int a, int b) {
    while (b != 0) {
        int carry = (a & b) << 1;  // carry bits
        a = a ^ b;                 // sum without carry
        b = carry;
    }
    return a;
}

Complexity:

Real World: Low-level arithmetic in embedded systems and hardware description languages where the + operator may not be available or is implemented in terms of bitwise gates. ALU design: a full adder is constructed from XOR (sum) and AND (carry) gates, exactly this algorithm repeated at each bit position.

Variations:

1. Subtract without - — negate b using two's complement (~b + 1 using the same add-without-plus), then add.
2. Multiply without * — repeated addition using bit shifts; shift a left and add when the corresponding bit of b is set.

Interview Disguises:

• "Implement addition for a processor that has only bitwise AND, OR, XOR, and shift instructions." — sum of two integers; the constraint is the whole point.
• "Design a 4-bit software ALU that supports addition without using Java's + operator." — same carry-propagation logic applied to 4 bits.

Problem 18: Longest Consecutive Sequence ⭐ MUST DO [B75-128]

Given an unsorted array, return the length of the longest consecutive elements sequence. Must run in O(n).

Example:

CopyInput:  [100, 4, 200, 1, 3, 2]
Output: 4   (sequence 1, 2, 3, 4)

Input:  [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
Output: 9

Key Insight:

• Add all numbers to a HashSet for O(1) lookup. A number is the start of a sequence only if n - 1 is not in the set. From each start, count consecutive numbers by checking n + 1, n + 2, ... — each number is visited at most twice total across all sequences.

Solution:

Copypublic int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int n : nums) {
        set.add(n);
    }

    int longest = 0;
    for (int n : set) {
        if (!set.contains(n - 1)) {     // only start from sequence beginnings
            int length = 1;
            while (set.contains(n + length)) {
                length++;
            }
            longest = Math.max(longest, length);
        }
    }
    return longest;
}

Complexity:

Real World: Detecting gaps in sequential event logs — order numbers, invoice IDs, and packet sequence numbers should be contiguous. A long consecutive run in user IDs may indicate a bot sweep registering accounts in bulk. Network diagnostics use the same pattern to find the longest uninterrupted packet sequence in a capture.

Variations:

1. Return the actual sequence — track the starting number and length when a new maximum is found; reconstruct by iterating from start to start+length.
2. Longest consecutive path in a binary tree (LC 298) — DFS variant; consecutive means parent value + 1 equals child value.

Interview Disguises:

• "Given a list of user IDs that signed up today, find the longest run of consecutive IDs — a long run may indicate automated registration." — longest consecutive sequence; IDs are the values.
• "Given packet sequence numbers received so far, find the longest contiguous run with no gaps to determine the reliable delivery window." — same HashSet start-detection logic.

Quick Reference Table

When to Use Each Pattern

HashMap / HashSet

• Need O(1) lookup to answer "have I seen X before?" or "does complement exist?"
• Frequency counting: build the map in one pass, query in another
• Grouping: sorted characters or frequency signature as map key

HashSet / Sequential Scan

• Load all values into a HashSet first for O(1) membership checks
• Find the start of a sequence by checking that the predecessor is absent from the set
• Scan forward from each sequence start — each element is processed at most twice across all sequences, giving O(n) total

One-Pass / Kadane's

• Running min/max or running sum that either extends the current window or restarts
• Kadane's: curr = max(nums[i], curr + nums[i]) — prefer restarting if the running sum is negative
• For max product: track both max and min because a large negative flips sign

Prefix / Suffix

• result[i] depends on the product/sum of elements to its left AND its right
• First pass fills prefix into result left-to-right; second pass multiplies in suffix using a running variable right-to-left

Palindrome Expand

• 2n-1 possible centers; try both single-char (odd) and gap (even) for each position
• Expand helper returns length (for longest) or count (for counting)
• Start position from length: start = center - (len-1)/2

Matrix

• Set Matrix Zeroes: first row/column as markers; record their own zero status beforehand
• Spiral: four boundary pointers shrink inward; check top ≤ bottom and left ≤ right before each direction
• Rotate 90° clockwise: transpose (swap [i][j] and [j][i] for j > i) then reverse each row

Bit Manipulation

• n & (n-1): clears lowest set bit — count set bits, detect power of 2
• XOR: cancels duplicate pairs — find missing/unique number
• AND + left shift: carry in bit addition — sum without arithmetic operators
• Right shift (>>1): halve a number — use with AND to check last bit

Common Mistakes to Avoid

Array Mistakes

1. Kadane's wrong initialization — initialize curr and max to nums[0], not 0; an array of all negatives has a max that is negative, not 0
2. Max Product Subarray: not saving prev_max before updating — save tmp = max before computing new max, because the new min formula needs the old max

Matrix Mistakes

3. Set Matrix Zeroes: zeroing first row/col before using them as flags — first scan and record firstRowZero/firstColZero, then use them as markers, then zero them last
4. Spiral Matrix: extra elements on non-square matrices — always guard the bottom and left passes with if (top <= bottom) and if (left <= right) respectively

Bit Mistakes

5. Counting Bits: using n/2 instead of n>>1 — both work for non-negative, but right shift is the conventional idiom; don't confuse n>>1 (integer division) with n-1
6. Reverse Bits: signed right shift — Java's >> is signed (fills with sign bit); use >>> for unsigned right shift when shifting the input n to avoid propagating the sign bit