• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Is this an In-place algo?

 
Ranch Hand
Posts: 692
Eclipse IDE Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Is this algo is an in-place, according to me yes, because tmp[] is consider as auxiliary space, so space complexity still remains O(1)
Do you agree with my answer if no please explain me too
thanks for your time and effort..!!

 
lowercase baba
Posts: 13089
67
Chrome Java Linux
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

naved momin wrote:
Is this algo is an in-place, according to me yes, because tmp[] is consider as auxiliary space, so space complexity still remains O(1)
Do you agree with my answer if no please explain me too
thanks for your time and effort..!!


I think not, but I could be wrong. I thought that "in place" means you swap elements within whatever structure you have. Further. I think your space complexity is actually O(N). The longer the string is, the more additional memory you need.
 
Rancher
Posts: 43081
77
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

I thought that "in place" means you swap elements within whatever structure you have.


+1

I think your space complexity is actually O(N).


+1
 
Master Rancher
Posts: 4806
72
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I was raised to understand that you could also have a small, constant amount of additional auxiliary space, and still be considered in-place. Like a temp variable. Now "small" may be a bit subjective, but the "constant" part is key. In this case, you're using a temp variable (fine) and assigning it a new array of length k.length() - not fine. The amount of extra space you're using is not a constant; it's O(N). Or O(k) in this case.
 
fred rosenberger
lowercase baba
Posts: 13089
67
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Mike Simmons wrote:I was raised to understand that you could also have a small, constant amount of additional auxiliary space, and still be considered in-place.


I guess that makes sense. If I have an int array of 10 elements, to do any swapping, I would need a int variable to hold the one while i swap (unless I do that fancy boolean trick, which I hate but know is an option).
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic