Java: KSum optimization

Question

I recently got this problem to find out the ksum from a pair of numbers and i got the solution but just looking to have a more optimized solution:

public class KSum {


    public static void kSum(int[] array, int k){
        for(int i=0;i<array.length;i++){
            for(int j=i+1;j<array.length;j++){
                if(k==(array[i]+array[j])){
                    System.out.println("pair=("+array[i]+","+array[j]+")");
                }
            }
        }
    }
    public static void main(String[] args) {
        int[] array={1,2,3,4,5,6,7};
        kSum(array, 7);
    }

}

This site is not for help with optimizing working code, and for that consider asking on the [Code Review StackExchange](https://codereview.stackexchange.com/), but if you do go this route, please read their [help](https://codereview.stackexchange.com/help) links and their [how-to-ask](https://codereview.stackexchange.com/help/asking) links, because their site has high quality and inclusion/exclusion standards as well. — Hovercraft Full Of Eels, Jun 17 '18 at 20:12
I'm voting to close this question as off-topic because it is asking about working code. — Hovercraft Full Of Eels, Jun 17 '18 at 20:13
Also, when asking about "optimized" solutions, you must give a metric, a way to judge just what you mean by optimization. — Hovercraft Full Of Eels, Jun 17 '18 at 20:17

score 1 · Answer 1 · answered Jun 17 '18 at 20:19

A more efficient solution would be sorting the input array and by using two pointers, one starting at the beginning and the other at the end of the array, go through whole array in both direction.

Doing basic logic we advance both pointers with every comparison until they met.

public static void kSum(int[] array, int K) {
    Arrays.sort(array);

    int start = 0, end = array.length - 1;
    while (start <= end) {
        int sum = array[start] + array[end];
        if (sum < K) {
            ++start
        } else if (sum > K) {
            --end
        } else {
            System.out.println ("pair=(" + array[start] + "," + array[end] + ")");
            ++start;
            --end;
    }
}

Time complexity is linear O(n) in this case, so it's optimization from your original O(n^2).

There is also another solution to this problem using HashMap [1]

--

[1]Count pairs from an array whose sum is equal to a given number?

Java: KSum optimization

1 Answers1