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

Question

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(n²), 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.

Answer 1

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

Answer 2

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).