# 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
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',  * 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
``````
• First of all, thanks for the answer! I forgot to say: 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. – nbro Mar 14 '15 at 11:11
• @Rinzler My algorithm is not using any such function. Arrays are core construct in any language. – Euphoric Mar 14 '15 at 18:06
• But you have to import them, and behind the scenes `array` is a class, with a `__init__` method, where some "unknown" operations are performed. Because of this, I should just use known time complexity operations: loops, assignments, accessing elements of a list... – nbro Mar 14 '15 at 18:10
• @Rinzler With your definition, even using Python, which uses a GC and can do anything while interpreting your code. You should be using C if you really want to be sure operations you are making have defined complexities. Also, "accessing elements of a list" has much less defined complexity than "accessing elements of an array". Hell, in C, you would have to use array, because list is a library structure with not clearly defined complexity. – Euphoric Mar 14 '15 at 18:17
• Of course I could have used C, but the problem is that my professors decided to use Python, since everybody in our class knows Python. They simply said that we should not use libraries (apart from `sys` to read some input). – nbro Mar 14 '15 at 18:20