Space Complexity vs Time Complexity

Walmart
LCingNow

Go to company page Walmart

LCingNow
May 20, 2021 20 Comments

I have been doing a lot of lc practice however I always almost struggle with space complexity when evaluating it. I slowly but surely realised not only your solution should be optimal in terms of time it should also be optimal in terms of space.

So can the community please suggest me a good resource for learning this forte because most if not all courses are focused on time complexity.#tech #interviews #faang

comments

Want to comment? LOG IN or SIGN UP
TOP 20 Comments
  • Amazon
    Pipmastah

    Go to company page Amazon

    Pipmastah
    The reason most university classes focus on time complexity and not so much on space complexity is because it's not that complex (see what I did there). You can have algorithms that have time complexities like O(A*B*log log C) and calculating that wouldn't be that straightforward. With space complexity, your space, given a particular input size, will usually be just constant, multiple or exponential times of the input size, and this is something you learn in middle school.
    May 20, 2021 4
  • Intuit / Eng
    BYun35

    Go to company page Intuit Eng

    BYun35
    Well, O(1) implies constant space or just utilizing the input you've been provided. O(n) means an additional amount of space which is equal to the input size - like a copy of the input array(1D). If you're building a graph using a matrix it's O(n^2) but if you use adjacency lists it's O(n + m)(n,m are # of vertices and edges).

    (Of course, this is a very quick answer typed up on a phone. But, solve more questions with data structures as the focus and you'll understand how to compute space complexity )
    May 20, 2021 2
    • Amazon / Eng
      __BRB

      Go to company page Amazon Eng

      PRE
      Nagarro
      __BRB
      Hey, don't we include input size in space complexity?
      Like if we are traversing an array of size n then won't space complexity be O(n) but auxiliary space used would be O(1).
      May 21, 2021
    • Amazon
      fatcat420

      Go to company page Amazon

      fatcat420
      AFAIK when people talk about space complexity it is assumed you are talking about auxiliary space
      May 21, 2021
  • Yardi
    sticktwots

    Go to company page Yardi

    sticktwots
    Time complexity issues are more annoying to end user
    May 20, 2021 0
  • LinkedIn
    hei5enberg

    Go to company page LinkedIn

    hei5enberg
    Just like time complexity try to understand it in terms of operations. Searching in an array, do you need to store the values in an additional array, if yes how much space (in order of the input) does it take, can you do it without creating an additional array; what are the implicit operations you might be doing that adds to the space complexity (e.g recursion and adding to call stack).
    May 20, 2021 2
    • LinkedIn
      hei5enberg

      Go to company page LinkedIn

      hei5enberg
      Both might give valid solutions, more space optimal might be not creating an additional or using an iterative approach vs recursive. I don't think there is any central resource but study as many also as you can and understand each operation in terms of space and time. Sometimes one can be optimized over the other.
      May 20, 2021
    • Walmart
      LCingNow

      Go to company page Walmart

      LCingNow
      OP
      Appreciate the detailed breakdown and explanation.
      May 21, 2021
  • Google
    d-ll-b

    Go to company page Google

    d-ll-b
    Your solution should definitely be time optimal first. Then without sacrificing that, if you can find ways to use less memory then that’s a plus. I don’t think there’s a one size fits all answer to this, it really depends on the problem
    May 20, 2021 0