Java Array Algorithm - Big O

Question

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

I can't see how you can get better than O(n) because you will atleast have to inspect all the entries in the array. — Abhishek Bansal
– Abhishek Bansal, Commented Oct 31, 2013 at 13:35
Writing this would give me O(n) + O(n) do you mean O(n) time and O(n) space complexity? — Michał Rybak
– Michał Rybak, Commented Oct 31, 2013 at 13:35
You cannot beat O(n) time when the worst case size of the output is O(n) bytes. — Sergey Kalinichenko
– Sergey Kalinichenko, Commented Oct 31, 2013 at 13:36
I assume you OP wants to reduce space complexity, as time complexity obviosly cannot be under O(n)... — Michał Rybak
– Michał Rybak, Commented Oct 31, 2013 at 13:37
I'm tempted to add the array tag to this. Then every word in the title would be a tag :) — Cruncher
– Cruncher, Commented Oct 31, 2013 at 13:56

Roy Dictus · Accepted Answer · 2013-10-31 13:39:16Z

3

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).

answered Oct 31, 2013 at 13:39

Roy Dictus

33.3k9 gold badges64 silver badges77 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Cruncher Over a year ago

In terms of Big-O complexity this is the same.

Cruncher Over a year ago

@Geobits O(n) is certainly an upper bound for building the string as well. So it's not really relevant.

user2366923 · Accepted Answer · 2013-10-31 13:41:07Z

1

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

answered Oct 31, 2013 at 13:41

user2366923

Comments

score 1 · Accepted Answer · 2013-10-31 14:15:10Z

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).

Collectives™ on Stack Overflow

Java Array Algorithm - Big O

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related