Is it still O(n) space if we don't perform the actual assignment?-CodePudding

Consider the Valid Anagram question where we return true if two strings are anagrams of each other:

e.g. validAnagram("name", "mane") returns true.

Assuming that we can only pass in the strings by value, a possible solution is to store the two sorted arrays into new variables, and then return whether those variables are equal:

    func validAnagram(_ s: String, _ t: String) -> Bool {
        guard s.count == t.count else { return false }
        
        let sortedS = s.sorted()
        let sortedT = t.sorted()
     
        return sortedS == sortedT
    }

In this case, the algorithm has a time complexity of O(nlogn), and space complexity O(2n) => O(n)

My question is whether changing the function to the following makes the space complexity O(1):

func validAnagram(_ s: String, _ t: String) -> Bool {
    guard s.count == t.count else { return false }
    return s.sorted() == t.sorted()
}

Is this true? Or is memory still allocated in the background to remember what s.sorted() and t.sorted() are, even though I am not explicitly initializing variables?

CodePudding user response：

It doesn't make any difference. You still allocate memory for sorted arrays.

To avoid using additional space you need to sort data in-place if it's possible.