Palindrome Pairs

📋

Problem

Imagine a search engine that suggests pairs of words which, when combined, form palindromes - a fun feature for word games or linguistic puzzles.

Given a list of unique words, find all pairs of distinct indices (i, j) such that the concatenation of words[i] + words[j] is a palindrome. Return all such pairs as a list of lists.

1 ≤ n ≤ 10^5 (number of words)1 ≤ length of each word ≤ 300All words consist of lowercase English lettersWords are unique

Edge cases: Empty string present → pairs with any palindrome wordSingle character words → always palindrome pairs with themselves reversedWords that are already palindromes → can form pairs with empty string

</>

IDE

def palindromePairs(words: list[str]) -> list[list[int]]:public List<List<Integer>> palindromePairs(List<String> words)vector<vector<int>> palindromePairs(vector<string> &words)function palindromePairs(words)

def palindromePairs(words):
    # Write your solution here
    pass

class Solution {
    public List<List<Integer>> palindromePairs(List<String> words) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
#include <string>
using namespace std;

vector<vector<int>> palindromePairs(vector<string> &words) {
    // Write your solution here
    return {};
}

function palindromePairs(words) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Missing pairs involving empty string and palindrome wordsNot handling empty string special case for palindrome pairs✅ Add explicit checks to pair empty string with all palindrome words at different indices

Wrong: Pairs with same index (e.g. [0,0]) includedNot enforcing distinct indices condition✅ Add condition to skip pairs where i == j

Wrong: Only pairs with fully reversed words found, missing partial palindrome pairsGreedy approach checking only full reversed words✅ Check palindrome prefixes and suffixes for partial matches to find all pairs

Wrong: Fails on large input due to timeoutBrute force O(n^2*k) approach used✅ Implement hash map or trie-based approach with O(n*k^2) complexity

Wrong: Misses pairs involving duplicate wordsMapping words to single index instead of all indices✅ Map words to all their indices and check all pairs

✓

Test Cases

Focus on handling empty strings and single word inputs correctly.

Watch out for greedy traps and ensure palindrome prefix/suffix checks.

Optimize your solution to avoid quadratic time complexity.

t1_01basic

Input["abcd","dcba","lls","s","sssll"]

Expected[[0,1],[1,0],[3,2],[2,4]]

⏱ Performance - must finish in 2000ms

Pairs: 'abcd' + 'dcba' = 'abcddcba' palindrome, 'dcba' + 'abcd' palindrome, 's' + 'lls' palindrome, 'lls' + 'sssll' palindrome.

💡 Check pairs of words by concatenating and verifying palindrome property.

💡 Use a hash map to find reversed words quickly and check palindrome prefixes/suffixes.

💡 Store indices of words and check for palindrome suffixes/prefixes to form pairs.

Why it failed: Basic case failed - likely missed checking both prefix and suffix palindrome conditions or reversed word lookups. Fix by verifying palindrome on both sides and using a map of reversed words.

✓ Core palindrome pair detection logic is correct.

t1_02basic

Input["bat","tab","cat"]

Expected[[0,1],[1,0]]

⏱ Performance - must finish in 2000ms

'bat' + 'tab' and 'tab' + 'bat' form palindromes; 'cat' forms no palindrome pairs.

💡 Try reversing words and checking if reversed exists in the list.

💡 Check if concatenation of word and reversed word forms palindrome pairs.

💡 Use a dictionary to map reversed words to indices and verify pairs.

Why it failed: Failed to find pairs where reversed words form palindromes. Fix by mapping reversed words and checking pairs correctly.

✓ Correctly identified palindrome pairs from reversed words.

t2_01edge

Input[""]

Expected[]

⏱ Performance - must finish in 2000ms

Single empty string alone cannot form pairs with distinct indices.

💡 Consider how empty strings interact with palindrome pairs.

💡 Empty string pairs with any palindrome word except itself.

💡 Check for empty string presence and pair with palindrome words at different indices.

Why it failed: Missed handling empty string edge case; empty string pairs with palindrome words at different indices. Fix by adding special case for empty string.

✓ Properly handles empty string edge case.

t2_02edge

Input["a"]

Expected[]

⏱ Performance - must finish in 2000ms

Single character word alone cannot form pairs with distinct indices.

💡 Single character words are palindromes themselves.

💡 Pairs require distinct indices; single element means no pairs.

💡 Return empty list when only one word is present.

Why it failed: Incorrectly returned pairs for single element input. Fix by ensuring pairs have distinct indices.

✓ Correctly returns no pairs for single element input.

t2_03edge

Input["a",""]

Expected[[0,1],[1,0]]

⏱ Performance - must finish in 2000ms

Empty string pairs with palindrome 'a' in both orders.

💡 Empty string pairs with any palindrome word.

💡 Check pairs where one word is empty and the other is palindrome.

💡 Add pairs (empty, palindrome) and (palindrome, empty) with distinct indices.

Why it failed: Failed to pair empty string with palindrome words. Fix by adding pairs involving empty string and palindrome words.

✓ Correctly pairs empty string with palindrome words.

t3_01corner

Input["abcd","dcba","lls","s","sssll","lls"]

Expected[[0,1],[1,0],[3,2],[2,4],[5,4]]

⏱ Performance - must finish in 2000ms

Detects duplicates and pairs correctly; 'lls' repeated at index 5 pairs with 'sssll' at 4.

💡 Check how duplicates affect palindrome pairs.

💡 Ensure indices are distinct and all pairs are found even with duplicates.

💡 Use a map from word to all indices to handle duplicates properly.

Why it failed: Missed pairs involving duplicate words or failed to handle multiple indices. Fix by mapping words to all indices and checking all pairs.

✓ Correctly handles duplicates and finds all palindrome pairs.

t3_02corner

Input["a","abc","cba"]

Expected[[1,2],[2,1]]

⏱ Performance - must finish in 2000ms

'abc' + 'cba' and 'cba' + 'abc' form palindromes; single character 'a' does not form pairs.

💡 Beware of greedy approaches that only check reversed full words.

💡 Check palindrome prefixes and suffixes for partial matches.

💡 Verify all splits of words for palindrome suffix/prefix to find pairs.

Why it failed: Greedy approach failed by only checking full reversed words. Fix by checking palindrome prefixes and suffixes for partial matches.

✓ Correctly finds pairs using palindrome prefix/suffix checks.

t3_03corner

Input["a","aa","aaa"]

Expected[[0,1],[1,0],[0,2],[2,0],[1,2],[2,1]]

⏱ Performance - must finish in 2000ms

Tests confusion between 0/1 knapsack style and unbounded; all pairs of palindromic words form pairs.

💡 Check that pairs are distinct indices, no reuse of same index twice.

💡 Avoid counting pairs multiple times or missing pairs due to index reuse.

💡 Ensure pairs (i,j) with i != j are included for all palindrome combinations.

Why it failed: Confused 0/1 constraint by allowing same index pairs or missing pairs. Fix by enforcing i != j and checking all pairs.

✓ Correctly handles all palindrome pairs with distinct indices.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this"}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100000 with max word length 300; brute force O(n^2*k) will TLE; efficient O(n*k^2) or trie-based needed.

💡 Brute force O(n^2*k) is too slow for large n.

💡 Use hash map or trie with palindrome suffix tracking for O(n*k^2).

💡 Optimize palindrome checks and avoid redundant computations.

Why it failed: TLE due to brute force O(n^2*k) complexity. Fix by implementing hash map or trie-based palindrome pair detection.

✓ Efficient O(n*k^2) or better complexity confirmed.

Practice

1. You are given a list of envelopes, each with a width and height. You want to find the maximum number of envelopes you can nest inside each other such that each envelope fits strictly inside the next one by both width and height. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy approach by sorting envelopes by width and picking the tallest envelope at each step.

B. Sort envelopes by width ascending and height descending, then find the Longest Increasing Subsequence (LIS) on heights using binary search.

C. Dynamic programming with a 2D table tracking all pairs of envelopes to find the longest chain.

D. Use a graph and find the longest path by topological sorting.

Solution

1. Step 1: Understand problem constraints

   The problem requires strict increasing order in both width and height for nesting envelopes.

2. Step 2: Identify optimal approach

   Sorting by width ascending and height descending ensures envelopes with the same width do not interfere. Then LIS on heights finds the longest chain efficiently.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sorting + LIS with binary search is the known optimal approach [OK]

Hint: Sort width asc, height desc, then LIS on heights [OK]

Common Mistakes:

• Using greedy picking tallest envelope only
• Applying LIS on widths instead of heights
• Using DP without sorting properly

2. Given the following Python code snippet implementing the merge step of the skyline problem, and the input skylines left = [[1, 3], [5, 0]] and right = [[2, 4], [6, 0]], what is the value of the variable merged after the while loop completes (before extending remaining points)?

easy

A. [[1, 3], [2, 4], [5, 0], [6, 0]]

B. [[1, 3], [2, 4]]

C. [[1, 3], [2, 4], [5, 0]]

D. [[1, 3], [2, 4], [5, 0], [6, 0], [7, 0]]

Solution

1. Step 1: Trace first iteration

   left[0] = [1,3], right[0] = [2,4]. Since 1 < 2, x=1, h1=3, h2=0, maxH=3 -> merged = [[1,3]]

2. Step 2: Trace second iteration

   left[1] = [5,0], right[0] = [2,4]. Since 2 < 5, x=2, h2=4, h1=3 (from previous), maxH=4 -> merged = [[1,3],[2,4]]

3. Step 3: Trace third iteration

   left[1] = [5,0], right[1] = [6,0]. Since 5 < 6, x=5, h1=0, h2=4 (previous), maxH=4 -> merged = [[1,3],[2,4],[5,0]]

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Correctly merged points before extending remaining [OK]

Hint: Trace pointer increments carefully to avoid off-by-one errors [OK]

Common Mistakes:

• Forgetting to update h1 or h2 correctly
• Appending points with same height consecutively
• Misaligning indices causing skipped points

3. Consider the following buggy code snippet for the optimal median of two sorted arrays. Which line contains the subtle bug that can cause incorrect median calculation or runtime error?

medium

A. Line 10: max_left_nums1 = float('-inf') if i == 0 else nums1[i - 1]

B. Line 7: i = (low + high) // 2

C. Line 17: elif max_left_nums1 > min_right_nums2:

D. Line 2: if len(nums1) < len(nums2): nums1, nums2 = nums2, nums1

Solution

1. Step 1: Check array swap condition

   The code swaps arrays only if len(nums1) < len(nums2), which is incorrect. It should swap if nums1 is larger to ensure binary search on smaller array.

2. Step 2: Consequences of wrong swap

   Without correct swap, binary search range can be large, causing inefficiency or index errors.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Swap condition reversed causes subtle bugs [OK]

Hint: Swap arrays so binary search is on smaller one [OK]

Common Mistakes:

• Swapping arrays incorrectly or not at all
• Off-by-one errors in partition indices
• Incorrect median calculation for odd/even lengths

4. What is the time complexity of the optimal two-pointer approach for finding the smallest range covering k lists, where n is the total number of elements across all lists and k is the number of lists?

medium

A. O(n * k) due to scanning each element for each list

B. O(n^2) since the two-pointer window can move over all pairs

C. O(n) as the two-pointer technique scans the merged array once

D. O(n log n) because of sorting the merged array of all elements

Solution

1. Step 1: Identify main operations

   Merging all elements takes O(n), sorting merged array takes O(n log n).

2. Step 2: Analyze two-pointer sliding window

   Two pointers scan merged array linearly, O(n) time.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sorting dominates, so total time is O(n log n) [OK]

Hint: Sorting merged array dominates time complexity [OK]

Common Mistakes:

• Assuming two-pointer is O(n^2)
• Ignoring sorting cost
• Confusing k factor in complexity

5. Consider the following buggy implementation of the two-pointer approach for trapping rain water. Which line contains the subtle bug that can cause incorrect trapped water calculation?

medium

A. Line 7: if height[left] < height[right]:

B. Line 15: if height[right] >= right_max:

C. Line 17: water += right_max - height[right]

D. Line 9: if height[left] > left_max:

Solution

1. Step 1: Compare condition for updating left_max

   The original buggy code used '>' instead of '>=' which causes left_max not to update when height[left] equals left_max.

2. Step 2: Effect of bug

   When height[left] == left_max, water is incorrectly added (left_max - height[left] = 0), which is harmless but logically incorrect and can cause issues in some cases.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Using '>=' ensures correct max update and prevents unnecessary water addition [OK]

Hint: Use '>=' when updating max heights to avoid underestimation [OK]

Common Mistakes:

• Using '>' instead of '>=' for max updates
• Incorrect pointer movement
• Adding water without checking max heights