vivekiitian's blog

Changing "int" to "Integer" gives significant performance improvement!
By vivekiitian, history, 5 years ago, In English

I tried to solve this problem. Refer to my solution 1 and 2. The only difference between those solutions is datatype int is replaced by Integer and solution got accepted (runtime got reduced from more than 1s to 140 ms). Any idea why is it happening?

  • Vote: I like it
  • +24
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Arrays.sort use Quick Sort (Worst case complexity of O(n^2)) when passing an array of primitive values, and Merge Sort (Worst case complexity of O(n log(n))) when using an array of object references.

I assume the problem has got some anti-tests against inefficient sorting.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Java sorts primitive types by quick sort which is O(N^2) in the worst case, while it sorts Objects in O(nlogn) using merge sort I think.

→ Reply
»
5 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Learn to read the API documentation (for your own good).

→ Reply