LeetCode 3Sum Java Solution

Question

I have this Java solution to LeetCode's 3Sum problem.

I would be really grateful if I could get feedback on correctness, scalability, efficiency, coding best practices, and OOP design.

I'm relatively new to Java.

class Solution
{
    public List<List<Integer>> threeSum(int[] nums)
    {
        List l1 = new ArrayList<ArrayList>();
        
        for (int idx = 0; idx < nums.length; idx++)
        {
            if (idx > 0 && nums[idx] == nums[idx - 1]) continue;

            HashMap<Integer, Integer> hash = new HashMap<>();
            
            for (int idxInner = idx + 1; idxInner < nums.length; idxInner++)
            {
                if (
                     hash.get(nums[idxInner]) != null && 
                     nums[idxInner]+hash.get(nums[idxInner]) == -1*nums[idx]
                   )
                {
                    List l2 = new ArrayList<Integer>();
                    
                    addInList(l2, nums[idx]);
                    addInList(l2, hash.get(nums[idxInner]));
                    addInList(l2, nums[idxInner]);

                    l1.add(l2);
                }
                else
                {
                    hash.put(-1*(nums[idx] + nums[idxInner]), nums[idxInner]);
                }
            }
        }
        
        removeDuplicates(l1);
        
        return l1;
    }
    
    public void addInList(List<Integer> list, int num)
    {
        if (list == null) return;
        
        int lSize = list.size();
        
        if (lSize == 0)
        {
            list.add(num);
            return;
        }
        
        int idx = 0;
        while (idx < lSize && list.get(idx) < num)
        {
            idx++;
        }
        
        if (idx < lSize) list.add(idx, num);
        else list.add(num);
        
        return;
    }
    
    public void removeDuplicates(List<ArrayList<Integer>> lists)
    {
        if(lists == null) return;

        for(int outer = 0; outer < lists.size(); outer++)
        {
            for(int inner = outer + 1; inner < lists.size(); inner++)
            {
                
                if (areDuplicates(lists.get(outer), lists.get(inner)))
                {
                    
                    lists.remove(inner);
                    inner--;
                }
            }
        }
    }
                    
    public boolean areDuplicates(ArrayList<Integer> first, ArrayList<Integer> second)
    {
        if (first == null && first == second) return true;
        if (first == null || second == null) return false;
        
        int fSize = first.size();
        int sSize = second.size();
        
        if (fSize != sSize) return false;
        
        for(int idx = 0; idx < fSize; idx++)
        {
            if (first.get(idx) != second.get(idx)) return false;
        }
        
        return true;        
    }
}

I get a timeout error on LeetCode if I try to run this.

Answer 1

The common Java style guide lines are that opening block parentheses are on the same line. Also you should always use block parentheses, even for single lines.

---

public List<List<Integer>> threeSum(int[] nums)

Integer and int are only interchangeable because the compiler supports that with AutoBoxing. having this might or might not be desirable or a problem.

In this case, the signature is obviously given, but it should be int[][].

---

        List l1 = new ArrayList<ArrayList>();

Always use descriptive variable names, overall your names are quite bad, they almost never tell one what the variable is or is used for.

for (int idx = 0; idx < nums.length; idx++)

And don't shorten names just because you can, it makes the code only harder to read and maintain.

---

for (int idxInner = idx + 1; idxInner < nums.length; idxInner++)

If you have an inner loop, there's a good chance that extracting that logic into a function of its own will increase how easy the code is to understand.

---

    public void removeDuplicates(List<ArrayList<Integer>> lists)

Always use the least super interface that gives you the required functionality, in this case List. It means that your code is easier to reuse.

---

I'm not convinced that your solution is correct and it does seem oddly complicated. Overall, you seem to perform a lot of list iterations and management to filter out the duplicates, when I'd rather expect to iterate over the given list once and then process the result.

So, let's restart at the beginning. We've been given an array of ints and want to find the triplets which have a sum of zero. For that I'd expect three nested loops of some kind to iterate over the array and finding the triplets.

for (int firstValueIndex = 0; firstValueIndex < numbers.length - 2; firstValueIndex++) {
    int firstValue = numbers[firstValueIndex];
    
    for (int secondValueIndex = firstValueIndex + 1; secondValueIndex < numbers.length - 1; secondValueIndex++) {
        int secondValue = numbers[secondValueIndex];
        
        for (int thirdValueIndex = secondValueIndex + 1; thirdValueIndex < numbers.length; thirdValueIndex++) {
            int thirdValue = numbers[thirdValueIndex];
            
            int sum = firstValue + secondValue + thirdValue;
            
            if (sum == 0) {
                // Hit.
            }
        }
    }
}

With in place, we can gather the results. I'd suggest to keep using primitives for everything to do as little conversions as possible. You have to remember, that arrays are Objects, to a certain extend, so we can use them without conversion inside a List. int would need to be converted to Integers first. Which is not necessarily a costly operation, but something to keep in mind.

List<int[]> triplets = new ArrayList<>();

// Inside the if from above...
triplets.add(new int[] { firstValue, secondValue, thirdValue });

Now we have a list of all triplets. Next, I'd sort the values and remove duplicates:

for (int[] triplet : triplets) {
    Arrays.sort(triplet);
}

for (int tripletIndex = 0; tripletIndex < triplets.size() - 1; tripletIndex++) {
    int[] currentTriplet = triplets.get(tripletIndex);
    
    for (int searchIndex = tripletIndex + 1; searchIndex < triplets.size(); searchIndex++) {
        if (Arrays.equals(currentTriplet, triplets.get(searchIndex))) {
            triplets.remove(searchIndex);
            searchIndex--;
        }
    }
}

Not the prettiest code, but gets the job done. So all that remains is to convert it into the expected result format:

List<List<Integer>> result = new ArrayList<>();

for (int[] triplet : triplets) {
    result.add(Arrays.asList(
            Integer.valueOf(triplet[0]),
            Integer.valueOf(triplet[1]),
            Integer.valueOf(triplet[2])));
}

With the following sample generation, which should match the given constraints, this code runs in 12ms for me:

Random random = new Random(0);

int[] numbers = new int[random.nextInt(3000)];

for (int index = 0; index < numbers.length; index++) {
    numbers[index] = random.nextInt(200000) - 100000;
}

Upping this to 6k elements will yield an execution time of 50 seconds. So we might need to cut some slack here, somehow. The first thing we can try is to inline our sort and search, so that our list never grows beyond the final result list.

// Inside the if inside the three loops.

int[] triplet = new int[] { firstValue, secondValue, thirdValue };
Arrays.sort(triplet);

if (!contains(triplets, triplet)) {
    triplets.add(triplet);
}

Because the default List implementations don't handle arrays well, we'll have to write our own contains method:

private static final boolean contains(List<int[]> list, int[] value) {
    for (int[] item : list) {
        if (Arrays.equals(item, value)) {
            return true;
        }
    }
    
    return false;
}

That cuts some execution time, but not nearly enough. As I've said, the default implementations of List and Set don't handle arrays too well, so if we want to use a Set to further cut looping, we'll have to work around that limitation:

// At the start of the function:

Set<Integer> tripletHashes = new HashSet<>();

// Inside the if inside the three loops.

int[] triplet = new int[] { firstValue, secondValue, thirdValue };
Arrays.sort(triplet);

Integer tripletHash = Arrays.hashCode(triplet);

// If the hash is not in tripletHashes, we can be sure that it has not been
// added, however, if it was found, there we need to check the exact value
// because of possible hash collisions.
if (!tripletHashes.contains(tripletHash) || !contains(triplets, triplet)) {
    tripletHashes.add(tripletHash);
    triplets.add(triplet);
}

That further cuts execution time for me. Not by as much as I had hoped, but still.

---

What you have to keep in mind here, is that you're looking at you're looking with 27 billion iterations at 3000 entries. If we double that to 6000 entries, we already have 216 billion iterations.

There might be a good mathematical way to solve this, but this solution is purely mechanical based on the given description.

Answer 2

This is a nice start, but there's some stylistic stuff that could be improved.

Generally it's a good idea to name variables for what their purpose is. Names like l1 are difficult to understand. This varies depending on the language, but in Java people tend to be explicit with their variable naming, preferring descriptive names over concise ones.

When declaring a data structure, convention in Java is to declare the type as the interface.

public boolean areDuplicates(ArrayList<Integer> first, ArrayList<Integer> second)

is more commonly written as

public boolean areDuplicates(List<Integer> first, List<Integer> second)

This is because List defines a set of behaviours that you want to have, and ArrayList defines how they are implemented. If someone has made a data structure with the exact same behaviour as an ArrayList, then you want your methods to support that data structure as well.

The format of the code in quite unusual for Java. I'd run your code through an autoformatter, which deals with all that stuff for you. Personally I use Eclipse's default one, but there's loads of choice out there.

This isn't a complete review, and it's mainly my opinion, so feel free to include or discard this advice.