CODEWITHSUNDEEP
pythonalgorithmtime-complexity
J. Doe
J. Doe

Reputation: 1341

About time complexity of the code snippet

I am trying to solve a question on Pramp:

Implement a function reverseWords that reverses the order of the words in the array in the most efficient manner.

Ex: arr = [ 'p', 'e', 'r', 'f', 'e', 'c', 't', ' ', 'm', 'a', 'k', 'e', 's', ' ', 'p', 'r', 'a', 'c', 't', 'i', 'c', 'e' ]

output: [ 'p', 'r', 'a', 'c', 't', 'i', 'c', 'e', ' ', 'm', 'a', 'k', 'e', 's', ' ', 'p', 'e', 'r', 'f', 'e', 'c', 't' ]

The Python-like pseudo-code which they have given is as follows:

function reverseWords(arr):
    # reverse all characters:
    n = arr.length
    mirrorReverse(arr, 0, n-1)

    # reverse each word:
    wordStart = null
    for i from 0 to n-1:
        if (arr[i] == ' '):
            if (wordStart != null):
                mirrorReverse(arr, wordStart, i-1)
                wordStart = null
        else if (i == n-1):
            if (wordStart != null):
                mirrorReverse(arr, wordStart, i)
        else:
            if (wordStart == null):
                wordStart = i

    return arr


# helper function - reverses the order of items in arr
# please note that this is language dependent:
# if are arrays sent by value, reversing should be done in place

function mirrorReverse(arr, start, end):
    tmp = null
    while (start < end):
        tmp = arr[start]
        arr[start] = arr[end]
        arr[end] = tmp
        start++
        end--

They say that the time complexity is O(n), essentially because they are traversing the array twice with a constant number of actions for each item. Co-incidentally, I came up with the exact same approach using stringstreams in C++, but thought that it was not efficient!

I think the time complexity of this snippet should be O(mn), where m is the number of words in the string and n is the average number of alphabets in each word. This is so because we iterate over all the elements in the input and in the worst case, mirrorReverse() visits all the elements again for reversing, for a given i.

Which is correct?

Upvotes: 1

Views: 112

Answers (1)

Prune
Prune

Reputation: 77900

In O(n), n refers to the length of the input (total characters), not the quantity of words. I suspect you're confused because the code uses a variable n in the latter sense.

Note the explanation: "traversing the array ...". "The array" consists of individual characters.

The implementation seems a bit silly to me; it's much more readable to:

  1. Join letter groups into words.
  2. Reverse the word order (including spaces) with a trivial list slice.
  3. Expand the words back into characters.

Upvotes: 2

Related Questions