Win a copy of Beginning Java 17 Fundamentals: Object-Oriented Programming in Java 17 this week in the Java in General forum!
  • 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:
  • Tim Cooke
  • Campbell Ritchie
  • Ron McLeod
  • Liutauras Vilda
  • Jeanne Boyarsky
Sheriffs:
  • Junilu Lacar
  • Rob Spoor
  • Paul Clapham
Saloon Keepers:
  • Tim Holloway
  • Tim Moores
  • Jesse Silverman
  • Stephan van Hulst
  • Carey Brown
Bartenders:
  • Al Hobbs
  • Piet Souris
  • Frits Walraven

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: 13023
66
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: 43027
76
  • 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
 
Rancher
Posts: 4070
56
  • 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: 13023
66
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).
 
reply
    Bookmark Topic Watch Topic
  • New Topic