CODEWITHSUNDEEP
javaalgorithmdata-structuresbig-ospace-complexity
Kelli
Kelli

Reputation: 89

What is the space complexity of an algorithm that returns an array list?

I am analyzing a spiral matrix algorithm. The solution calls for input of a matrix and the return of an array list. This is the chosen solution:

class Solution {
public List < Integer > spiralOrder(int[][] matrix) {
    List ans = new ArrayList();
    if (matrix.length == 0)
        return ans;
    int r1 = 0, r2 = matrix.length - 1;
    int c1 = 0, c2 = matrix[0].length - 1;
    while (r1 <= r2 && c1 <= c2) {
        for (int c = c1; c <= c2; c++) ans.add(matrix[r1][c]);
        for (int r = r1 + 1; r <= r2; r++) ans.add(matrix[r][c2]);
        if (r1 < r2 && c1 < c2) {
            for (int c = c2 - 1; c > c1; c--) ans.add(matrix[r2][c]);
            for (int r = r2; r > r1; r--) ans.add(matrix[r][c1]);
        }
        r1++;
        r2--;
        c1++;
        c2--;
    }
    return ans;
}

}

I have looked up space complexity at this site but I do not know how to apply the information to this case.

I have looked in the discussion section of the comments.

Some say it is O(N) space because the solution creates an array list.

Some say that it is O(1) space because the question requires the return of the array list. So that space is already accounted for.

Which one is true?

Upvotes: 1

Views: 1011

Answers (2)

molamk
molamk

Reputation: 4126

Definitely O(n)

  • Since the size of the List ans depends on the size of the matrix, we can say that O(1) is not the answer. This is because O(1) indicates a constant space, which is not the case here.
  • The List ans has an exact size of n = width * height, which will allow it to contain all items in the matrix.
  • If our matrix doubles in size, then our ans will also double in size since the number of items has doubled. This indicates a linear relation between the size of matrix and ans. We can then say that our space is complexity is indeed O(n).

Upvotes: 2

Trevin
Trevin

Reputation: 1

The O(1) means that the amount of memory needed for this algorithm is not dependent on the size of the input. This clearly is not the case, an element is added to the array list each time one of the inner for loops iterates. So, since the algorithm has O(MN) run time, it also has O(MN) memory complexity where matrix is of size M x N.

Upvotes: 0

Related Questions