How to Optimise a given problem time complexity?

Question

I have a question which says

Given an input

ababacad

The output should be all the a's should come first together rest characters should follow their sequence as they were originally. i.e.

aaaabbcd

I solved it like below code

String temp="", first="" ; for(int i=0;i<str.length;i++) { if(str.charAt(i)!='a') temp=temp+str.charAt(i); else first=first+str.charAt(i); } System.out.print(first+temp);

The output matches but it says it is still not optimised. I guess its already order of N complexity. Can it be optimised further.

yes..it has to do with both. Because strings are immutable, when you concatenate them together, you create a new string and copy the characters from each of the other strings into the new string. This overhead increases the amount of time your algorithm takes to run. Using StringBuilder instead will optimize your solution. — Code-Apprentice
– Code-Apprentice, Commented Sep 10, 2019 at 16:43
You clearly can't get a better asymptotic lower bound than linear simply because you must look at all the array elements to verify they're in an acceptable order. It might be possible to get better constant multipliers than your method yields, if that's what you're after. — Patrick87
– Patrick87, Commented Sep 10, 2019 at 16:46
@HimanshuAhuja is it a sorting problem? Does your solution works for ababadacabb? — ArpanKhandelwal
– ArpanKhandelwal, Commented Sep 10, 2019 at 16:53
The + makes it O(n^2). So, use a char array, swap values and return a new string from this char array. — mighty_dev
– mighty_dev, Commented Sep 10, 2019 at 19:54

kumarchandresh · Accepted Answer · 2019-09-12 03:31:49Z

Optimization here can mean string operations as well as the number of iterations. So, just to be on the safe side, you can implement it using arrays. The time complexity will be O(n) which is the minimum for this problem as you have to check every position for the presence of char 'a'.

String input = "ababacad"; char[] array = input.toCharArray(); char[] modified = new char[array.length]; int a = 0; // index for a int b = array.length - 1; // index for not a for (int i = array.length - 1; i >= 0; --i) { if (array[i] != 'a') modified[b--] = array[i]; else modified[a++] = array[i]; } String output = new String(modified); System.out.println(output);

You can also do it in-place, by reversing the loop, but the overall time complexity would be the same, while in terms of memory it would be constant.

Collectives™ on Stack Overflow

How to Optimise a given problem time complexity?

1 Answer 1

1 Comment

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Related