I have a huge int array which I need to find the Mode of,

Ive seen a few methods that use 2 `for`

loops (one nested) which seems unnecessary.

The only way I can think to find the mode with only one loop involves using `Map`

s:

```
int[] elements = new int[]{....numbers...};
Map<Integer,Integer> map = new .....Map Type....;
for(int number : elements){
if(map.containsKey(Integer.valueOf(number))){
map.put(Integer.valueOf(number),map.get(Integer.valueOf(number))+1);
}else{
map.put(Integer.valueOf(number),1);
}
}
```

Im not sure what kind of speed benefits using maps would actually give. Is there a better method?

If you use a hash map, the runtime complexity of your algorithm should be O(n): You visit each of the n elements once, and HashMap lookup and write is usually assumed to be O(1). So in total you get O(n * 1) which is O(n). If you use a tree map, you get O(n log n).

Compared to two nested loops (which sounds like O(n²)), the speed improvement is going from quadratic to linear, which is quite good: For 1000 elements, you perform 1000 "steps" instead of 1,000,000.

P.S. Getting better than linear is probably hard here -- can't imagine a way of calculating this without visiting each element at least once.

As Stefan Haustein already wrote, the complexity using a map is much lower than using 2 for loops.

There is one further improvement or rather specialization that can be done if you know the range of numbers stored inside your array. For example if you count colors which are in the range of 0-255, you don't have to use a map and instead can use a simple array.

```
int[] elements = new int[]{....numbers...};
int[] histogram = new int[256]; // 255 = highest possible value in elements
for(int number : elements){
++histogram[number];
}
```

Using a map is a more generalized way. You can think of a map as an array with a more complex indexing function. So in a normal array the number is at `array pointer + index`

while in a map this is calculated using a liner hash function.

No algorithm can be faster than O(n) (have a look at the wikipedia page for big-o notation). At least, not consistently (across all possible inputs). This does not mean that it cannot go any faster -- just that, beyond a certain problem size, whatever is faster can't keep on increasing the speed difference by more than a (probably small) linear factor.

This is because, whatever the order in which you examine the elements, given an array that is "almost balanced" as to the winner, the last element you examine can turn out to be the tiebreaker. Give me any algorithm that doesn't look at all elements, and I can write a input array that will make it return incorrect results. Therefore, you have to examine all of them at least once: O(n) complexity.

Hashmaps have general insert and lookup complexities of O(1) -- that is, on average, regardless of the size of the data, they take up a constant time to do their thing. Note that this constant time is several times larger than, say, array update/lookups (see **TwoThe**'s answer). Therefore, except for constants (which will vary depending on hashmap implementation, machine, VM, and so on), you can't get much faster than the code you posted. If you really need that 10% extra performance, then build a benchmark on hardware/software/input data as near as possible to your intended deployment and optimize *that*.

Similar Questions

I implement it by the following code, but I don't know whether there's a more efficient way to remove all blank spaces from a StringBuilder private static StringBuilder removeBlankSpace(StringBuilder

I was curious what the most efficient way to swap two elements in an array in Perl would be. Say I want to switch the elements with indexes of 3 and 5 respectively, what would be the fastest way to do

a newbie needs some help with logic flow: I'm using the Auto Complete extender control that ships with the Asp.net Ajax toolkit. This extender is hooked up to a web service, which will run a function

What would be the most efficient way to select a record when one of the value has changed? Ex: I have an account history table like below where records are being created when the account change: Id A

I'm using the following code to pull the definition of a word from a tab-delimited file with only two columns (word, definition). Is this the most efficient code for what I'm trying to do? <?php $h

What is the most efficient(fast and safe) way of reading a log file in java? The log file continuously(almost every second) gets updated.

Any know how can I get the mode value from an array? For example, if I have a array with difference number, how can I use Java to search out which number is appears the most?

What is the most efficient method to convert an throwable/exception's entire stack trace into a ByteBuffer (in Java)? Specifically, I need to log the entire exception into the database. The Thread.cur

I was wondering if someone could help me find the most efficient way of pulling data from two tables which have a common ID. A simple example is that I have two tables; customers and messages which h

I'm getting out of memory exceptions from the following function when RowCollection is 50000+ and thus i need to make it more memory efficient. The function is simply needs to construct a comma separa

I send JSON object to server. On server side I have to parse this obj with PHP. I'm stuck in the loop. I don't know how to proceed inside loops. Im looking for most efficient way to parse this object

I need to see if there are duplicates in an array of strings, what's the most time-efficient way of doing it?

I am looking at http://stackoverflow.com/questions/101439/the-most-efficient-way-to-implement-an-integer-based-power-function-powint-int. This is the answer they got. I am trying to make it work for C

I am trying to generate a query and having difficulty finding the most efficient way to do it in sqlalchemy, (note I'm using flask-sqlalchemy) The goal is to find all users have a meeting with a speci

What's the most resources efficient way to take a screenshot of display object in as3? This is the code I am currently using: public static function img(o:DisplayObject,width:int,height:int):ByteArray

What is the most efficient way of getting current time/date/day/year in C language? As I have to execute this many times, I need a real efficient way. I am on freeBSD. thanks in advance.

What is the most efficient method/data structure to create collections of similar objects in python? Example: Assume I have a number of Point() instances. Each instance has an x attribute. I'd like to

Possible Duplicate: Declaring variables inside or outside of a loop Please consider these 2 samples of Java code: // 1st sample for (Item item : items) { Foo foo = item.getFoo(); int bar = item.getB

Given an array a[], what would be the most efficient way to determine whether or not at least one element i satisfies the condition a[i] == i? All the elements in the array are sorted and distinct, bu

Given an array of integers 1 to 100 (inserted randomly), and one integer is taken out of the array. What is the most efficient way of finding the integer that is missing?

Basic Question: I have a k dimensional box. I have a vector of upper bounds and lower bounds. What is the most efficient way to enumerate the coordinates of the vertices? Background: As an example, sa

I have four different types of objects within my environment(box2d), each type of object having multiple instances of itself, and would like to find the most efficient way to deal with adding and mani

I have utilized the techniques here and concatenated two 1.5GB files in 70 seconds. http://nadeausoftware.com/articles/2008/02/java_tip_how_read_files_quickly My code involved using FileChannels with

Given an input String, what is the most efficient way to make just the first character lower case? I can think of a number of ways to do this. For example, using charAt and subString: String string=

What is the most efficient way to solve system of equations involving the digamma function? I have a vector v and I want to solve for a vector w such that for all i: digamma(sum(w)) - digamma(w_i) = v

This sentences are equals myString != null, myString.length() > 0 and ! myString.equals() ? Wich is the most efficient? (Java 1.4)

What is the most efficient algorithm for grouping identical items together in an array, given the following: Almost all items are duplicated several times. The items are not necessarily integers or a

In MS SQL 2000 and 2005, given a datetime such as '2008-09-25 12:34:56' what is the most efficient way to get a datetime containing only '2008-09-25'? Duplicated here.

Can anybody find any potentially more efficient algorithms for accomplishing the following task?: For any given permutation of the integers 0 thru 7, return the index which describes the permutation l

Assuming one needs to store a list of items, but it can be stored in any variable type; what would be the most efficient type, if used mostly for matching? To clarify, a list of items needs to be cont

I'm working on an iPhone app with a GAE backend. I currently have a database of ~8000 products and each product has 5 keywords, mined from reviews, that are the words used most often to describe the p

What's this easiest / most efficient way to initialize these blocks of doubles, preferably at compile time: #define N 1000 double mul1[N][N] __attribute__ ((aligned (64))); double mul2[N][N] __attribu

Can anyone suggest more efficient way of subsetting dataframe without using SQL/indexing/data.table options? I looked for similar questions, and this one suggests indexing option. Here are ways to sub

I have just finished this MySQL query and as I still consider myself a novice, was wondering if I have done this in the most efficient way? I have 4 tables, the first 2 contain category data and categ

I need to parse an xml file in java and store it in an array for sorting later. The xml file has this format <Experiments> <Experiment ID=312 RIndex=3 DIndex=3>40231</Experiment&g

How can I replicate Excel's mode function using SQL? If I run the mode function on a set of numbers in Excel it will return one mode value even if there are multiple mode values. I need some SQL to wo

I'm looking for a more efficient implementation for a generic dictionary counter. Currently this naive function produces a faster result compared to the collections.Counter implementation def unique

Below is the page with two iframes. This page has the javascript function called DoWork() which is called from any frame via window.top.DoWork. <html> <head runat=server> <title>TO

I have a need to convert audio samples from 11025 and 22050 to 44100; I'm looking for the fastest and best sounding conversion routine. I require that the answer be given in pure Java, without the nee

is it more efficient to use $('.active') or $('div.active') ? I have always avoided including div because it's extra text in the javascript file I don't want the user to have to download.

What is most efficient way to saturate int64 value to int32 with ARMv4 instruction set?

elasticsearch has several APIs for submitting documents (http, thrift, memcached). What's the most efficient way to submit a document in terms of resources used? My use case is about to have quite int

Which variant is most efficient, and why? Or will they get optimized to the same code? char inplace(int i) { // [some check if 0<=i<=2 here] return azS[i]; } char infunc(int i) { const char s[

What are the most expensive (both in terms of bytecode and cpu cycles) statements in the Java Programming language?

What would be the most efficient way of storing (and retrieving) session data (array) from a shopping bag into a mysql db? So that visitors get back their shopping bag content on a new visit. All I ne

I'm wondering what the most generally efficient tree structure would be for a collection that has the following requirements: The tree will hold anywhere between 0 and 232 - 1 items. Each item will b

Here is my interface: import java.util.ArrayList; public abstract class Function { private String name; private String result; public Function(String name, String result) { this.name = name; this.resu

What is the most efficient way to pass data (list of pairs of [Integer, Double]) between two Google App Engine instances ? Currently I use Java binary serialization. Frontend servlet receives data fro

What's the most efficient way to pass a single char to a method expecting a CharSequence? This is what I've got: textView.setText(new String(new char[] {c} )); According to the answers given here, th

What would be the most efficient way to iterate through a collection with a large number of items (1,000 or more) and update the items' properties in real-time? At the moment, my program draws an imag