CODEWITHSUNDEEP
javaalgorithmbig-o
Deslyxia
Deslyxia

Reputation: 629

Java Array Algorithm - Big O

With regards to Big O notation what is the best method of solving the following problem?

Given a String array of size N. Iterate through the array and return a single string containing the string that was repeated in the array the most. Also the string returned should repeat the string the number of times it was in the array. EX. if in the array "Bob" was the string found most and it was found 3 times the string returned should be "BobBobBob"

In thinking of how to do this I was thinking of using a HashMap or something else that would force unique key values, store the string as the key and the frequency as the value. When its all said and done that would leave me to iterate through the map comparing values..

Overall this would give me O(n) + O(n) ... im just wondering if there is a better way to do it

EDIT:

I understand that you cant do better than O(n) but the issue here is that once i iterate over the initial array to build the HashMap I will then have to reIterate over the hashmap to figure out which pair has the highest value which will again be O(n) .. essentially is there a way to do this where i only have to iterate the entire list One time

Upvotes: 0

Views: 283

Answers (3)

user2858650
user2858650

Reputation:

As long as you have to cycle through the entire list to pull back your values, you are never going to get better than O(n). The only way I could think of ever pulling back anything close to O(1) would be to store a "max" instance variable that calculates the max value during your insert.

But then really you are only trading an O(1) insert for an O(n) insert. But depending on which you will use more frequently, that might work for you.

A better possible alternative (though really heavy on overhead) would be to store a hashmap of all your total counts when you insert values into your array. Then you can keep a running total and storing a max value would be better than O(n) more closer to O(log n).

EDIT:

I understand what you are asking now... You might try storing your values in a Binary Search Tree... that will sort your data as you add it into the data structure and any recalls to that data structure will be either O(log n) for a traversed get and O(1) to pull back the root (or max value).

Upvotes: 1

user2366923
user2366923

Reputation:

it is sure that you have to go throw all the array, so I think that you just have to create a struct or class like:

     class myString{
       public String str ;
       public int repetition ;
       public myString(String str){
             this.str = str ;
             repetition = 1 ;
       }
       public void increment(){
              repetition+=1;
       }
      }

you use this and go throw your array and create new object and increment when find existing one. at the end the one having big repetition value is what you are searching

Upvotes: 1

Roy Dictus
Roy Dictus

Reputation: 33139

My 2 cents: O(2n) isn't bad, but maybe you can do better...

You can use a HashMap<String, Integer> and then also a WinnerText string and WinnerCount integer counter that you update on the fly. Then at the end you use the latter two to build your result string, and that should give you O(n) + O(1).

Upvotes: 3

Related Questions