4. How to Solve LeetCode in Java and Beat Everyone
July 11, 2026
I dislike Java and I also dislike LeetCode-style interviews, so I don't really understand how I found myself solving almost every daily LeetCode problem in Java for more than half a year already, but here I am, and now I have something to share.
When I practiced for my software development interviews before, I normally used either plain C, or C++ with some limited STL. Both are good enough for a regular LeetCode-style task, and I got all my offers using one of those. I know a few folks who used Java for their interviews, and I was wondering why; it really looks like the language is just a little bit too verbose for this purpose, and simple things like “let's sort this array in the descending order” require remembering some weird names like Collections.reverseOrder(), which is not something I want to do during my interview.
But, as I said, I found myself doing this Java+LeetCode challenge; and when you submit a LeetCode problem, it shows you a histogram of all accepted solutions for this task in the given language, and it looks like this:
Even if it does not affect anything, you naturally want to score higher, so after doing this for half a year, I think I know something about improving your Java solution runtime on LeetCode.
Note: I don't know much, or anything, about optimizing Java code in general. Everything written below is strictly limited to the LeetCode execution environment. You have been warned.
We'll start from some simple ideas, and then we'll see what kind of code style directly follows from those ideas.
Avoid allocations
Allocations are expensive. A few allocations, like creating new int[n] in the beginning of your function, are inevitable, but if you call new in a loop, you will probably end up somewhere in the middle of the histogram, unless these allocations are required by the problem.
Avoid wrapper types
In Java, you cannot create a collection of primitive types, such as ArrayList<int>; you must create ArrayList<Integer> instead. I would assume it's not a big deal for any real life usage, because in the real code, you don't need to create containers with primitive types too often; but for LeetCode, it's often a deal breaker. Each Integer is an allocated object, so while new int[n] allocates memory just once, new ArrayList<Integer>() and then adding n elements will allocate n+1 times, killing your chances to score high.
These two items combined bring us to the next idea:
Avoid collections
Yes, all those HashSets and TreeMaps. Sometimes inevitable, but try to avoid them, especially in cases like HashMap<Integer, Integer>, which combines the worst of the previous paragraphs.
If it all feels a little bit negative, here's one positive thing:
Function calls are cheap
In the LeetCode context, I didn't see any serious improvement when I tried to reduce the number of function calls. It's completely fine to create a helper function and call it 10000 times, or use a recursion for your DFS. Calling functions is just fine.
Array element access is expensive
Accessing array elements is unavoidable, but if you want to access the same element twice, save the value in a variable. Again, I'm completely not sure if this recommendation makes sense for your regular Java program (probably not), but for LeetCode, it improves things quite a lot.
Where do we arrive when we try to follow these rules? A surprising idea directly follows:
If you want to write a fast Java solution on LeetCode, write as if it's plain C.
Indeed, most of my solutions can be rewritten in C with only minor syntax changes.
— But what about all those collections, don't you need them to solve the problems effectively?
— Sure. You just implement what you need.
This is probably not good advice for any real interview: I think the interviewer will be confused if, instead of using a HashSet, you write your own quick'n'dirty implementation. But when solving problems for fun, why not? It's all not too difficult, so let me show you a few common patterns here.
Replace HashSet and HashMap with a simple linear probing
There are tons of LeetCode problems that require using either a HashSet or a HashMap for an amortized constant time lookup, and very often you need HashSet<Integer> or HashMap<Integer, Integer>, both of them violate all three principles above.
Luckily, there is a magical trick that helps avoid using these containers, and this trick is well-known since the times I participated in ACM contests in early 2000s, writing code in Borland Pascal 7.0 and Borland C++ 3.1. A hand-written hash function combined with linear probing is the easiest way to implement a hash set or a hash map for primitive types, and requires zero allocations, except for the initial allocation of the arrays you need.
For integers, I would normally use the following hash function, adapted from this StackOverflow answer; note that Java does not have unsigned int, hence Math.floorMod:
public int hash(int x) {
x = ((x >> 16) ^ x) * 0x45d9f3b;
x = ((x >> 16) ^ x) * 0x45d9f3b;
x = (x >> 16) ^ x;
return Math.floorMod(x, size);
}
For strings, I would do this:
public int hash(char[] s) {
int result = 0;
for (char c : s) {
result = result * 37 + c;
}
return Math.floorMod(result, size);
}
Note: in my experiments on LeetCode it's often faster to convert your string to a char or byte array (.toCharArray() or .getBytes()) rather than calling .charAt(), even though both conversions allocate an array.
Now that you have those hash functions, what do you do? Let's look at LeetCode #1, Two Sum, which is a great example of an easy problem that requires hash maps to get a nearly linear solution. The default solution would look like this:
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
int[] result = new int[2];
for (int i = 0; i < nums.length; ++i) {
int needed = target - nums[i];
Integer got = map.get(needed);
if (got != null) {
result[0] = i;
result[1] = got;
break;
}
map.put(nums[i], i);
}
return result;
}
}
and it scores 2ms when submitted. Let's rewrite it using our hash function and linear probing. We'll need two arrays, one for keys and one for values:
int size;
int[] keys;
int[] values;
We'll use the integer hash function I defined above. Now, to put a key-value pair into our hash table, we'll use linear probing: we'll cycle through the array, starting from the location pointed by the hash code of our key, until we either find the same key, or an empty cell:
void put(int key, int value) {
int code = hash(key);
int k = keys[code];
int v = values[code];
while (v != 0 && key != k) {
code = (code + 1) % size;
k = keys[code];
v = values[code];
}
keys[code] = key;
// values are [0..n); we add 1 so 0 means "free"
values[code] = value + 1;
}
Getting a value is very similar:
int get(int key) {
int code = hash(key);
int k = keys[code];
int v = values[code];
while (v != 0 && key != k) {
code = (code + 1) % size;
k = keys[code];
v = values[code];
}
return v - 1; // -1 will mean "not found"
}
We'll need to allocate our table before we use it:
void init(int sz) {
size = sz;
keys = new int[size];
values = new int[size];
}
With that, the solution stays very similar to the HashMap one. For linear probing to be effective, we want our hash table to never be more than 50% full, so we allocate 2x size. Everything else is just the same:
public int[] twoSum(int[] nums, int target) {
init(nums.length * 2 + 1);
int[] result = new int[2];
for (int i = 0; i < nums.length; ++i) {
int needed = target - nums[i];
int got = get(needed);
if (got != -1) {
result[0] = i;
result[1] = got;
break;
}
put(nums[i], i);
}
return result;
}
And it scores 1ms! Of course, 1ms vs 2ms is not that much of a difference, but the difference can be huge on problems with larger test cases.
Depending on what kind of data you need to store, if zeros are acceptable keys or values, you might need to change the way you put your data in the hash table, e.g. do something else where I add 1 to accommodate zero values.
Store graphs in arrays
Very often you will be given a graph as an array of edges: int[][] edges, where each element edge is an array of two elements, edge[0] and edge[1], the two vertices of the given edge (which can be directed or not, depending on the problem).
Normally, you would convert this to something like ArrayList<ArrayList<Integer>> storing, for each vertex, an array of adjacent vertices, but that's a lot of allocations! Instead, we can store the whole graph in three arrays:
int[] graph = new int[2 * edges.length];
int[] degree = new int[n];
int[] offset = new int[n];
We will calculate the degree of each vertex first:
for (int[] edge : edges) {
int from = edge[0], to = edge[1];
++degree[from];
++degree[to];
}
Then calculate offsets of each vertex in the graph array, accumulating the degrees:
int sumDegree = 0;
for (int i = 0; i < n; ++i) {
offset[i] = sumDegree;
sumDegree += degree[i];
}
Finally, iterate the edges again, this time building the adjacency lists, using a temporary array for counting how many adjacent vertices we have already processed:
int[] counts = new int[n];
for (int[] edge : edges) {
int from = edge[0], to = edge[1];
graph[offset[from] + counts[from]++] = to;
graph[offset[to] + counts[to]++] = from;
}
With this representation, it's very easy to write any graph traversal, for example, your regular BFS:
boolean[] visited = new boolean[n];
int[] queue = new int[n];
int r = 0, w = 0;
queue[w++] = start;
visited[start] = true;
while (r < w) {
int curr = queue[r++];
int itsOffset = offset[curr];
int itsDegree = degree[curr];
for (int i = 0; i < itsDegree; ++i) {
int to = graph[itsOffset + i];
if (!visited[to]) {
visited[to] = true;
queue[w++] = to;
}
}
}
Sort arrays manually
Really. Just implement your regular quicksort or heapsort on an array. As an added bonus, you will be able to add extras such as tracking the position of each element while sorting. I found that my homemade quicksort implementation often beats the standard Arrays.sort or Collections.sort.
void quicksort(int[] arr, int l, int r) {
// use the average of arr[l] and arr[r] as the pivot
// to make worst-case inputs less likely
int pivot = arr[l] + ((arr[r] - arr[l]) >> 1);
int i = l, j = r;
while (i <= j) {
while (arr[i] < pivot) ++i;
while (arr[j] > pivot) --j;
if (i <= j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
++i;
--j;
}
}
if (l < j) quicksort(arr, l, j);
if (i < r) quicksort(arr, i, r);
}
I'm following these rules in my Java solutions and, in most cases, beat more than 90% of submissions. There are some exceptions: for example, I found that a trie is better to implement with allocations instead of trying to put it into an array, probably because that array becomes too huge to be effectively cached. Try this if you are interested, and you'll see what works for you, and what does not.
And don't use any of this on a real interview. Really, just don't.