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

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  paers = new HashMap();
        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[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)\$ al

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  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

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

-
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?

-
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

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

-
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:

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

-
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.

-
If you're limiting your algorithm to a list of unique 32-bit integers, there's

StackExchange Code Review Q#121041, answer score: 4