Find the number of K-Complementary pairs in an array

Below is the program to find k-complementary pairs: K = A[i] + A[j];.

package org.test;

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

public class ComplementaryPairs {

    public int noOfComplementaryPairs(int arr[],int k){
        int result = 0;
        for(int i=0;i<=arr.length;i++){
            for(int j=i;j<arr.length-1;j++){
                if(arr[i] + arr[j+1] == k){
                    result++;
                }
            }
        }
        return result * 2;
    }
    public static void main(String[] args) {
        int[] intArray = new int[] {4,5,6,3,1,8,-7,-6};
        int k = 1;
        System.out.println("No of k complementary pairs : "+new ComplementaryPairs().noOfComplementaryPairs(intArray, k));
    }

}

What is the time complexity of the above program? Is there a better way to optimize it further?

Current algorithm

The time complexity of the current solution is O(N²): for a given array of length N, it needs to loop through its elements from 0 to its length, and then for each of those, loop again through the elements after it. Note that it is still O(N²), even with the logic of avoiding duplicate indexes (if the pair (0,1) was a solution, it always follows that (1,0) is one, so we don't need to test it).

About the code itself, the first for loop is deceiving:

for(int i=0;i<=arr.length;i++){
    for(int j=i;j<arr.length-1;j++){
        if(arr[i] + arr[j+1] == k){

It makes the reader think that i will go up to arr.length. What's worse, it makes the reader think the algorithm fails because we fetch arr[i] later on, which cannot work for arr.length (and would fail with an ArrayIndexOutOfBoundsException). In reality, it won't, because there is a second inner loop of j going from i to arr.length-1, so when i is greater than arr.length-1, nothing will happen anyway.

I suggest making that clear in the bounds used. Consider having:

for(int i=0;i<arr.length-1;i++){
    for(int j=i;j<arr.length-1;j++){
        if(arr[i] + arr[j+1] == k){

In the same way, instead of reasoning with j+1, you could have j loop through its natural bounds and reason with j:

for (int i = 0; i < arr.length - 1; i++) {
    for (int j = i + 1; j < arr.length; j++) {
        if (arr[i] + arr[j] == k) {

With those bounds, it's clear to everyone reading the code that no out of bounds exception can happen. Note also how I added white spaces around the different operators and calculations: it adds to clarity.

Also, maybe I wouldn't make this method an instance method, rather a static one that is directly invoked in main.

Better performance

It would be possible to solve this problem in O(N) time complexity, instead of O(N²), at the expense of also being O(N) in terms of memory.

The idea is that we want to avoid looping through the array again and again. Here's another approach:

• Go through the array once, and store in a Map the difference of the wanted sum and the current element mapped to how many times it occured. Effectively, this map remembers how much we're missing for an element at a given index so that the sum can be reached.

• Go through the array a second time, and check whether the map contains this element. If it does, then it means that our map contains an element e for which e = sum - arr[i], so it means that we've found a matching pair. And the number of matching pair we found, is the number of times this element appears in the array, which is the value of the map.

That's how it would look like with the example in the question where the sum to look for is 1:

` arr = 4 5 6 3 1 8 -7 -6
1st pass, map = -3 -4 -5 -2 0 -7 8 7

This shows that there are 2 such pairs, and that is the answer. As an example of putting this into code, and using Java 8, you could have:

public int noOfComplementaryPairs(int arr[], int k) {
    Map map = new HashMap();
    for (int i = 0; i  map.getOrDefault(element, 0)).sum();
}

StackExchange Code Review Q#145071, answer score: 10