Find two numbers that add up to a given total, from a formatted string

Question

The full challenge from codeeval.com can be viewed here.

Input

Your program should accept as its first argument a filename. This file will contain a comma separated list of sorted numbers and then the sum 'X', separated by semicolon. Ignore all empty lines. If no pair exists, print the string NULL.

Output

Print out the pairs of numbers that equal to the sum X. The pairs should themselves be printed in sorted order i.e the first number of each pair should be in ascending order.

I am writing a program to solve the above conditions. It currently works, however I believe it can be optimized to run better. This challenge is unique, since it requires you to work with a String for input, and to output a specifically formatted String as well. The problem with this is memory efficiency, as I have to convert this String to a String array, and then further convert it to a workable int array.

I am a student developer, and I don't have much experience, so any tips and tricks would be helpful.

Java

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class SomeClass {
    public static void main(String[] gras) {
        String line = "1,2,3,4,5;6"; //replace string with test case

        //code
        String[] j = line.split(";")[0].split(",");
        int[] input = new int[j.length];
        for (int i = 0; i < j.length; i++) {
            input[i] = Integer.parseInt(j[i]);
        }
        Arrays.sort(input);
        int k = Integer.parseInt(line.split(";")[1]);
        // Modified Algorithm
        Map<Integer, Integer> paers = new HashMap<Integer, Integer>();
        boolean d = false;
        for (int i = input.length - 1; i >= 0; i--) {
            paers.put(k - input[i], input[i]);
        }
        for (int i = 0; i < input.length; i++) {
            if (paers.containsKey(input[i]) && paers.get(input[i]) > input[i]) {
                if (d) {
                    System.out.print(";");
                }
                d = true;
                System.out.print(input[i] + "," + paers.get(input[i]));
            }
        }
        if (!d) System.out.println("NULL"); else System.out.println("");
    }
}

As far as what I've tried, this is my final product. I changed my solution from using a naive \$O(n^2)\$ algorithm to this \$O(3n)\$ algorithm. Again, my terminology might be off, I'm just figuring this stuff out. Also, the code is tested and working.

Answer 1

Improved algorithm

You can significantly reduce the memory requirements of your algorithm by not creating any objects, including avoiding Maps, Sets, and String concatenations (the +s you use in print statements). You only need to use a constant amount of memory, comprised completely of primitives stored on the stack (avoiding garbage collection).

You can significantly reduce the time requirements of your algorithm by using a simple trick that allows you to scan the input list only once by moving toward the middle from the left and the right.

public final class SumPairs {
    public static final void printSumPairs(final String input) {
        final int inputLength = input.length();

        // On the left, move to the very first number.
        int leftStartIndex = 0;
        int leftEndIndex   = input.indexOf(',', 1);
        int leftNumber     = parseIntFromSubstring(input, leftStartIndex, leftEndIndex);

        // On the right, move to the very last number.
        int rightEndIndex   = input.lastIndexOf(';', inputLength - 2);
        int rightStartIndex = input.lastIndexOf(',', rightEndIndex - 2) + 1;
        int rightNumber     = parseIntFromSubstring(input, rightStartIndex, rightEndIndex);

        // Figure out the desired sum.
        final int desiredSum = parseIntFromSubstring(input, rightEndIndex + 1, inputLength);

        boolean noOutputYet = true;

        while (leftStartIndex < rightStartIndex) {
            final int currentSum = leftNumber + rightNumber;

            if (currentSum > desiredSum) {
                // On the right, move to the previous distinct number.
                int oldRightNumber;
                do {
                    oldRightNumber = rightNumber;

                    rightEndIndex   = rightStartIndex - 1;
                    rightStartIndex = input.lastIndexOf(',', rightEndIndex - 2) + 1;
                    rightNumber     = parseIntFromSubstring(input, rightStartIndex, rightEndIndex);
                } while ((rightNumber == oldRightNumber) && (leftStartIndex < rightStartIndex));
            }
            else { 
                if (currentSum == desiredSum) {
                    if (noOutputYet) noOutputYet = false;
                    else System.out.print(';');

                    System.out.print(leftNumber);
                    System.out.print(',');
                    System.out.print(rightNumber);
                }

                // On the left, move to the next distinct number.
                int oldLeftNumber;
                do {
                    oldLeftNumber = leftNumber;

                    leftStartIndex = leftEndIndex + 1;
                    leftEndIndex   = input.indexOf(',', leftStartIndex + 1);
                    leftNumber     = parseIntFromSubstring(input, leftStartIndex, leftEndIndex);
                } while ((leftNumber == oldLeftNumber) && (leftStartIndex < rightStartIndex));
            }
        }

        if (noOutputYet) System.out.print("NULL");
        System.out.println();
    }

    // Java 7 and later's String#substring creates a new char[] array just about every time it's used.
    // Since Integer#parseInt requires a full String, we'd have to let String#substring create a lot of char[]s if we used Integer#parseInt.
    // We'd like to avoid that to reduce memory requirements and to eliminate garbage collection.

    // WARNING: This method doesn't actually check whether there is a valid number.
    //          That's your job!
    private static final int parseIntFromSubstring(final String str, int start, final int end) {
        int result = 0;
        final boolean negative = str.charAt(start) == '-';
        if (negative) start++;

        for (; start < end; start++)
            result = 10*result + str.charAt(start) - '0';

        if (negative) return -result;
        else return result;
    }

    public static final void main(String[] args) {
        printSumPairs("1,2,3,4,5,6;6");
    }
}

---

Critiques

Problem statement

1. The part about outputting "NULL" should be in the section about output, not the section about input.

2. The characters in the input are not fully specified. Will there be spaces or other characters to ignore mixed in? Can numbers have a decimal point? Can numbers be negative? Are newlines separators for separate problems to solve?

3. The CodeEval challenge says not to output duplicate pairs. For example "3,3,3,3;6" should output "3,3", not "3,3;3,3;3,3;...".

Your solution

1. The problem statement says to read lines from a file, but your algorithm doesn't do that.

2. You don't need to sort the array of ints. The problem statement says they'll already be sorted.

Time complexity

Your code shouldn't be regarded as \$O(3n)\$ for a few reasons:

1. Big O notation ignores constant multiples like 3. It should be \$O(n)\$, not \$O(3n)\$.

2. You use Arrays#sort when you don't need to. While it uses a nicer version of quicksort than normal, it still has a \$O(n^2)\$ worst case time complexity.

3. If you're limiting your algorithm to a list of unique 32-bit integers, there's only so many of those available to put in your input list. This means that there will be an input that takes the longest amount of time to produce an answer. This means that you have a constant upper bound on the time needed, which makes your algorithm (including your 'naive' one) \$O(1)\$.

   If you're not limiting your algorithm to a list of unique 32-bit integers, then you should realize that it takes a lot longer to add together two integers with billions of digits than it does to add 1 and 2. The time complexity of addition is \$O(m)\$, where \$m\$ is the number of digits in the largest number in the input list. This means your complexity will be \$O(mn)\$.

Answer 2

Instead of using a map

Map<Integer, Integer> paers = new HashMap<Integer, Integer>();

you can simply use a set

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

because you can always check whether you have seen k-input[i] before by checking the set. But, this would give pairs in reverse order. Hence, use stringbuilder to construct the string and reverse it in the end before printing it. This would also improve your time complexity because you only need to iterate through the array once.

Naming: k could be better named as target and d as foundOnePair.

Here is the code.

public static void printPairsThatMakeTarget(String line){

    String[] j = line.split(";")[0].split(",");
    int[] input = new int[j.length];
    for (int i = 0; i < j.length; i++) {
        input[i] = Integer.parseInt(j[i]);
    }
    Arrays.sort(input);
    int target = Integer.parseInt(line.split(";")[1]);
    // Modified Algorithm
    Set<Integer> set = new HashSet<>();
    StringBuilder result = new StringBuilder();
    boolean foundOnePair = false;
    for (int i = input.length - 1; i >= 0; i--) {
        if(set.contains(target - input[i])){
            if (foundOnePair) {
                result.append(";");
            }
            foundOnePair = true;
            result.append((target - input[i]) + "," + input[i]);
        }
        else
            set.add(input[i]);
    }
    if (!foundOnePair) result.append("NULL"); 
    else{ 
        result.reverse();
    }
    System.out.println(result.toString());
}