Leetcode: 319. Bulb Switcher

There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb. Find how many bulbs are on after n rounds.

Example:

Given n = 3. 

At first, the three bulbs are [off, off, off].
After first round, the three bulbs are [on, on, on].
After second round, the three bulbs are [on, off, on].
After third round, the three bulbs are [on, off, off]. 

So you should return 1, because there is only one bulb is on.

Code (Java):

public class Solution {
    public int bulbSwitch(int n) {
        return (int) Math.sqrt(n);
    }
}

Leetcode: 320. Generalized Abbreviation

Write a function to generate the generalized abbreviations of a word.

Example:

Given word = "word", return the following list (order does not matter):

["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]

Understand the problem:
A classic dfs + backtracking problem. A trick here is if we've already abbrivate part of a word, we must jump at least a character.

Code (Java):

public class Solution {
    public List<String> generateAbbreviations(String word) {
        List<String> result = new ArrayList<>();

        result.add(word);
        generateHelper(0, word, result);
        
        return result;
    }
    
    private void generateHelper(int start, String s, List<String> result) {
        if (start >= s.length()) {
            return;
        }
        
        for (int i = start; i < s.length(); i++) {
            for (int j = 1; i + j <= s.length(); j++) {
                String num = Integer.toString(j);
                String abbr = s.substring(0, i) + num + s.substring(i + j);
                result.add(abbr);
                generateHelper(i + 1 + num.length(), abbr, result); // skip 1b
            }
        }
    }
}

Leetcode: 321. Create Maximum Number

Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits. You should try to optimize your time and space complexity.

Example 1:

nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
return [9, 8, 6, 5, 3]

Example 2:

nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
return [6, 7, 6, 0, 4]

Example 3:

nums1 = [3, 9]
nums2 = [8, 9]
k = 3
return [9, 8, 9]

Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

Solution:
First find out the maximum number for each array, and then merge it into a global maximal one. 

Code (Java):

public class Solution {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int[] result = new int[k];
        int n1 = nums1.length;
        int n2 = nums2.length;
        
        // step 1: find the largest number from each array, and merge into one
        for (int i = Math.max(0, k - n2); i <= Math.min(n1, k); i++) {
            int[] list1 = findMax(nums1, i);
            int[] list2 = findMax(nums2, k - i);
            
            // then merge into one
            int[] curr = merge(list1, list2);
            
            if (greater(curr, 0, result, 0)) {
                result = curr;
            }
        }
        
        return result;
    }
    
    private int[] findMax(int[] nums, int k) {
        int[] result = new int[k];
        
        int n = nums.length;
        int len = 0;
        for (int i = 0; i < n; i++) {
            while (len > 0 && len + n - i > k && nums[i] > result[len - 1]) {
                len--;
            }
            
            if (len < k) {
                result[len] = nums[i];
                len++;
            }
        }
        
        return result;
    }
    
    private int[] merge(int[] list1, int[] list2) {
        int n1 = list1.length;
        int n2 = list2.length;
        
        int[] result = new int[n1 + n2];
        
        int i = 0; 
        int j = 0;
        int k = 0;
        
        while (k < n1 + n2) {
            if (greater(list1, i, list2, j)) {
                result[k++] = list1[i++];
            } else {
                result[k++] = list2[j++];
            }
        }
        
        return result;
    }
    
    private boolean greater(int[] list1, int pos1, int[] list2, int pos2) {
        int n1 = list1.length;
        int n2 = list2.length;
        
        while (pos1 < n1 && pos2 < n2 && list1[pos1] == list2[pos2]) {
            pos1++;
            pos2++;
        }
        
        if (pos2 == n2) {
            return true;
        }
        
        if (pos1 < n1 && list1[pos1] > list2[pos2]) {
            return true;
        }
        
        return false;
    }
}

Leetcode: 327. Count of Range Sum

Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive.
Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j (i ≤ j), inclusive.

Note:
A naive algorithm of O(n2) is trivial. You MUST do better than that.

Example:
Given nums = [-2, 5, -1], lower = -2, upper = 2,
Return 3.
The three ranges are : [0, 0], [2, 2], [0, 2] and their respective sums are: -2, -1, 2.

Solution 1: Use Segment Tree

Solution 2: Use Binary Search Tree

Leetcode: 325. Maximum Size Subarray Sum Equals k

Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn't one, return 0 instead.

Example 1:

Given nums = [1, -1, 5, -2, 3], k = 3,
return 4. (because the subarray [1, -1, 5, -2] sums to 3 and is the longest)

Example 2:

Given nums = [-2, -1, 2, 1], k = 1,
return 2. (because the subarray [-1, 2] sums to 1 and is the longest)

Follow Up:
Can you do it in O(n) time?

Solution:
The idea of the problem is to check where there is a range from i to j, inclusive, so that its sum equals to k, and the length of the range is the maximum. 

So we can naturally think of this question as a range summary problem, and we need to calculate the prefix sum of the array first. So the sum(i, j) = presum[j] - presum[i - 1] = k

In order to achieve the O(n) time, we can leverage the same idea of the "Two Sum" problem by using a hash map. So we store the presum[i - 1] + k into the map, and check if presum[j] is in the map for each iteration. Note that we can do this in one-pass of loop iteration because for each j, i - 1 must be in the position above j. 

Code (Java):

public class Solution {
    public int maxSubArrayLen(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        // step 1: calculate the prefix sum for all numbers of the nums array
        int n = nums.length;
        int[] preSum = new int[n + 1];
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            preSum[i + 1] = sum;
        }
        
        // step 2: put the preSum + target into a map
        int max = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int j = 0; j < preSum.length; j++) {
            if (map.containsKey(preSum[j])) {
                max = Math.max(max, j - map.get(preSum[j]));
            }
            
            if (!map.containsKey(preSum[j] + k)) {
                map.put(preSum[j] + k, j);
            }
        }
        
        
        return max;
    }
}

Leetcode: 328. Odd Even Linked List

iven a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Example:
Given 1->2->3->4->5->NULL,
return 1->3->5->2->4->NULL.

Note:
The relative order inside both the even and odd groups should remain as it was in the input. 
The first node is considered odd, the second node even and so on ...

Credits:
Special thanks to @DjangoUnchained for adding this problem and creating all test cases.

Solution:
The problem has two cases to consider: the length of the list is even and odd, respectively. 
We use two pointers, p1 and p2, to trace the odd and even nodes, respectively. If the length of the list is even, we stop at p2.next == null, i.e, when p2 reaches to the last node. In this case, p1 is in the node next to the last. e.g.
1 -> 2 -> 3 -> 4 -> null
               |      |
             p1    p2

If the length of the list is odd, we stop at p2 == null, i.e, p1 is in the last node. 
1 -> 2 -> 3 -> 4 -> 5 -> null
                              |      |
                             p1   p2

We can observe that p1 is always one step below the p2, and we must let p1 stop at the last node of the odd list, then finally p1.next = evenHead. That is, we cannot lose the tail of the odd list, i.e., let p1 = null. 

Code (Java):

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode odd = head;
        ListNode even = head.next;
        ListNode evenHead = even;
        
        while (even != null && even.next != null) {
            odd.next = even.next;
            odd = odd.next;
            
            even.next = odd.next;
            even = even.next;
        }
        
        odd.next = evenHead;
        
        return head;
    }
}

Leetcode: 329. Longest Increasing Path in a Matrix

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

nums = [
  [9,9,4],
  [6,6,8],
  [2,1,1]
]

Return 4
The longest increasing path is [1, 2, 6, 9].

Example 2:

nums = [
  [3,4,5],
  [3,2,6],
  [2,2,1]
]

Return 4
The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

Solution:
This is a very classic DFS + memorialization problem. If we only use the DFS solution, it will end with many repeated calculations. Therefore, for each element in the matrix[i][j], we use a DP array dp[i][j] to denote the length of the maximum increasing path from this point. So along with the DFS, for a point in the matrix, if we've already found the longest increasing path, we don't have to repeatedly compute it again; we just need to return the length, which is dp[i][j]. 

One trick here is dp[i][j] stores the length of the longest increasing path. That is because the DFS from a point matrix[i][j] can guarantee the longest path from this point. Since we store this value in the dp[i][j], that can guarantee that dp[i][j] is the longest path from the point matrix[i][j]. 

Code (Java):

public class Solution {
    private int[] dx = new int[]{0, 0, -1, 1};
    private int[] dy = new int[]{1, -1, 0, 0};
    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }
        
        int m = matrix.length;
        int n = matrix[0].length;
        
        int max = 0;
        int[][] dp = new int[m][n];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                max = Math.max(max, helper(i, j, matrix, dp));
            }
        }
        
        return max;
    }
    
    private int helper(int row, int col, int[][] matrix, int[][] dp) {

        if (dp[row][col] > 0) {
            return dp[row][col];
        }
        
        int m = matrix.length;
        int n = matrix[0].length;
        
        int curMax = 0;
        
        for (int i = 0; i < 4; i++) {
            int x = dx[i] + row;
            int y = dy[i] + col;
            
            if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[row][col]) {
                curMax = Math.max(curMax, helper(x, y, matrix, dp));
            }
        }
        
        dp[row][col] = curMax + 1;
        
        return curMax + 1;
    }
}

Leetcode: 330. Patching Array

Given a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in range [1, n] inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.

Example 1:
nums = [1, 3], n = 6
Return 1.

Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.
Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3].
Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6].
So we only need 1 patch.

Example 2:
nums = [1, 5, 10], n = 20
Return 2.
The two patches can be [2, 4].

Example 3:
nums = [1, 2, 2], n = 5
Return 0.

Understand the problem:

show the algorithm with an example,

let nums=[1 2 5 6 20], n = 50.

Initial value: with 0 nums, we can only get 0 maximumly.

Then we need to get 1, since nums[0]=1, then we can get 1 using [1]. now the maximum number we can get is 1. (actually, we can get all number no greater than the maximum number)

number used [1], number added []
can achieve 1~1

Then we need to get 2 (maximum number +1). Since nums[1]=2, we can get 2. Now we can get all number between 1 ~ 3 (3=previous maximum value + the new number 2). and 3 is current maximum number we can get.

number used [1 2], number added []
can achieve 1~3

Then we need to get 4 (3+1). Since nums[2]=5>4; we need to add a new number to get 4. The optimal solution is to add 4 directly. In this case, we could achieve maximumly 7, using [1,2,4].

number used [1 2], number added [4]
can achieve 1~7

Then we need to get 8 (7+1). Since nums[2]=5<8, we can first try to use 5. Now the maximum number we can get is 7+5=12. Since 12>8, we successfully get 8.

number used [1 2 5], number added [4]
can achieve 1~12

Then we need to get 13 (12+1), Since nums[3]=6<13, we can first try to use 6. Now the maximum number we can get is 12+6=18. Since 18>13, we successfully get 13.

number used [1 2 5 6], number added [4]
can achieve 1~18

Then we need to get 19 (18+1), Since nums[4]=20>19, we need to add a new number to get 19. The optimal solution is to add 19 directly. In this case, we could achieve maximumly 37.

number used [1 2 5 6], number added [4 19]
can achieve 1~37

Then we need to get 38(37+1), Since nums[4]=20<38, we can first try to use 20. Now the maximum number we can get is 37+20=57. Since 57>38, we successfully get 38.

number used [1 2 5 6 20], number added [4 19]
can achieve 1~57

Since 57>n=50, we can all number no greater than 50.

The extra number we added are 4 and 19, so we return 2.

The code is given as follows

Code (Java):

public class Solution {
    public int minPatches(int[] nums, int n) {
        long maxReach = 0;
        int patch = 0;
        int i = 0;
        
        while (maxReach < n) {
            if (i < nums.length && nums[i] <= maxReach + 1) {
                maxReach += nums[i];
                i++;
            } else {
                patch++;
                maxReach += maxReach + 1;
            }
        }
        
        return patch;
    }
}

Leetcode: 331. Verify Preorder Serialization of a Binary Tree

One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node's value. If it is a null node, we record using a sentinel value such as #.

     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #

For example, the above binary tree can be serialized to the string "9,3,4,#,#,1,#,#,2,#,6,#,#", where # represents a null node.

Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.

Each comma separated value in the string must be either an integer or a character '#' representing null pointer.

You may assume that the input format is always valid, for example it could never contain two consecutive commas such as "1,,3".

Example 1:
"9,3,4,#,#,1,#,#,2,#,6,#,#"
Return true

Example 2:
"1,#"
Return false

Example 3:
"9,#,#,1"
Return false

Understand the problem:
The key of the problem is if a preorder traversal of a binary tree is valid, a leaf node must have the sequence like "number, #, #". Therefore, we can start from leaf nodes of tree, remove the leaf nodes by replacing the number, #, # by a single # until the tree becomes empty. 

Code (Java):

public class Solution {
    public boolean isValidSerialization(String preorder) {
        if (preorder == null || preorder.length() == 0) {
            return true;
        }
        
        String[] nodes = preorder.split(",");
        Stack<String> stack = new Stack<>();
        
        for (String node : nodes) {
            if (node.equals("#")) {
                while (!stack.isEmpty() && stack.peek().equals("#")) {
                    stack.pop();
                    if (stack.isEmpty()) {
                        return false;
                    }
                    
                    stack.pop();
                }
            }
            
            stack.push(node);
        }
        
        return stack.size() == 1 && stack.peek().equals("#");
    }
}

Leetcode: 332. Reconstruct Itinerary

Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.

Note:

1. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].
2. All airports are represented by three capital letters (IATA code).
3. You may assume all tickets form at least one valid itinerary.

Example 1:
tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Return ["JFK", "MUC", "LHR", "SFO", "SJC"].

Example 2:
tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Return ["JFK","ATL","JFK","SFO","ATL","SFO"].
Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical order.

Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

Understand the problem:
Classical graph problem. Use DFS + backtracking. 

Code (Java):

public class Solution {
    public List<String> findItinerary(String[][] tickets) {
        List<String> result = new ArrayList<>();
        if (tickets == null || tickets.length == 0) {
            return result;
        }
        
        // step 1: build the ajdList
        Map<String, List<String>> adjList = new HashMap<>();
        for (String[] ticket : tickets) {
            String from = ticket[0];
            String to = ticket[1];
            
            if (adjList.containsKey(from)) {
                adjList.get(from).add(to);
            } else {
                List<String> neighbors = new ArrayList<>();
                neighbors.add(to);
                adjList.put(from, neighbors);
            }
        }
        
        // step 2: sort the adjlist according to lex order
        for (String from : adjList.keySet()) {
            List<String> neighbors = adjList.get(from);
            Collections.sort(neighbors);
        }
        
        // step 3: start the dfs
        findItineraryHelper("JFK", adjList, result);
        
        return result;
    }
    
    private void findItineraryHelper(String curr, Map<String, List<String>> adjList, List<String> result) {
        
        List<String> neighbors = adjList.get(curr);
        
        if (neighbors != null) {
            while (neighbors.size() > 0) {
                String neighbor = neighbors.get(0);
                neighbors.remove(0);
                findItineraryHelper(neighbor, adjList, result);
            }
        }
        
        result.add(0, curr);
    }
}

Leetcode: 333. Largest BST Subtree

Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it.

Note:
A subtree must include all of its descendants.
Here's an example:

    10
    / \
   5  15
  / \   \ 
 1   8   7

The Largest BST Subtree in this case is the highlighted one. 
The return value is the subtree's size, which is 3.

Hint:

1. You can recursively use algorithm similar to 98. Validate Binary Search Tree at each node of the tree, which will result in O(nlogn) time complexity.

Follow up:
Can you figure out ways to solve it with O(n) time complexity?

Code (Java):

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private int max = 0;
    public int largestBSTSubtree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        largestBSTHelper(root);
        
        return max;
    }
    
    private Data largestBSTHelper(TreeNode root) {
        Data curr = new Data();
        if (root == null) {
            curr.isBST = true;
            return curr;
        }
        
        Data left = largestBSTHelper(root.left);
        Data right = largestBSTHelper(root.right);
        
        curr.lower = Math.min(root.val, Math.min(left.lower, right.lower));
        curr.upper = Math.max(root.val, Math.max(left.upper, right.upper));
        
        if (left.isBST && root.val > left.upper && right.isBST && root.val < right.lower) {
            curr.size = left.size + right.size + 1;
            curr.isBST = true;
            max = Math.max(max, curr.size);
        } else {
            curr.size = 0;
        }
        
        return curr;
    }
}

class Data {
    int size = 0;
    int lower = Integer.MAX_VALUE;
    int upper = Integer.MIN_VALUE;
    boolean isBST = false;
}

Leetcode: 334. Increasing Triplet Subsequence

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there exists i, j, k 
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.

Your algorithm should run in O(n) time complexity and O(1) space complexity.

Examples:
Given [1, 2, 3, 4, 5],
return true.

Given [5, 4, 3, 2, 1],
return false.

Credits:
Special thanks to @DjangoUnchained for adding this problem and creating all test cases.

Understand the problem:
The easiest solution for this problem is to use the same DP method for the Longest Increasing Subsequence (LIS). If then, we only need to check if the dp[i] >= 3. However, this will result in a O(n^2) time complexity. Since this problem asks for O(n) time, we need to think another solution. 

The idea of the O(n) time solution is greedy. We maintain two variables m1 and m2, which denote the minimum number and next to minimum number we have seen so far. So for each number in the array, we update the minimum and next minimum. If the number if greater than both m1 and m2, then we found the increasing triplet. 

Code (Java):

public class Solution {
    public boolean increasingTriplet(int[] nums) {
        if (nums == null || nums.length < 3) {
            return false;
        }
        
        int m1 = Integer.MAX_VALUE;
        int m2 = Integer.MAX_VALUE;
        
        for (int num : nums) {
            if (num <= m1) {
                m1 = num;
            } else if (num <= m2) {
                m2 = num;
            } else {
                return true;
            }
        }
        
        return false;
    }
}

Leetcode: 335. Self Crossing

You are given an array x of n positive numbers. You start at point (0,0) and moves x[0] metres to the north, then x[1] metres to the west, x[2] metres to the south,x[3] metres to the east and so on. In other words, after each move your direction changes counter-clockwise.

Write a one-pass algorithm with O(1) extra space to determine, if your path crosses itself, or not.

Example 1:

Given x = [2, 1, 1, 2],
┌───┐
│   │
└───┼──>
    │

Return true (self crossing)

Example 2:

Given x = [1, 2, 3, 4],
┌──────┐
│      │
│
│
└────────────>

Return false (not self crossing)

Example 3:

Given x = [1, 1, 1, 1],
┌───┐
│   │
└───┼>

Return true (self crossing)

Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

Understand the problem:
The problem is tricky to solve. There are in total three cases to consider if there is no cross
1. Only have internal squirrels. In this case, the length of each step should go smaller and smaller. So we only need to check if x[i] < x[i - 2]. 
2. Only have external squirrels. In this case, the length of each step should go larger and larger. So we only need to check if x[i] > x[i - 2]. 
3. In the third case, it goes external squirrel first then go internal. In this case, the trick part is we may need to update the base of the internal squirrel. 

Code (Java):

public class Solution {
    public boolean isSelfCrossing(int[] x) {
        if (x == null || x.length <= 3) {
            return false;
        } 
        
        int i = 2;
        int len = x.length;
        
        // case 1: outside squrial
        while (i < len && x[i] > x[i - 2]) {
            i++;
        }
        
        if (i == len) {
            return false;
        }
        
        // case 2: transist to inside squrial
        if ((i >= 4 && x[i] + x[i - 4] >= x[i - 2]) || 
            (i == 3 && x[i] == x[i - 2])) {
            x[i - 1] -= x[i - 3];
        }
        i++;
        
        // case 3: inside squrial
        while (i < len && x[i] < x[i - 2]) {
            i++;
        }
        
        return i != len;
    }
}

Leetcode: 336. Palindrome Pairs

Given a list of unique words. Find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome.

Example 1:
Given words = ["bat", "tab", "cat"]
Return [[0, 1], [1, 0]]
The palindromes are ["battab", "tabbat"]

Example 2:
Given words = ["abcd", "dcba", "lls", "s", "sssll"]
Return [[0, 1], [1, 0], [3, 2], [2, 4]]
The palindromes are ["dcbaabcd", "abcddcba", "slls", "llssssll"]

Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

Code (Java):

public class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> result = new ArrayList<>();
        
        if (words == null || words.length == 0) {
            return result;
        }
        
        // step1: put the reverse order of the words into a map
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            String rWord = reverse(words[i]);
            map.put(rWord, i);
        }
        
        // step 2 & 3: check the prefix of each word. 
        // It can form a palindrome iff prefix in the map AND 
        // rest substring is a palindrome. 
        // e.g. abll, if the prefix is ab, and the map contains a "ab", then
        // we can form a palindrome which is abllba
        
        // check the postfix of each word. 
        // The word can form a palindrome iff postfix is in the map AND
        // the rest of prefix is a palindrome
        // e.g. llab, where the postfix is ab, if the map cotnains a "ab", then
        // we can form a palindrome of ballab
        for (int j = 0; j < words.length; j++) {
            String word = words[j];
            
            // get prefix of each word
            for (int i = 0; i <= word.length(); i++) {
                String prefix = word.substring(0, i);
                String rest = word.substring(i);
                if (map.containsKey(prefix) && isPalindrome(rest) && 
                    map.get(prefix) != j) {
                    List<Integer> curr = new ArrayList<>();
                    curr.add(j);
                    curr.add(map.get(prefix));
                    result.add(curr);
                }
            }
            
            // get postfix of each word
            for (int i = word.length(); i > 0; i--) {
                String postfix = word.substring(i);
                String rest = word.substring(0, i);
                if (map.containsKey(postfix) && isPalindrome(rest) && 
                    map.get(postfix) != j) {
                    List<Integer> curr = new ArrayList<>();
                    curr.add(map.get(postfix));
                    curr.add(j);
                    result.add(curr);
                }
            }
        }
        
        return result;
    }
    
    private String reverse(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        
        char[] array = s.toCharArray();
        int start = 0;
        int end = array.length - 1;
        
        while (start < end) {
            swap(start, end, array);
            start++;
            end--;
        }
        
        return new String(array);
    }
    
    private void swap(int start, int end, char[] array) {
        char temp = array[start];
        array[start] = array[end];
        array[end] = temp;
    }
    
    private boolean isPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return true;
        }
        
        int start = 0;
        int end = s.length() - 1;
        
        while (start < end) {
            if (s.charAt(start) != s.charAt(end)) {
                return false;
            }
            start++;
            end--;
        }
        
        return true;
    }
}

Analysis:
Assume the number of words is n, and the average length of a word is m. The average time complexity is O(m^2 * n). 
Space complexity: O(n) since we use a map to store all the words