Watch 5 video solutions for Palindromic Subarray Sum, a hard level problem. This walkthrough by Rajan Keshari ( CSE - IIT Dhanbad ) has 774 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer array nums.
Return the maximum possible sum of a subarray of nums that is a palindrome.
Example 1:
Input: nums = [10,10]
Output: 20
Explanation:
The whole array [10,10] is a palindrome. Therefore, the maximum sum is 10 + 10 = 20.
Example 2:
Input: nums = [1,2,3,2,1,5,6]
Output: 9
Explanation:
The contiguous subarray [1,2,3,2,1] is a palindrome. Its sum is 1 + 2 + 3 + 2 + 1 = 9 and it is the maximum sum.
Example 3:
Input: nums = [7,1,2,1,7,3,4,3,4]
Output: 18
Explanation:
The contiguous subarray [7,1,2,1,7] is a palindrome. Its sum is 7 + 1 + 2 + 1 + 7 = 18 and it is the maximum sum.
Example 4:
Input: nums = [1,2,3,4,5]
Output: 5
Explanation:
No subarray with length greater than 1 is a palindrome. The largest element in the array is 5. Therefore, the answer is 5.
Example 5:
Input: nums = [1000]
Output: 1000
Explanation:
The subarray with only one element is a palindrome. Therefore, the answer is 1000.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 10āāāāāāā9Problem Overview: You need to find subarrays whose total sum is a palindrome number. The challenge is avoiding repeated subarray scans and expensive palindrome checks across all possible ranges.
Approach 1: Brute Force Enumeration (O(n^3) time, O(1) space)
Iterate over every possible subarray using two nested loops, then compute the subarray sum with another loop. After calculating the sum, convert the value into a string or reverse the digits numerically to verify whether it is palindromic. This approach is useful for validating small test cases and building intuition, but it becomes unusable once the array size grows beyond a few thousand elements.
Approach 2: Prefix Sum + Direct Palindrome Check (O(n^2 * log M) time, O(n) space)
Build a prefix sum array so each subarray sum can be computed in constant time using prefix[r + 1] - prefix[l]. This removes the inner summation loop and reduces the complexity significantly. The remaining bottleneck is checking whether every generated sum is a palindrome. Numeric reversal works better than string conversion because it avoids extra allocations and reduces constant overhead.
Approach 3: Prefix Sum + Precomputed Palindrome Values (O(n * P) time, O(n) space)
The optimal solution generates all palindrome numbers within the possible subarray sum range ahead of time. While iterating through the array, maintain cumulative sums and use a hash map to count previously seen prefix sums. For every palindrome value p, check whether currentPrefix - p exists in the map. This transforms the problem into a frequency lookup problem and avoids checking palindrome properties repeatedly. The approach combines array traversal, prefix sums, and hash-based counting efficiently.
Recommended for interviews: Interviewers usually expect you to begin with brute force to demonstrate correctness, then optimize using prefix sums. The strongest solution precomputes valid palindrome sums and uses hash lookups for constant-time frequency checks. That progression shows both problem-solving depth and practical optimization skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n^3) | O(1) | Small arrays or debugging correctness |
| Prefix Sum + Palindrome Check | O(n^2 * log M) | O(n) | Medium constraints where direct checking is acceptable |
| Prefix Sum + Precomputed Palindromes | O(n * P) | O(n) | General optimal solution for large inputs |