More efficient alternative that checks if a list can be made a palindrome

For my algorithms and data structures class, I have to write an algorithm that is more efficient in the worst case than the following algorithm:

``````def algo_X(A):
i = 0
j = len(A)-1
while i < j:
if A[i] != A[j]:
k = i + 1
while k < j:
if A[i] == A[k]:
A[k], A[j] = A[j], A[k]
break
elif A[j] == A[k]:
A[k], A[i] = A[i], A[k]
break
else:
k += 1
if k == j:
return False
i += 1
j -= 1
return True
``````

This algorithm returns True if the elements of list passed as argument can be manipulated (swapped) in order to create a new list, which, if we read from the left or from the right, has the same order of elements (palindrome). Else returns False. For example, this list `['a', 'a', 'b', '2', 'b', 'b', ‘2’]` can be ordered so that we have a list with the same elements in the same positions, if we read at the same time from the left and from the right: `['a', 'b', '2', 'b', '2', 'b', ‘a’]`.

Note that this is my interpretation of the algorithm, they did not tell us what this algorithm was supposed to do.

If I am not wrong, this algorithm, in the worst case (and average case), is O(n2), and Ɵ(n) in the best case.

The exercise specifically states that I don't have necessarily to change the list (like in `algo_X`), but just to return `True` or `False` specifying respectively if the list can be made a palindrome or not.

We cannot use libraries, but just built-in constructs. We cannot even use slice, for example. This is because we don't "know" exactly the time complexity of those functions. I will edit my question

To make a better algorithm for the worst case, I thought I could use `merge sort`, whose time complexity is always n*log(n), plus a loop, which would not make the algorithm worse, asymptotically.

This is my `merge` function for my merge sort function:

``````def merge(A, B):
ls = []
a, b = 0, 0
while a < len(A) and b < len(B):
if A[a] <= B[b]:
ls.append(A[a])
a += 1
else:
ls.append(B[b])
b += 1
while a < len(A):
ls.append(A[a])
a += 1
while b < len(B):
ls.append(B[b])
b += 1
return ls
``````

This is my merge sort function:

``````def merge_sort(A):
if len(A) < 2:  # basic condition
return A
L = merge_sort(A[0:len(A)//2])
R = merge_sort(A[len(A)//2:])
return merge(L, R)
``````

Finally, here's my alternative, which returns `True`, if the list can be made a palindrome, `False` otherwise:

``````def better_algo_x(A):
if len(A) < 2:
return True
sorted_A = merge_sort(A)
odd_groups = 0
current = sorted_A[0]
c = 1  # Used to count the number of characters that are equal between them
for i in range(1, len(sorted_A)):
if current == sorted_A[i]:
c += 1
else:
if c % 2 == 1:
odd_groups += 1
if odd_groups > 1:
return False
current = sorted_A[i]
c = 1
# for the last group of characters
if c % 2 == 1:
odd_groups += 1
if odd_groups > 1:
return False
return True
``````

I have a few questions:

• Are my functions correct?

• Is my analysis of the time complexity of the algorithm `algo_X` correct?

• Does my `better_algo_x` do what it is supposed to do?

• Does it do it in n*log(n) in the worst case?

• Can I still improve it? How?

• Do you know (other) better alternatives for `algo_X`?

Of course, some questions might seem silly, but I would like to hear the opinion of some experts. Of course, I have tried my algorithms.

Yes, your analysis and algorithms are correct. But it can be made better by trading off memory for performance IF the amount of possible characters in string is limited (eg. it is not full Unicode). Basically, you can use hash-map to keep count of every character in O(n)*O(1) and then go through the list in O(1) (because the count of all possible characters is always the same). Meaning O(n)*O(1)+O(1) = O(n) in worst case.

``````def isPalindromic(A):
hashArray = array.array('I', [0] * 256)

for ch in A:
ascii = ord(ch)
hashArray[ascii] += 1

notEven = 0
for count in hashArray:
if (count > 0 and count % 2 == 1):
notEven += 1

return notEven <= 1 #one can be even, then it will be in the center
``````
• Goalie it’s not. If the length is even it is impossible that there is a single character occurring an odd number of times. Commented Feb 5, 2021 at 6:37

Starting from the answer from Euphoric, no reason to restrict your character pool:

``````from collections import defaultdict

def isPalindromic(A):
counter = defaultdict(int);
# initializes a dictionary that returns 0 if the key is missing

for letter in A:
counter[letter] += 1

notEven = len([count for count in counter.values() if count % 2 == 1])
# if you want to avoid the extra list allocation,
# this is less clear but more efficient:
notEven = sum(1 for count in counter.values() if count % 2 == 1)

return notEven <= 1
``````

For reasoning about the complexity, note that:

• You iterate once over the entire array to count the letters and insertion in the dictionary is constant time (`O(n)`)
• You iterate over all the values of the dictionary, the values are at most `n`, so `O(n)`

In particular, the complexity is `O(n)` with an additional space complexity of `O(n)` (worst case scenario, the array has all distinct values).

• Your check for odd/even length is not needed at all. Commented Feb 5, 2021 at 6:40
• @gnasher729 You're right, removing it Commented Feb 5, 2021 at 7:59